Trovare rapidamente stringhe simili con PostgreSQL

A modo tuo, la somiglianza tra ogni elemento e ogni altro elemento della tabella deve essere calcolata (quasi un cross join). Se la tua tabella ha 1000 righe, sono già 1.000.000 (!) di calcoli di somiglianza, prima quelli possono essere controllati rispetto alla condizione e ordinati. Ridimensiona terribilmente.

Usa SET pg_trgm.similarity_threshold e il % operatore invece. Entrambi sono forniti da pg_trgm modulo. In questo modo, un indice GiST trigram può essere utilizzato con grande efficacia.

Il parametro di configurazione pg_trgm.similarity_threshold ha sostituito le funzioni set_limit() e show_limit() in Postgres 9.6. Le funzioni deprecate funzionano ancora (a partire da Postgres 13). Inoltre, le prestazioni degli indici GIN e GiST sono migliorate in molti modi da Postgres 9.1.

Prova invece:

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;

Più veloce per ordini di grandezza, ma comunque lento.

pg_trgm.similarity_threshold è un'opzione "personalizzata", che può essere gestita come qualsiasi altra opzione. Vedi:

• Interroga un parametro (impostazione postgresql.conf) come "max_connections"

Potresti voler limitare il numero di possibili coppie aggiungendo precondizioni (come la corrispondenza delle prime lettere) prima unione incrociata (e supportarla con un indice funzionale corrispondente). La performance di un cross join si deteriora con O(N²) .

Questo non funziona perché non puoi fare riferimento alle colonne di output in WHERE o HAVING clausole:

WHERE ... sim > 0.8

Questo è secondo lo standard SQL (che è gestito in modo piuttosto approssimativo da alcuni altri RDBMS). D'altra parte:

ORDER BY sim DESC

Funziona perché le colonne di output possono essere utilizzato in GROUP BY e ORDER BY . Vedi:

• Risultato del calcolo del riutilizzo di PostgreSQL nella query selezionata

Caso di prova

Ho eseguito un rapido test sul mio vecchio server di test per verificare le mie affermazioni.
PostgreSQL 9.1.4. Tempi presi con EXPLAIN ANALYZE (al meglio di 5).

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

Primo round di test con indice GIN:

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

Secondo round di test con indice GIST:

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

Nuova query:

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;

Indice GIN utilizzato, 64 hit:runtime totale:484,022 ms
Indice GIST utilizzato, 64 hit:runtime totale:248,772 ms

Vecchia query:

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;

Indice GIN non utilizzato, 64 risultati:durata totale:6345,833 ms
indice GIST non utilizzato, 64 risultati:autonomia totale:6335,975 ms

Altrimenti risultati identici. Il consiglio è buono. E questo è per solo 1000 righe !

GIN o GiST?

GIN offre spesso prestazioni di lettura superiori:

• Differenza tra indice GiST e GIN

Ma non in questo caso particolare!