Schnelles Finden ähnlicher Zeichenfolgen mit PostgreSQL

So wie Sie es haben, muss die Ähnlichkeit zwischen jedem Element und jedem anderen Element der Tabelle berechnet werden (fast ein Cross Join). Wenn Ihre Tabelle 1000 Zeilen hat, sind das bereits 1.000.000 (!) Ähnlichkeitsberechnungen, vorher diese können auf den Zustand geprüft und sortiert werden. Skaliert schrecklich.

Verwenden Sie SET pg_trgm.similarity_threshold und der % Betreiber statt. Beide werden von pg_trgm bereitgestellt Modul. Auf diese Weise kann ein GiST-Index mit Trigramm sehr effektiv verwendet werden.

Der Konfigurationsparameter pg_trgm.similarity_threshold ersetzt die Funktionen set_limit() und show_limit() in Postgres 9.6. Die veralteten Funktionen funktionieren noch (ab Postgres 13). Außerdem hat sich die Leistung von GIN- und GiST-Indizes seit Postgres 9.1 in vielerlei Hinsicht verbessert.

Versuchen Sie stattdessen:

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;

Um Größenordnungen schneller, aber immer noch langsam.

pg_trgm.similarity_threshold ist eine "benutzerdefinierte" Option, die wie jede andere Option gehandhabt werden kann. Siehe:

• Fragen Sie einen Parameter (postgresql.conf-Einstellung) wie "max_connections" ab

Möglicherweise möchten Sie die Anzahl der möglichen Paare einschränken, indem Sie vorher Vorbedingungen (z. B. übereinstimmende Anfangsbuchstaben) hinzufügen Cross Joining (und unterstützen Sie dies mit einem passenden funktionalen Index). Die Leistung eines Cross Join verschlechtert sich mit O(N²) .

Das funktioniert nicht da Sie in WHERE nicht auf Ausgabespalten verweisen können oder HAVING Klauseln:

WHERE ... sim > 0.8

Das entspricht dem SQL-Standard (der von bestimmten anderen RDBMS eher locker gehandhabt wird). Andererseits:

ORDER BY sim DESC

Funktioniert weil Ausgabespalten können in GROUP BY verwendet werden und ORDER BY . Siehe:

• PostgreSQL-Wiederverwendung des Berechnungsergebnisses in ausgewählter Abfrage

Testfall

Ich habe einen Schnelltest auf meinem alten Testserver durchgeführt, um meine Behauptungen zu überprüfen.
PostgreSQL 9.1.4. Mit EXPLAIN ANALYZE aufgenommene Zeiten (Beste von 5).

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

Erste Testrunde mit GIN-Index:

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

Zweite Testrunde mit GIST-Index:

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

Neue Abfrage:

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;

Verwendeter GIN-Index, 64 Treffer:Gesamtlaufzeit:484.022 ms
Verwendeter GIST-Index, 64 Treffer:Gesamtlaufzeit:248.772 ms

Alte Abfrage:

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-Index nicht gebraucht, 64 Treffer:Gesamtlaufzeit:6345,833 ms
GIST-Index nicht gebraucht, 64 Treffer:Gesamtlaufzeit:6335,975 ms

Ansonsten identische Ergebnisse. Beratung ist gut. Und das für nur 1000 Zeilen !

GIN oder GiST?

GIN bietet oft eine überlegene Leseleistung:

• Unterschied zwischen GiST- und GIN-Index

Aber nicht in diesem speziellen Fall!