1

I have kind of a special problem using a levenshtein algorithm in MySql. But I don't think that it's special for levenshtein. This query:

SELECT *,levenshtein(word,'Facbook') FROM Words WHERE length(word) between 6 and 8 and levenshtein(word,'Facbook') <=1 is pretty slow with around 5000 rows it takes about 1s.

But on the other hand this one:

SELECT *,levenshtein(word,'Facbook') FROM Words WHERE length(word) between 6 and 8 is kind of fast (0.02s).

The explain statments looks nearly identical only the number of rows differs a single bit.

The explain table for the first query:

 | id select_type table type possible_keys key key_len ref rows Extra                    |
 ----------------------------------------------------------------------------------------
 | 1  SIMPLE      Words index NULL         word   302  NULL 4711 Using where; Using index|

The second explain:

 | id  select_type table type   possible_keys key key_len ref rows Extra                  |
 ------------------------------------------------------------------------------------------
 | 1   SIMPLE      Words index  NULL          word 302    NULL 4621 Using where; Using index

Btw I have an index on the word column. Now the question is why is the first one so much slower? It only has to use the second query and "print out" only the words that matching the second where clause: levenshtein(word,'Facbook') <=1 Right?

Strange: I used PHPMyAdmin to check the time and now I used a simple php file to send the query and now both queries took 1s. So maybe this question is totally bullshit...

  • If you are trying to implement a poor man's fuzzy fulltext search with mysql and levensthein - you're gonna have a baaaaaad time. Try elastic search or something. – Falcon Mar 18 '15 at 9:48
  • Well I had no idea that these simple looking queries are so hard :D I don't want a perfect solution just want to learn sth doing it by myself. Thanks for your ideas. – Wikunia Mar 18 '15 at 9:54
1

Here's the difference between the two statements:

The first statement calls the levenshtein function only on the retrieved resultset.

The second statement calls the levenshtein and the length function as a so called "predicate" for every row in the table to retrieve the resultset. Even if levenshtein is only evaluated if the first condition is true, then there's the overhead of doing additional comparisons.

Thus, the second query is naturally slower.

IMHO this is a CPU bound problem. To make this query faster, either supply more predicates that can be evaluated (means: add more restrictions to the where clause), add more CPU power and try parallel selects (if mysql supports that).

  • But why? I mean is there a way to say mysql that length is much faster than levenshtein? Cause than it only has to calculate length and because of the and between the wheres the levenshtein function hasn't to be calculated on every row. – Wikunia Mar 18 '15 at 9:39
  • Depends on the mysql optimizer. Try this: Is it faster? – Falcon Mar 18 '15 at 9:40
  • SELECT * FROM (SELECT *,levenshtein(word,'Facbook') as dist FROM Words WHERE length(word) between 6 and 8) WHERE dist <= 1 – Falcon Mar 18 '15 at 9:41
  • okay is there a way to say: Do this part of the where first? – Wikunia Mar 18 '15 at 9:41
  • See previous comment. And no, there's no nice way to express that in SQL, as it is a declarative language. It depends on the database engine. – Falcon Mar 18 '15 at 9:42
0

A likely answer...

The first query (WHERE LENGTH...) finds the rows with the give length, then fetches *,levenshtein(word,'Facbook') for those words.

The second query probably evaluates the entire WHERE LENGTH... AND LEVEN... for each word. Please provide EXPLAIN SELECT ....

That is, the second query has a lot more calls to levenshtein().

Here's a possible workaround:

SELECT  *, levenshtein(word,'Facbook') AS dist
    FROM  Words
    WHERE  length(word) between 6 AND 8
    HAVING  dist <= 1;
  • I've added the explain table. Unfortunately your having takes 1s as well. – Wikunia Mar 18 '15 at 8:23
  • Of course it takes 1s as well, it's the same semantics just expressed differently. – Falcon Mar 18 '15 at 9:28
0

I found a solution for this special levenshtein problem using this idea:

http://norvig.com/spell-correct.html

In short: Don't check the levenshtein distance for every word in your table. Instead reverse the process. Start with the word 'Facbook' and generate all words that have a levenshtein distance of 1. Then use sth. like

SELECT word FROM `Words` where word in ('afacbook','aacbook','acbook',...) 

On this special example I need only about 0.002s.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.