Para pesquisar com eficiência usando a distância levenshtein, você precisa de um índice eficiente e especializado, como um bk-tree . Infelizmente, nenhum sistema de banco de dados que eu conheça, incluindo MySQL, implementa índices bk-tree. Isso é ainda mais complicado se você estiver procurando por pesquisa de texto completo, em vez de apenas um único termo por linha. De imediato, não consigo pensar em nenhuma maneira de fazer a indexação de texto completo de uma maneira que permita a pesquisa com base na distância levenshtein.