Re: Query taking long with levenshtein function

On Feb 28, 2023, at 6:31 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

Teju Jakkidi vlogs <teja(dot)jakkidi05(at)gmail(dot)com> writes:

We have a query as below which uses the levenshtein function to compare

strings.

SELECT "name", levenshtein("name",'some string') as p FROM table1

where levenshtein("name",'some string')   <= 2 order by p desc;

We have a GIST index built on top of this table as below:

CREATE INDEX gist_idx ON table1 USING GIST("name");

AFAIK, that index is completely useless for this query.  I don't

really see a good way to index it either --- "levenshtein distance

less than X" seems like a not very tractable requirement.  Can

you formulate your matching rules some other way?

Can you use trigram similarity instead? That has index support...

Reference links:

F.35. pg_trgm


postgresql.org

Optimize PostgreSQL query with levenshtein() function


stackoverflow.com

Since they are so similar, I also wonder how difficult it would be to take the pg_trgm module and modify it to work with levenshtein() instead....

Regards,

Ed