Optimering af MySQL-søgning ved hjælp af like og jokertegn

Hvor lange er dine strenge?

Hvis de er relativt korte (f.eks. engelske ord; avg_len=5), og du har databaselager til overs, så prøv denne fremgangsmåde:

• For hvert ord, du vil gemme i tabellen, skal du i stedet tage alle mulige suffiks af det ord. Med andre ord bliver du ved med at strippe det første tegn, indtil der ikke er noget tilbage. For eksempel ordet value giver:
  • value
  • alue
  • lue
  • ue
  • e
• Gem hver af disse suffikser i databasen.
• Du kan nu søge efter understrenge ved at bruge LIKE 'alu%' (som vil finde 'alu' som en del af 'værdi').

Ved at gemme alle suffikser har du fjernet behovet for det førende jokertegn (hvilket gør det muligt at bruge et indeks til hurtigt opslag) på bekostning af lagerplads.

Lagringsomkostninger

Antallet af tegn, der kræves for at gemme et ord, bliver word_len*word_len / 2 , dvs. kvadratisk i ordlængden, på en per-ord basis. Her er stigningsfaktoren for forskellige ordstørrelser:

• 3-bogstavsord:(3*3/2) / 3 = 1.5
• 5-bogstavsord:(5*5/2) / 5 = 2.5
• 7-bogstavsord:(7*7/2) / 7 = 3.5
• 12-bogstavsord:(12*12/2) / 12 = 6

Antallet af rækker, der kræves for at gemme et ord, stiger fra 1 til word_len . Vær opmærksom på dette overhead. Yderligere kolonner bør holdes på et minimum for at undgå lagring af store mængder overflødige data. For eksempel burde et sidetal, som ordet oprindeligt blev fundet på, være fint (tænk usigneret smallint), men omfattende metadata om ordet skal gemmes i en separat tabel pr. ord i stedet for for hvert suffiks.

Overvejelser

Der er en afvejning i, hvor vi deler 'ord' (eller fragmenter). Som et eksempel fra den virkelige verden:hvad gør vi med bindestreger? Gemmer vi adjektivet five-letter som et ord eller to?

Afvejningen er som følger:

• Alt, der er opdelt, kan ikke findes som et enkelt element. Hvis vi gemmer five og letter separat, søger efter five-letter eller five-letter vil mislykkes.
• Alt, der ikke er brudt op vil tage mere lagerplads. Husk, at lagerkravet øges kvadratisk i ordlængden.

For nemheds skyld vil du måske fjerne bindestregen og gemme five-letter . Ordet kan nu findes ved at søge på five , letter og five-letter . (Hvis du også fjerner bindestreger fra enhver søgeforespørgsel, kan brugerne stadig finde five-letter .)

Endelig er der måder at gemme suffiks-arrays på, som ikke medfører meget overhead, men jeg er endnu ikke sikker på, om de oversætter godt til databaser.