Ett tillvägagångssätt är att titta på Levenshtein-avståndet mellan söktermen och sökordslistan. Det finns några exempel på hur man implementerar detta i MySQL, t.ex. HÄR
Eftersom du har en så stor katalog måste du först titta på att implementera ett filter (kanske baserat på en "LIKE"-uppslagning) så att du inte mäter avståndet för alla 1M rader.
Om du rangordnar resultat efter avstånd bör du kunna sortera resultat efter relevans för sökningen.