MySQLのみに縛られている場合、簡単な解決策はありません。
通常、これは、高速候補ルックアップフィルタリング用の特殊なngramインデックスを使用して解決され、10〜50の候補に対してのみlevenstheinを計算します。これは、すべてのペアのlevenstheinを計算するよりも高速です。
Solr/Luceneのような特殊な全文検索エンジンにはこれが組み込まれています。
PostgreSQLには、チャームのように機能するpg_trgm contribモジュール（http://www.postgresql.org/docs/9.0/static/pgtrgm.html）があります。
全文索引を使用してMySQLでこれをシミュレートすることもできますが、すべてのドキュメントから単語を収集してそれらをngramに変換し、それらに全文索引を作成し、それらをすべて一緒にハックして高速検索を行う必要があります。これは、冗長性、同期に関するあらゆる種類の問題をもたらします...あなたの時間の価値はありません。