Öncelikle şunu sorayım?

Sorguyu mysql üzerinde mi, elastic üzerinde mi yoksa, casandra, mongo gibi diğer nosql dbler de mi yapacaksınız?

Levenshtein algoritması çok kapsamlı bir algoritmadır. Bunu php üzerinde bir fonksiyon ile yapacaksanız performans düşer. Mysql üzerinde yapacaksanız da data'nın ne kadar çok olduğuna bağlı. Özellikle elasticsearch üzerinde bu konuda daha sağlıklı çözümler bulunuyor.

Geliştirme ortamına göre çözüm düşünelim.