Wenn Sie nur an MySQL gebunden sind, gibt es keine einfache Lösung.
Normalerweise wird dies gelöst, indem eine spezialisierte ngram-Indizierung für eine schnelle Filterung der Kandidatensuche verwendet wird und dann Levensthein nur für etwa 10-50 Kandidaten berechnet wird, was schneller ist als die Berechnung von Levensthein für alle Paare.
Spezialisierte Volltextsuchmaschinen wie Solr/Lucene haben dies eingebaut.
PostgreSQL hat das Contrib-Modul pg_trgm (http://www.postgresql.org/docs/9.0/static/pgtrgm.html), das wie ein Zauber funktioniert.
Sie können dies sogar in MySQL mit Volltextindizierung simulieren, aber Sie müssen Wörter aus all Ihren Dokumenten sammeln, sie in Ngrams konvertieren, Volltextindizes darauf erstellen und sie alle zusammen hacken, um sie schnell nachschlagen zu können. Das bringt alle möglichen Probleme mit Redundanz, Synchronisierung ... Ihre Zeit nicht wert.
