Optimalisatie van MySQL-zoekopdrachten met likes en jokertekens

Hoe lang zijn je snaren?

Als ze relatief kort zijn (bijv. Engelse woorden; avg_len=5) en je hebt databaseopslag over, probeer dan deze aanpak:

• Neem voor elk woord dat u in de tabel wilt opslaan elk mogelijk achtervoegsel van dat woord. Met andere woorden, je blijft het eerste teken strippen totdat er niets meer over is. Bijvoorbeeld het woord value geeft:
  • value
  • alue
  • lue
  • ue
  • e
• Bewaar elk van deze achtervoegsels in de database.
• Je kunt nu naar substrings zoeken met LIKE 'alu%' (die 'alu' zal vinden als onderdeel van 'waarde').

Door alle achtervoegsels op te slaan, heeft u de noodzaak voor het leidende jokerteken verwijderd (waardoor een index kan worden gebruikt voor snel opzoeken), ten koste van opslagruimte.

Opslagkosten

Het aantal tekens dat nodig is om een ​​woord op te slaan wordt word_len*word_len / 2 , d.w.z. kwadratisch in de woordlengte, per woord. Hier is de toenamefactor voor verschillende woordgroottes:

• 3-letterwoord:(3*3/2) / 3 = 1.5
• Woord van 5 letters:(5*5/2) / 5 = 2.5
• Woord van zeven letters:(7*7/2) / 7 = 3.5
• 12-letterig woord:(12*12/2) / 12 = 6

Het aantal rijen dat nodig is om een ​​woord op te slaan, neemt toe van 1 tot word_len . Houd rekening met deze overhead. Extra kolommen moeten tot een minimum worden beperkt om te voorkomen dat er grote hoeveelheden overtollige gegevens worden opgeslagen. Een paginanummer waarop het woord oorspronkelijk werd gevonden, zou bijvoorbeeld prima moeten zijn (denk aan unsigned smallint), maar uitgebreide metadata over het woord moet per woord in een aparte tabel worden opgeslagen, in plaats van voor elk achtervoegsel.

Overwegingen

Er is een afweging waarbij we 'woorden' (of fragmenten) splitsen. Als voorbeeld uit de praktijk:wat doen we met koppeltekens? Slaan we het bijvoeglijk naamwoord five-letter op? als één of twee woorden?

De afweging is als volgt:

• Alles dat is opgebroken, kan niet als een enkel element worden gevonden. Als we five opslaan en letter afzonderlijk zoeken naar five-letter of fiveletter zal mislukken.
• Alles wat niet is opgebroken kost meer opslagruimte. Onthoud dat de opslagvereiste kwadratisch toeneemt in de woordlengte.

Voor het gemak wil je misschien het koppelteken verwijderen en fiveletter . opslaan . Het woord kan nu gevonden worden door te zoeken op five , letter , en fiveletter . (Als u ook koppeltekens uit een zoekopdracht verwijdert, kunnen gebruikers five-letter nog steeds vinden .)

Ten slotte zijn er manieren om suffix-arrays op te slaan die niet veel overhead met zich meebrengen, maar ik weet nog niet zeker of ze goed vertalen naar databases.