mySQL:Verwendung der Levenshtein-Distanz, um Duplikate in 20.000 Zeilen zu finden

Ich kenne mindestens eine Optimierung, die die Laufzeit halbieren könnte:

AND a.id < b.id

Dies verhindert, dass Sie a=1, b=2 testen, wenn Sie bereits a=2, b=1 getestet haben.

Es wird zwar immer noch O(n^2) sein, aber ich sehe nicht, wie du viel dagegen tun kannst.