Vraag Soortgelijke strings vinden met PostgreSQL snel


Ik moet een rangorde maken van vergelijkbare strings in een tabel.

Ik heb de volgende tabel

create table names (
name character varying(255)
);

Momenteel gebruik ik pg_trgm module die de similarity functie, maar ik heb een probleem met de efficiëntie. Ik heb een index gemaakt zoals de De handleiding van Postgres suggereert:

CREATE INDEX trgm_idx ON names USING gist (name gist_trgm_ops);

en ik voer de volgende query uit:

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;

De zoekopdracht werkt, maar is erg traag als je honderden namen hebt. Bovendien ben ik misschien een beetje SQL vergeten, maar ik begrijp niet waarom ik de voorwaarde niet kan gebruiken and sim > .8 zonder een "column sim does not exist" -fout te krijgen.

Ik wil graag een hint om de query sneller te maken.


21
2018-06-28 17:10


oorsprong


antwoorden:


Bijwerken: In postgres 9.6 (beta vanaf het schrijven) de functies set_limit() en show_limit() worden vervangen door de configuratieparameter pg_trgm.similarity_threshold (samen met verschillende andere verbeteringen aan de module pg_trgm). De functies zijn verouderd, maar werken nog steeds.

Ook zijn de prestaties van de GIN- en GiST-indexen op verschillende manieren verbeterd sinds Postgres 9.1.


Gebruik set_limit() en de % operator in plaats daarvan. Beide worden geleverd door de pg_trgm module.

Zoals je het hebt, moet de overeenkomst tussen elk element en elk ander element van de tabel worden berekend (bijna een kruising). Als uw tabel 1000 rijen heeft, is dat 1.000.000 (!) Berekende overeenkomsten, voor die kunnen worden gecontroleerd tegen de conditie en gesorteerd. Proberen:

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;

Moet sneller zijn in orden van grootte, maar het zal nog steeds langzaam zijn.

Misschien wilt u het aantal mogelijke paren beperken door meer randvoorwaarden te introduceren (zoals het matchen van de eerste letter) voor cross joining (en ondersteun dat met een bijpassende functionele index). De uitvoering van een cross join verslechtert kwadratisch met het groeiende aantal records - O (N²).


Wat betreft uw subsidiaire vraag:

WHERE ... sim > 0.8

Werkt niet omdat jij kan niet refereer naar de output kolommen in WHERE of HAVING clausules. Dat is volgens de (een beetje verwarrende, toegekende) SQL-standaard - die nogal losjes wordt afgehandeld door bepaalde andere RDBMS.

Aan de andere kant:

ORDER BY sim DESC

Werken omdat uitvoer kolommen kan worden gebruikt in GROUP BY en ORDER BY. Details:


54
2018-06-28 17:36