Ако сте обвързани само с MySQL, няма лесно решение.
Обикновено това се решава с помощта на специализирано индексиране на ngram за бързо филтриране на търсене на кандидати и след това изчисляване на levensthein само за около 10-50 кандидата, което е по-бързо от изчисляването на levensthein за всички двойки.
Специализирани пълнотекстови търсачки като Solr/Lucene имат това вградено.
PostgreSQL има модул pg_trgm contrib (http://www.postgresql.org/docs/9.0/static/pgtrgm.html), който работи като чар.
Можете дори да симулирате това в MySQL, като използвате пълнотекстово индексиране, но трябва да събирате думи от всичките си документи, да ги конвертирате в ngram, да създавате пълнотекстови индекси върху тях и да ги хакнете заедно за бързо търсене. Което носи всякакви проблеми с излишъка, синхронизирането...не си струва времето.
