Pokud jste vázáni pouze na MySQL, není snadné řešení.
Obvykle se to řeší pomocí specializovaného indexování ngramů pro rychlé filtrování kandidátů a následného výpočtu levenstheinu pouze pro 10-50 kandidátů, což je rychlejší než výpočet levenstheinu pro všechny páry.
Specializované fulltextové vyhledávače jako Solr/Lucene to mají zabudované.
PostgreSQL má modul pg_trgm contrib (http://www.postgresql.org/docs/9.0/static/pgtrgm.html), který funguje jako kouzlo.
Můžete to dokonce simulovat v MySQL pomocí fulltextového indexování, ale musíte sbírat slova ze všech svých dokumentů, převádět je na ngramy, vytvářet na nich fulltextové indexy a hackovat je všechna dohromady pro rychlé vyhledávání. Což přináší nejrůznější problémy s redundancí, synchronizací...nestojí to za váš čas.