mySQL:Levenshtein-afstand gebruiken om duplicaten in 20.000 rijen te vinden

Ik ken ten minste één optimalisatie die de looptijd zou kunnen halveren:

AND a.id < b.id

Dit voorkomt dat u a=1, b=2 test als u a=2, b=1 al heeft getest.

Het wordt echter nog steeds O(n^2), maar ik zie niet in hoe je daar veel aan kunt doen.