Encontrar cadenas similares con PostgreSQL rápidamente

De la forma en que lo tiene, se debe calcular la similitud entre cada elemento y todos los demás elementos de la tabla (casi una unión cruzada). Si su tabla tiene 1000 filas, eso ya es 1,000,000 (!) Cálculos de similitud, antes se pueden comparar con la condición y ordenar. Escala terriblemente.

Use SET pg_trgm.similarity_threshold y el % operador en su lugar. Ambos son proporcionados por pg_trgm módulo. De esta manera, un índice GiST de trigrama se puede utilizar con gran efecto.

El parámetro de configuración pg_trgm.similarity_threshold reemplazó las funciones set_limit() y show_limit() en Postgres 9.6. Las funciones en desuso todavía funcionan (a partir de Postgres 13). Además, el rendimiento de los índices GIN y GiST mejoró de muchas maneras desde Postgres 9.1.

Prueba en su lugar:

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;

Más rápido por órdenes de magnitud, pero aún lento.

pg_trgm.similarity_threshold es una opción "personalizada", que se puede manejar como cualquier otra opción. Ver:

• Consulte un parámetro (configuración postgresql.conf) como "max_connections"

Es posible que desee restringir la cantidad de pares posibles agregando condiciones previas (como hacer coincidir las primeras letras) antes unión cruzada (y apoyar eso con un índice funcional coincidente). El rendimiento de una unión cruzada se deteriora con O(N²) .

Esto no funciona porque no puede hacer referencia a las columnas de salida en WHERE o HAVING cláusulas:

WHERE ... sim > 0.8

Eso es de acuerdo con el estándar SQL (que es manejado de manera bastante flexible por algunos otros RDBMS). Por otro lado:

ORDER BY sim DESC

Funciona porque las columnas de salida pueden ser usado en GROUP BY y ORDER BY . Ver:

• PostgreSQL reutilizando el resultado del cálculo en la consulta de selección

Caso de prueba

Realicé una prueba rápida en mi antiguo servidor de prueba para verificar mis afirmaciones.
PostgreSQL 9.1.4. Tiempos tomados con EXPLAIN ANALYZE (al mejor de 5).

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

Primera ronda de pruebas con índice GIN:

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

Segunda ronda de pruebas con índice GIST:

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

Nueva consulta:

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;

Índice GIN utilizado, 64 resultados:tiempo de ejecución total:484,022 ms
Índice GIST utilizado, 64 resultados:tiempo de ejecución total:248,772 ms

Consulta anterior:

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;

Índice GIN no utilizado, 64 resultados:tiempo de ejecución total:6345,833 ms
Índice GIST no utilizado, 64 hits:tiempo de ejecución total:6335,975 ms

Por lo demás resultados idénticos. El consejo es bueno. Y esto es para solo 1000 filas !

GIN o GiST?

GIN a menudo proporciona un rendimiento de lectura superior:

• Diferencia entre el índice GiST y GIN

¡Pero no en este caso en particular!