Einführung in Full-Text-Suche in Datenbanken

Warum man LIKE % vermeiden sollten

| Autor / Redakteur: Denis Rosa * / Stephan Augsten

Der invertierte Index umfasst die in einer Datenbank gespeicherten Wörter und ihr Vorkommen.
Der invertierte Index umfasst die in einer Datenbank gespeicherten Wörter und ihr Vorkommen. (Bild: Couchbase)

Im Datenbank-Umfeld sollte ein gut implementierter Suchlauf im Wesentlichen schnell und sachdienlich sein; Eine Datenbankabfrage „Like %“ ist keines von beidem. In diesem Beitrag betrachten wir, warum das so ist und wie es besser geht.

Die Suchfunktion war wohl eine der meist unterschätzten Funktionen in bisherigen Anwendungen. In letzter Zeit hat sie allerdings all die Aufmerksamkeit erhalten, die sie verdient, denn wir haben endlich verstanden, wie sie Umsätze steigern oder das Verhalten und das Engagement von Nutzern prägen kann. Eine „Like %“-Abfrage wird diesen Ansprüchen allerdings aus mehreren Gründen nicht gerecht.

Das Problem mit der Geschwindigkeit

Nimmt man an, man möchten einen Suchlauf für einen Film anhand seines Titels starten. Eine unbedarfte SQL-Abfrage nach allen „Star Trek“-Filmen würde wie folgt aussehen:

Select * from Movies where title like “Star Trek%”

Die Abfrage führt standardmäßig einen Full Table Scan durch und versucht, diesen Begriff mit allen Zeilen abzugleichen. Sie kann aber mithilfe eines Index‘ optimiert werden, was höchstwahrscheinlich zu einer B-Baumstruktur führt. Daher würden selbst Suchläufe wie der folgende den Index zum Teil noch nutzen.

Select * from Movies where title like “Star%Trek”

Select * from Movies where title like “St%Trek”

Was aber, wenn der Nutzer ein großer Fan von Batman ist und beschließt, nach dem Begriff „Dark Knight” zu suchen? Dem vorherigen Beispiel zufolge würde die Abfrage wie folgt aussehen:

Select * from Movies where title like “Dark Knight%”

Obige Suche würde keine Ergebnisse bringen, denn der wirkliche Name des Films lautet “The Dark Knight Rises”. Um dieses Problem zu lösen, fügt man am Anfang unseres Suchbegriffs eine Wildcard an:

Select * from Movies where title like “%Dark Knight%”

Obige Abfrage wird zu einem Ergebnis wie “The Dark Knight Rises” führen, aber es wird den Index nicht mehr nutzen und im großen Maßstab definitiv nicht gut funktionieren. Like % „versteht” den Inhalt Ihres Feldes nicht. Es behandelt einen Text vielmehr wie ein einzelnes Element. Das macht es für alles, was über irgendeine Grundstruktur verfügt, nicht zur besten Option. Eine mögliche Lösung ist die Nutzung von MATCH, das in einigen Datenbanken auch als langsam gilt.

Das Problem mit der Relevanz

Was, wenn man auch nach einer Zusammenfassung des Films suchen möchten? Eine naive Lösung wäre es, der Suche lediglich ein neues Feld anzufügen:

Select * from Movies where title like “%Dark Knight%” or overview like “%Dark Knight%”+

Diese Vorgehensweise führt zu einem neuen Problem: Alle Filme mit der Nennung „Dark Knight“ in der Zusammenfassung haben die gleiche Relevanz wie Filme mit der Nennung im Titel, und die Reihenfolge der Ergebnisse ist völlig unsicher.

Ein gängiger Fehler ist es zu denken, dass UNION DISTINCT dieses Problem lösen könnte. Allerdings führen die meisten Abfrageplaner jeden Block der Union gleichzeitig aus, was wieder die Reihenfolge/Relevanz durcheinanderbringt.

Versucht man einfacher SQL wirklich eine Art Relevanz zu implementieren, bestünde eine simple Lösung darin, zwei separate Abfragen auszuführen und das Ergebnis der einen an die andere anzuhängen. Natürlich ist diese Strategie alles andere als optimal, den man müsste Duplizierungen immer noch manuell nachbearbeiten.

Obige Beispiele belegen eine der unausgesprochenen Wahrheiten über Suchläufe: Die wahre Herausforderung bei der Suche besteht nicht darin, die Matches zu finden, sondern in der Frage, wie man sie sortiert. Schließlich ist das Abgleichen eines Textes eine sehr unkomplizierte Aufgabe; ihm den richtigen Wert zuzuordnen, ist etwas, was mit großer Sorgfalt vorgenommen werden sollte.

Volltextsuche ist die Rettung in der Not!

Der invertierte Index umfasst die in einer Datenbank gespeicherten Wörter und ihr Vorkommen.
Der invertierte Index umfasst die in einer Datenbank gespeicherten Wörter und ihr Vorkommen. (Bild: Couchbase)

Um eine Datenbank mithilfe von Fulltext-Suche abzufragen, muss man zunächst einen invertierten Index erstellen. Dieser Index ist, grob gesagt, eine Aufstellung von Wörtern und ihrem Vorkommen. Hat man den hier dargestellten Index zur Hand, ist die Suche nach einem Wort eine einfache Sache, weil man ganz leicht nur die Dokumente bekommt, die den Zielbegriff enthalten.

Man sollte nicht vergessen, dass man während der Erstellung des invertierten Indexes Sätze in eine Reihe von Wörtern umgewandelt hat, so dass keine Wildcards nötig sind, da man die Zielbegriffe direkt mit dem invertierten Index vergleichen kann. Dennoch läuft hier selbst die Verwendung von Wildcards (Bsp.: *star*) in großem Maßstab noch schneller, denn man muss nur den Index durchgehen, um alle Matches zu finden, anstatt alle Dokumente in Ihrer Datenbank zu scannen.

Es gibt noch weitere Funktionen wie Dictionaries, Stemming, Analyseprogramme, Tokenizern und Synonymen. Die würden diesen Artikel allerdings überfrachten.

Die Lösung für Relevanz

Die Strategie zur Anwendung eines relevanten Suchergebnisses kann in Abhängigkeit des Bereichs variieren. Im Allgemeinen kann die Relevanz auf viele verschiedene Arten beeinflusst werden. Die einfachste davon heißt Boosting. Das ist nur eine einfache Möglichkeit, die Field Matches eine Gewichtung zuzuordnen:

Abfrage:

Titel:”Star Trek”^2 | Zusammenfassung:”Star Trek”

Im Beispiel oben ist der Wert eines Matches für „Star Trek” im Titel doppelt so hoch wie ein Match in Zusammenfassung eins. Im Prinzip ist das die Art und Weise, die man für eine Sortierung Ihrer Suchergebnisse empfehlen kann.

Warum nutzt dann nicht jeder die Volltextsuche?

Für die Fulltext-Suche müsste man normalerweise eine völlig neue Infrastruktur aufbauen, neue Abhängigkeiten hinzufügen, mehrere Indizes erstellen und dann alle Dokumentenänderungen zu einem externen System wie Elastic Search oder Solr verschieben, selbst wenn man nur eine einfache Suche implementieren möchten. Deshalb neigen Entwickler dazu, diesen enormen Arbeitsaufwand solange zu vermeiden, bis er unbedingt notwendig wird.

Mit dem Tool Bleve lässt sich recht einfach ein neuer Datenbank-Index erstellen.
Mit dem Tool Bleve lässt sich recht einfach ein neuer Datenbank-Index erstellen. (Bild: Couchbase)

Das ist einer der Gründe, warum erste NoSQLD-Datenbanken Tools wie Bleve integriert haben, denn dadurch muss der Programmierer wie im Bild zu sehen nur einen neuen Index in der Web-Konsole erstellen. Dann ist man automatisch in der Lage, Volltextsuchen mithilfe der standardmäßigen Couchbase SDK durchzuführen:

String indexName = "movies_index";

PhraseQuery query = SearchQuery.phrase("Star Trek");

SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(

   new SearchQuery(indexName, query).highlight().limit(20));

Die meisten relationalen Datenbanken verfügen bereits über Support für Volltextsuche. Warum verwendet man nicht einfach diese?

Eigentlich wären sie eine gute Wahl für kleinere Anwendungsfälle – denn skalieren ist hierbei sehr schwierig: Wann immer es sich um ein größeres Datenvolumen handelt, wird es schwierig.

Denis Rosa
Denis Rosa (Bild: Couchbase)

Es gibt noch einen erheblichen Vorteil, der für die Verwendung einer richtigen FTS spricht: die Abfragesprache. Die Mehrzahl der relationalen Datenbanken versuchen, dafür erneut SQL zu verwenden. Dabei kann es richtig chaotisch werden, wenn man versucht, erweiterte Suchen zu schreiben. SQL wurde schließlich nicht entwickelt, um sich mit Konjunktions-/Disjunktionsabfragen, Facetten, komplexen Rankingfaktoren usw. zu befassen.

* Denis Rosa ist Developer Advocate bei Couchbase.

Kommentare werden geladen....

Kommentar zu diesem Artikel

Der Kommentar wird durch einen Redakteur geprüft und in Kürze freigeschaltet.

Anonym mitdiskutieren oder einloggen Anmelden

Avatar
Zur Wahrung unserer Interessen speichern wir zusätzlich zu den o.g. Informationen die IP-Adresse. Dies dient ausschließlich dem Zweck, dass Sie als Urheber des Kommentars identifiziert werden können. Rechtliche Grundlage ist die Wahrung berechtigter Interessen gem. Art 6 Abs 1 lit. f) DSGVO.
  1. Avatar
    Avatar
    Bearbeitet von am
    Bearbeitet von am
    1. Avatar
      Avatar
      Bearbeitet von am
      Bearbeitet von am

Kommentare werden geladen....

Kommentar melden

Melden Sie diesen Kommentar, wenn dieser nicht den Richtlinien entspricht.

Kommentar Freigeben

Der untenstehende Text wird an den Kommentator gesendet, falls dieser eine Email-hinterlegt hat.

Freigabe entfernen

Der untenstehende Text wird an den Kommentator gesendet, falls dieser eine Email-hinterlegt hat.

copyright

Dieser Beitrag ist urheberrechtlich geschützt. Sie wollen ihn für Ihre Zwecke verwenden? Infos finden Sie unter www.mycontentfactory.de (ID: 45671961 / Datenbanken)