Un approccio consiste nell'esaminare la distanza di Levenshtein tra il termine di ricerca e l'elenco delle parole chiave. Ci sono alcuni esempi tranquilli di come implementarlo in MySQL, ad es. QUI
Poiché disponi di un catalogo così ampio, dovrai prima esaminare l'implementazione di un filtro (magari basato su una ricerca "MI PIACE") in modo da non misurare la distanza per tutte le righe da 1 milione.
Se classifichi i risultati in base alla distanza, dovresti essere in grado di ordinare i risultati in base alla pertinenza alla ricerca.
