mySQL:Använd Levenshtein-avstånd för att hitta dubbletter i 20 000 rader

Jag känner till minst en optimering som kan halvera körtiden:

AND a.id < b.id

Detta hindrar dig från att testa a=1, b=2 när du redan har testat a=2, b=1.

Det kommer fortfarande att vara O(n^2), men jag kan inte se hur du kan göra så mycket åt det.