How to optimize this Levenshtein distance calculation

Question

Table a has around 8,000 rows and table b has around 250,000 rows. Without the levenshtein function the query takes just under 2 seconds. With the function included it is taking about 25 minutes.

SELECT
      *
   FROM
      library a,
      classifications b
   WHERE  
      a.`release_year` = b.`year`
      AND a.`id` IS NULL
      AND levenshtein_ratio(a.title, b.title) > 82

Obviously I have no idea of what levenshtein algorithm you're using, but you could try looking into optimizing you levenshtein distance [calculations](http://stackoverflow.com/q/4057513/781965) and [calling method](http://stackoverflow.com/a/10371198/781965) — Jeff, Jan 31 '13 at 01:16

score 1 · Accepted Answer · answered Jan 31 '13 at 00:44

I'm assuming that levenshtein_ratio is a function that you wrote (or maybe included from somewhere else). If so, the database server would not be able to optimize that in the normal sense of using an index. So it means that it simply needs to call it for each record that results from the other join conditions. With an inner join, that could be an extremely large number with those table sizes (a maximum of 8000*250000 = 2 billion). You can check the total number of times it would need to be called with this:

SELECT
      count(*)
   FROM
      library a,
      classifications b
   WHERE  
      a.`release_year` = b.`year`
      AND a.`id` IS NULL

That is an explanation of why it is slow (not really an answer to the question of how to optimize it). To optimize it, you likely need to add additional limiting factors to the join condition to reduce the number of calls to the user-defined function.

Mickle Foretic · Answer 2 · 2013-01-31T01:04:18.457

You are giving too little information to actually help you.

1) My first guess would be to try to create other WHERE conditions that reduce the amount of rows to be scanned.

2) If that is not possible...Given that the titles from table library and classifications are known, one idea would be to create a table where all the data is already calculated like this:

TABLE levenshtein_ratio
id_table_library
id_table_classifications
precalculated_levenshtein_ratio

so you would populate the table using this query:

insert into levenshtein_ratio select a.id, b.id, levenshtein_ratio(a.title, b.title) from library, classifications

and then your query would be:

    SELECT
          *
       FROM
          library a LEFT JOIN 
          classifications b ON a.`release_year` = b.`year`

LEFT JOIN levenshtein_ratio c ON c.id_table_library = a.id AND c.id_table_classifications = b.id
       WHERE  
          a.`id` IS NULL
          AND precalculated_levenshtein_ratio > 82

this query will probably then no more than the original 2 secs.

The problem with this solution is the fact that the data in tables a and b can change, so you will need to create a trigger to keep it updated.

score 0 · Answer 3 · answered Jan 31 '13 at 00:49

Change your query to use proper joins (syntax has been around since 1996).

Also, all your levensrein condition may be moved into the join condition, which should give you a performance benefit:

SELECT *
FROM library a
JOIN classifications b
    ON a.`release_year` = b.`year`
    AND levenshtein_ratio(a.title, b.title) > 82
WHERE a.`id` IS NULL

Also, make sure there's an index on b.year:

create index b_year on b(year);

How to optimize this Levenshtein distance calculation

3 Answers3

Linked