Optimierung der MySQL-Suche mit Likes und Wildcards

Wie lang sind deine Saiten?

Wenn sie relativ kurz sind (z. B. englische Wörter; avg_len=5) und Sie über ausreichend Datenbankspeicher verfügen, versuchen Sie es mit diesem Ansatz:

• Nehmen Sie für jedes Wort, das Sie in der Tabelle speichern möchten, stattdessen alle möglichen Suffixe dieses Wortes. Mit anderen Worten, Sie entfernen das erste Zeichen so lange, bis nichts mehr übrig ist. Zum Beispiel das Wort value ergibt:
  • value
  • alue
  • lue
  • ue
  • e
• Speichern Sie jeden dieser Suffixe in der Datenbank.
• Sie können jetzt mit LIKE 'alu%' nach Teilstrings suchen (was 'alu' als Teil von 'value' findet).

Indem Sie alle Suffixe speichern, haben Sie die Notwendigkeit für den führenden Platzhalter beseitigt (wodurch ein Index für eine schnelle Suche verwendet werden kann), auf Kosten des Speicherplatzes.

Speicherkosten

Die Anzahl der Zeichen, die zum Speichern eines Wortes erforderlich sind, wird zu word_len*word_len / 2 , d. h. quadratisch in der Wortlänge, auf einer Pro-Wort-Basis. Hier ist der Erhöhungsfaktor für verschiedene Wortgrößen:

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

Die Anzahl der zum Speichern eines Wortes erforderlichen Zeilen erhöht sich von 1 auf word_len . Denken Sie an diesen Mehraufwand. Zusätzliche Spalten sollten auf ein Minimum beschränkt werden, um das Speichern großer Mengen redundanter Daten zu vermeiden. Zum Beispiel sollte eine Seitennummer, auf der das Wort ursprünglich gefunden wurde, in Ordnung sein (denken Sie an unsigned smallint), aber umfangreiche Metadaten zu dem Wort sollten in einer separaten Tabelle pro Wort gespeichert werden, anstatt für jedes Suffix.

Überlegungen

Es gibt einen Kompromiss darin, wo wir „Wörter“ (oder Fragmente) aufteilen. Als Beispiel aus der Praxis:Was machen wir mit Bindestrichen? Speichern wir das Adjektiv five-letter als ein Wort oder zwei?

Der Kompromiss ist wie folgt:

• Alles, was zerlegt ist, kann nicht als einzelnes Element gefunden werden. Wenn wir five speichern und letter getrennt nach five-letter suchen oder fiveletter wird scheitern.
• Alles, was nicht ist Aufgebrochen nimmt mehr Speicherplatz in Anspruch. Denken Sie daran, dass der Speicherbedarf quadratisch mit der Wortlänge zunimmt.

Der Einfachheit halber möchten Sie vielleicht den Bindestrich entfernen und fiveletter speichern . Das Wort kann nun durch die Suche five gefunden werden , letter , und fiveletter . (Wenn Sie auch Bindestriche aus einer beliebigen Suchanfrage entfernen, können Benutzer five-letter weiterhin erfolgreich finden .)

Schließlich gibt es Möglichkeiten, Suffix-Arrays zu speichern, die nicht viel Overhead verursachen, aber ich bin mir noch nicht sicher, ob sie sich gut in Datenbanken übersetzen lassen.