mySQL:utilizzo della distanza di Levenshtein per trovare duplicati in 20.000 righe

Conosco almeno un'ottimizzazione che potrebbe dimezzare il tempo di esecuzione:

AND a.id < b.id

Ciò ti impedisce di testare a=1, b=2 quando hai già testato a=2, b=1.

Sarà comunque O(n^2), ma non vedo come tu possa fare molto al riguardo.