español - Encontrar cadenas similares con PostgreSQL rápidamente
manual de postgresql 10 en español pdf (1)
Necesito crear una clasificación de cadenas similares en una tabla.
Tengo la siguiente tabla
create table names (
name character varying(255)
);
Actualmente, estoy usando el módulo pg_trgm que ofrece la función de similarity , pero tengo un problema de eficiencia. Creé un índice como el manual de Postgres sugiere :
CREATE INDEX trgm_idx ON names USING gist (name gist_trgm_ops);
y estoy ejecutando la siguiente consulta:
select (similarity(n1.name, n2.name)) as sim, n1.name, n2.name
from names n1, names n2
where n1.name != n2.name and similarity(n1.name, n2.name) > .8
order by sim desc;
La consulta funciona, pero es realmente lenta cuando tienes cientos de nombres. Además, tal vez olvidé un poco de SQL, pero no entiendo por qué no puedo usar la condición and sim > .8 sin obtener el error "la columna no existe".
Me gustaría cualquier pista para hacer la consulta más rápida.
Actualización: En Postgres 9.6 (versión beta de escritura), las funciones set_limit() y show_limit() se reemplazan con el parámetro de configuración pg_trgm.similarity_threshold (junto con varias otras mejoras al módulo pg_trgm ). Las funciones están en desuso pero aún funcionan.
Además, el rendimiento de los índices GIN y GiST se ha mejorado de varias maneras desde Postgres 9.1.
Use set_limit() y el operador % lugar. Ambos son proporcionados por el módulo pg_trgm .
De la forma en que lo tiene, la similitud entre cada elemento y todos los demás elementos de la tabla debe calcularse (casi una combinación cruzada). Si su tabla tiene 1000 filas, eso es 1,000,000 (!) Similitudes calculadas, antes de que puedan ser verificadas contra la condición y ordenadas. Tratar:
SELECT set_limit(0.8);
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;
Debería ser más rápido en órdenes de magnitud, pero seguirá siendo lento.
Es posible que desee restringir el número de pares posibles introduciendo más condiciones previas (como emparejar la primera letra) antes de la unión cruzada (y admitirlo con un índice funcional coincidente). El rendimiento de una combinación cruzada se deteriora de forma quadratically con el número creciente de registros: O (N²) .
En cuanto a su pregunta subsidiaria:
WHERE ... sim > 0.8
No funciona porque no puede hacer referencia a las columnas de salida en las cláusulas WHERE o HAVING . Eso es de acuerdo con el estándar de SQL (un poco confuso, otorgado), que se maneja de forma bastante flexible por otros RDBMS.
Por otra parte:
ORDER BY sim DESC
Funciona porque las columnas de salida se pueden utilizar en GROUP BY y ORDER BY . Detalles:
Caso de prueba
Realicé una prueba rápida en mi antiguo servidor de prueba para verificar mis reclamos.
PostgreSQL 9.1.4. Tiempos tomados con EXPLAIN ANALYZE (el mejor de cinco).
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 show_limit();
SELECT set_limit(0.8); -- fewer hits and faster with higher limit
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 de GIN utilizado, 64 hits: tiempo de ejecución total: 484.022 ms
Índice GIST utilizado, 64 aciertos: tiempo de ejecución total: 248.772 ms
Consulta antigua:
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 hits: tiempo de ejecución total: 6345.833 ms
Índice GIST no utilizado, 64 aciertos: tiempo total de ejecución: 6335.975 ms
De lo contrario resultados idénticos. El consejo es bueno. Y esto es solo para 1000 filas .
GIN o GiST?
GIN a menudo proporciona un rendimiento de lectura superior:
Pero no en este caso particular:
Esto puede implementarse de manera bastante eficiente mediante índices GiST, pero no mediante índices GIN.