El problema de la falta de ortografía es difícil, si no imposible, de resolver bien en MySQL puro.
El FULLTEXT de varias columnas la búsqueda no es tan mala.
Su consulta se verá así...
SELECT column, column
FROM table
WHERE MATCH(Company, FirstName, LastName, whatever, whatever)
AGAINST('search terms' IN NATURAL LANGUAGE MODE)
Producirá un montón de resultados, ordenados por lo que MySQL supone que es el primer resultado más probable. Las conjeturas de MySQL no son muy buenas, pero por lo general son adecuadas.
Necesitarás un FULLTEXT índice que coincide con la lista de columnas en su MATCH() cláusula. La creación de ese índice se ve así.
ALTER TABLE book
ADD FULLTEXT INDEX Fulltext_search_index_1
(Company, FirstName, LastName, whatever, whatever);
A pesar de los comentarios en su pregunta, solo necesita un índice para el grupo de columnas que buscará.
20 000 filas no supondrán una gran carga para ningún hardware de servidor reciente.
Error ortográfico:podría probar SOUNDEX() , pero es un algoritmo de principios del siglo XX diseñado por Bell System para buscar nombres de personas en inglés estadounidense. Está diseñado para obtener muchos resultados falsos positivos, y realmente es más tonto que un balde de rocas.
Si realmente necesita una corrección ortográfica, es posible que deba investigar a Sphinx.
