En tilgang er at se på Levenshtein-afstanden mellem søgeordet og søgeordslisten. Der er stille et par eksempler på, hvordan man implementerer dette i MySQL, f.eks. HER
Fordi du har så stort et katalog, skal du først se på implementeringen af et filter (måske baseret på et 'LIKE'-opslag), så du ikke måler afstanden for alle 1M rækker.
Hvis du rangerer resultater efter afstand, bør du være i stand til at sortere resultater efter relevans for søgningen.