Быстрый поиск похожих строк с PostgreSQL

Мне нужно создать ранжирование аналогичных строк в таблице.

У меня есть следующая таблица

create table names (
name character varying(255)
);

В настоящее время я использую модуль pg_trgm, который предлагает функцию similarity, но у меня есть проблема с эффективностью. Я создал индекс, как Руководство Postgres предлагает:

CREATE INDEX trgm_idx ON names USING gist (name gist_trgm_ops);

и я выполняю следующий запрос:

select (similarity(n1.name, n2.name)) as sim, n1.name, n2.name
from names n1, names n2
where n1.name != n2.name and similarity(n1.name, n2.name) > .8
order by sim desc;

Запрос работает, но очень медленно, когда у вас сотни имен. Более того, возможно, я забыл немного SQL, но я не понимаю, почему я не могу использовать условие and sim > .8, не получив ошибку "column sim does not exist".

Мне бы хотелось, чтобы запрос был быстрее.

Ответы

Ответ 1

Обновление: В Postgres 9.6 (бета с момента написания) функции set_limit() и show_limit() заменяются параметром конфигурации pg_trgm.similarity_threshold (наряду с несколькими другими улучшениями модуля pg_trgm). Функции устаревают, но все еще работают.

Кроме того, производительность индексов GIN и GiST была улучшена несколькими способами после Postgres 9.1.

Используйте set_limit() и %. Оба обеспечивают модуль pg_trgm.

То, как вы это делаете, должно быть рассчитано сходство между каждым элементом и каждым другим элементом таблицы (почти перекрестное соединение). Если ваша таблица имеет 1000 строк, это 1 000 000 (!) Вычисленных сходств, прежде чем их можно будет проверить на соответствие и отсортировать. Попробуйте:

SELECT set_limit(0.8);

SELECT similarity(n1.name, n2.name) AS sim, n1.name, n2.name
FROM   names n1
JOIN   names n2 ON n1.name <> n2.name
               AND n1.name % n2.name
ORDER  BY sim DESC;

Быть быстрее на порядок, но он все равно будет медленным.

Вы можете ограничить количество возможных пар, введя дополнительные предварительные условия (например, сопоставление первой буквы) до скрещивания (и поддерживайте это с соответствующим функциональным индексом). Производительность cross join ухудшает quadratically с увеличением числа записей - O (N²).

Что касается вашего вспомогательного вопроса:

WHERE ... sim > 0.8

Не работает, потому что вы не можете ссылаться на выходные столбцы в предложениях WHERE или HAVING. Это согласно (немного запутанному, предоставленному) стандарту SQL - который обрабатывается довольно слабо некоторыми другими СУБД.

С другой стороны:

ORDER BY sim DESC

Работает, поскольку выходные столбцы могут использоваться в GROUP BY и ORDER BY. Подробности:

Тестовый кейс

Я проверил быстрый тест на своем старом тестовом сервере, чтобы проверить мои претензии.
PostgreSQL 9.1.4. Время, затраченное на EXPLAIN ANALYZE (лучший из пяти).

CREATE TEMP table t AS 
SELECT some_col AS name FROM some_table LIMIT 1000;  -- real life test strings

Первый раунд тестов с индексом GIN:

CREATE INDEX t_gin ON t USING gin(name gin_trgm_ops);  -- round1: with GIN index

Второй раунд тестов с индексом GIST:

DROP INDEX t_gin;
CREATE INDEX t_gist ON t USING gist(name gist_trgm_ops);

Новый запрос:

-- SELECT show_limit();
SELECT set_limit(0.8);   -- fewer hits and faster with higher limit

SELECT similarity(n1.name, n2.name) AS sim, n1.name, n2.name
FROM   t n1
JOIN   t n2 ON n1.name <> n2.name
           AND n1.name % n2.name
ORDER  BY sim DESC;

Используется индекс GIN, 64 обращения: общая продолжительность выполнения: 484.022 ms
Используется индекс GIST, 64 обращения: общая продолжительность выполнения: 248,772 мс

Старый запрос:

SELECT (similarity(n1.name, n2.name)) as sim, n1.name, n2.name
FROM   t n1, t n2
WHERE  n1.name != n2.name
AND    similarity(n1.name, n2.name) > 0.8
ORDER  BY sim DESC;

Индекс GIN не, 64 просмотров: общая продолжительность: 6345.833 мс
Индекс GIST не, 64 обращения: общая продолжительность: 6335,975 мс

Иначе идентичные результаты. Совет хорош. И это всего за 1000 строк.

GIN или GiST?

GIN часто обеспечивает превосходную производительность чтения:

Но не в этом конкретном случае:

Это может быть эффективно реализовано с помощью индексов GiST, но не Индексы GIN.