At finde lignende strenge med PostgreSQL hurtigt

Som du har det, skal ligheden mellem hvert element og hvert andet element i tabellen beregnes (næsten en krydsforbindelse). Hvis din tabel har 1000 rækker, er det allerede 1.000.000 (!) lighedsberegninger, før disse kan kontrolleres i forhold til tilstanden og sorteres. Skalerer frygteligt.

Brug SET pg_trgm.similarity_threshold og % operatør i stedet for. Begge leveres af pg_trgm modul. På denne måde kan et trigram GiST-indeks bruges med stor effekt.

Konfigurationsparameteren pg_trgm.similarity_threshold erstattede funktionerne set_limit() og show_limit() i Postgres 9.6. De forældede funktioner fungerer stadig (fra Postgres 13). Ydeevnen af GIN- og GiST-indekser er også forbedret på mange måder siden Postgres 9.1.

Prøv i stedet:

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;

Hurtigere i størrelsesordener, men stadig langsomt.

pg_trgm.similarity_threshold er en "tilpasset" mulighed, som kan håndteres som enhver anden mulighed. Se:

Forespørg en parameter (postgresql.conf indstilling) som "max_connections"

Du ønsker måske at begrænse antallet af mulige par ved at tilføje forudsætninger (som matchende første bogstaver) før krydssammenføjning (og understøtte det med et matchende funktionsindeks). Udførelsen af en kryds-tilslutning forringes med O(N²) .

Dette virker ikke fordi du ikke kan henvise til outputkolonner i WHERE eller HAVING klausuler:

WHERE ... sim > 0.8

Det er i henhold til SQL-standarden (som håndteres ret løst af visse andre RDBMS). På den anden side:

ORDER BY sim DESC

Virker fordi outputkolonner kan bruges i GROUP BY og ORDER BY . Se:

PostgreSQL-genbrug af beregningsresultat i udvalgt forespørgsel

Testcase

Jeg kørte en hurtig test på min gamle testserver for at bekræfte mine påstande.
PostgreSQL 9.1.4. Tider taget med EXPLAIN ANALYZE (bedst af 5).

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

Første runde af test med GIN-indeks:

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

Anden testrunde med GIST-indeks:

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

Ny forespørgsel:

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-indeks brugt, 64 hits:samlet kørselstid:484.022 ms
GIST-indeks brugt, 64 hits:samlet kørselstid:248.772 ms

Gammel forespørgsel:

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-indeks ikke brugt, 64 hits:samlet køretid:6345.833 ms
GIST-indeks ikke brugt, 64 hits:samlet køretid:6335.975 ms

Ellers identiske resultater. Rådene er gode. Og dette er for kun 1000 rækker !

GIN eller GiST?

GIN giver ofte overlegen læseydelse:

Forskel mellem GiST og GIN-indeks

Men ikke i dette særlige tilfælde!

Dette kan implementeres ganske effektivt af GiST-indekser, men ikke af GIN-indekser.

Flerkolonneindeks på 3 felter med heterogene datatyper