Jeśli jesteś przywiązany tylko do MySQL, nie ma łatwego rozwiązania.
Zwykle jest to rozwiązywane za pomocą wyspecjalizowanego indeksowania ngramów do szybkiego filtrowania wyszukiwania kandydatów, a następnie obliczania levensthein tylko dla 10-50 kandydatów, co jest szybsze niż obliczanie levensthein dla wszystkich par.
Wyspecjalizowane wyszukiwarki pełnotekstowe, takie jak Solr/Lucene, mają to wbudowane.
PostgreSQL posiada moduł contrib pg_trgm (http://www.postgresql.org/docs/9.0/static/pgtrgm.html), który działa jak czar.
Możesz nawet symulować to w MySQL, używając indeksowania pełnotekstowego, ale musisz zebrać słowa ze wszystkich dokumentów, przekonwertować je na ngramy, utworzyć na nich indeksy pełnotekstowe i zhakować je wszystkie razem, aby szybko je wyszukać. Co powoduje różnego rodzaju problemy z redundancją, synchronizacją… niewarte twojego czasu.
