mySQL:Brug af Levenshtein-afstand til at finde dubletter i 20.000 rækker

Jeg kender mindst én optimering, der kan halvere køretiden:

AND a.id < b.id

Dette forhindrer dig i at teste a=1, b=2, når du allerede har testet a=2, b=1.

Det vil dog stadig være O(n^2), men jeg kan ikke se, hvordan du kan gøre meget ved det.