Бързо намиране на подобни низове с PostgreSQL

По начина, по който го имате, трябва да се изчисли приликата между всеки елемент и всеки друг елемент от таблицата (почти кръстосано съединение). Ако таблицата ви има 1000 реда, това вече е 1 000 000 (!) изчисления за сходство, преди те могат да бъдат проверени спрямо състоянието и сортирани. Ужасно мащабира.

Използвайте SET pg_trgm.similarity_threshold и % вместо това оператор. И двете се предоставят от pg_trgm модул. По този начин триграма GiST индекс може да се използва с голям ефект.

Конфигурационният параметър pg_trgm.similarity_threshold замени функциите set_limit() и show_limit() в Postgres 9.6. Оттеглените функции все още работят (от Postgres 13). Също така производителността на индексите GIN и GiST се подобри по много начини след Postgres 9.1.

Опитайте вместо това:

SET pg_trgm.similarity_threshold = 0.8;  -- Postgres 9.6 or later
  
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;

По-бързо с порядък, но все пак бавно.

pg_trgm.similarity_threshold е "персонализирана" опция, която може да се обработва като всяка друга опция. Вижте:

• Запитване за параметър (настройка postgresql.conf) като "max_connections"

Може да искате да ограничите броя на възможните двойки, като добавите предварителни условия (като съвпадение на първите букви) преди кръстосано свързване (и поддържа това със съвпадащ функционален индекс). Изпълнението на кръстосано съединение се влошава с O(N²) .

Товане работи защото не можете да се обърнете към изходни колони в WHERE или HAVING клаузи:

WHERE ... sim > 0.8

Това е според стандарта SQL (който се обработва доста слабо от някои други RDBMS). От друга страна:

ORDER BY sim DESC

Работи защото изходните колони могат да се използва в GROUP BY и ORDER BY . Вижте:

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

Тестов случай

Проведох бърз тест на стария си тестов сървър, за да потвърдя твърденията си.
PostgreSQL 9.1.4. Времена, взети с EXPLAIN ANALYZE (най-доброто от 5).

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 set_limit(0.8);

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 ms

Иначе резултати са идентични. Съветът е добър. И това е за само 1000 реда !

GIN или GiST?

GIN често осигурява превъзходна производителност на четене:

• Разлика между GiST и GIN индекс

Но не в този конкретен случай!

Това може да се реализира доста ефективно от GiST индекси, но не и от GIN индекси.

• Многоколонов индекс на 3 полета с разнородни типове данни