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

Question

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

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

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 без получения ошибки "колонка сим не существует".

Я хотел бы, чтобы любой запрос сделал запрос быстрее.

Answer 1

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

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

---

использование set_limit()и % оператор вместо. Оба предоставлены pg_trgm модуль.

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

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;

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

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

---

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

WHERE ... sim > 0.8

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

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

ORDER BY sim DESC

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

• PostgreSQL повторно использует результат вычисления в запросе выбора

Прецедент

Я провел быстрый тест на своем старом тестовом сервере, чтобы проверить свои претензии.
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 мс
Используется индекс 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.

• Многоколонный индекс на 3 поля с разнородными типами данных