Rychlé nalezení podobných řetězců pomocí PostgreSQL

Jak to máte, podobnost mezi každým prvkem a každým dalším prvkem tabulky musí být vypočtena (téměř křížové spojení). Pokud má vaše tabulka 1 000 řádků, je to již 1 000 000 (!) výpočtů podobnosti, před ty lze zkontrolovat podle stavu a třídit. Strašně se škáluje.

Použijte SET pg_trgm.similarity_threshold a % místo toho operátor. Obojí poskytuje pg_trgm modul. Tímto způsobem lze s velkým efektem použít trigramový GiST index.

Konfigurační parametr pg_trgm.similarity_threshold nahradil funkce set_limit() a show_limit() v Postgresu 9.6. Zastaralé funkce stále fungují (od Postgres 13). Od Postgresu 9.1 se také v mnoha ohledech zlepšil výkon indexů GIN a GiST.

Zkuste místo toho:

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;

Řádově rychlejší, ale stále pomalé.

pg_trgm.similarity_threshold je „přizpůsobená“ možnost, se kterou lze zacházet jako s jakoukoli jinou možností. Viz:

• Dotaz na parametr (nastavení postgresql.conf), jako je „max_connections“

Možná budete chtít omezit počet možných párů přidáním předpokladů (jako je shoda prvních písmen) před křížové spojování (a podpořte je odpovídajícím funkčním indexem). Výkon křížového spojení zhoršuje se O(N²) .

Toto nefunguje protože nemůžete odkazovat na výstupní sloupce v WHERE nebo HAVING klauzule:

WHERE ... sim > 0.8

To je podle standardu SQL (který je některými jinými RDBMS řešen poněkud volně). Na druhou stranu:

ORDER BY sim DESC

Funguje protože výstupní sloupce mohou použít v GROUP BY a ORDER BY . Viz:

• PostgreSQL znovu používá výsledek výpočtu ve výběrovém dotazu

Testovací případ

Provedl jsem rychlý test na svém starém testovacím serveru, abych ověřil svá tvrzení.
PostgreSQL 9.1.4. Časy získané pomocí EXPLAIN ANALYZE (nejlepší z 5).

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

První kolo testů s GIN indexem:

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

Druhé kolo testů s GIST indexem:

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

Nový dotaz:

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;

Použitý index GIN, 64 přístupů:celková doba běhu:484,022 ms
Použitý index GIST, 64 přístupů:celková doba běhu:248,772 ms

Starý dotaz:

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;

Index GIN není použito, 64 přístupů:celková doba běhu:6345,833 ms
index GIST není použito, 64 zásahů:celková doba běhu:6335,975 ms

Jinak shodné výsledky. Rada je dobrá. A to je pro pouhých 1000 řádků !

GIN nebo GiST?

GIN často poskytuje vynikající výkon při čtení:

• Rozdíl mezi indexem GiST a GIN

Ale ne v tomto konkrétním případě!

To lze poměrně efektivně implementovat pomocí indexů GiST, nikoli však pomocí indexů GIN.

• Vícesloupcový index na 3 polích s heterogenními datovými typy