mySQL:Używanie odległości Levenshteina do znajdowania duplikatów w 20 000 wierszy

Znam co najmniej jedną optymalizację, która może skrócić czas działania o połowę:

AND a.id < b.id

Zapobiega to testowaniu a=1, b=2 po przetestowaniu a=2, b=1.

Jednak nadal będzie O(n^2), ale nie widzę, jak możesz coś z tym zrobić.