Engineering

Volltextsuche mit relationalen Datenbanken am Beispiel PostgreSQL

In PostgreSQL hat man neben der offensichtlichen Suche nach exakten Treffern im Wesentlichen zwei Möglichkeiten um Datensätze zu durchsuchen. Einerseits kann man eine LIKE-Abfrage einsetzen, andererseits ist es für anspruchsvollere Anwendungen möglich, eine echte Volltextsuche zu nutzen.

LIKE-Abfrage

Die einfachste Möglichkeit, die man für die Umsetzung einer Suchfunktion einsetzen kann, ist die sogenannte LIKE-Abfrage. Dieses Abfrageschema wird von allen modernen relationalen Datenbanken unterstützt und dient dazu, einen Datensatz anhand des Vorkommens einer bestimmten Zeichenkette aus der Datenbank abzufragen. Dabei ist es möglich, das %-Zeichen als Platzhalter in der Abfrage zu verwenden, welches für eine beliebige Zeichenkette steht. Diese Lösung lässt sich noch verbessern, indem man die Abfrage so gestaltet, dass die Groß/Kleinschreibung ignoriert wird. Der konkrete Befehl ist je nach Datenbank unterschiedlich, im Falle von PostgreSQL lässt sich das Ganze mit dem Schlüsselwort ILIKE lösen. Wenn man beispielsweise nach einem Blogartikel suchen möchte, in dem an einer beliebigen Stelle die Zeichenkette „zweitag“ vorkommt, kann man folgende Datenbankabfrage verwenden:

SELECT * FROM posts WHERE body ILIKE '%zweitag%'

Wobei in der Praxis natürlich der Suchbegriff „zweitag“ dynamisch an der richtigen Stelle eingesetzt wird und dann die Eingabe des Nutzers enthält.

Diese Methode ist sehr einfach umzusetzen und für einfache Anwendungen, aber auch für die erste Version einer Suchfunktion oft ausreichend. Dabei ist hervorzuheben, dass bei diesem Verfahren neben der ohnehin vorhandenen Datenbank keine zusätzliche Software nötig ist. Ein Nachteil der LIKE-Abfrage ist, dass diese besonders bei einer hohen Anzahl von Datensätzen sehr langsam sein kann, da alle vorhandenen Datensätze einzeln auf Übereinstimmungen mit der Suchanfrage überprüft werden müssen (Sequential Scan). Wie wir in den folgenden Absätzen sehen werden, sind außerdem die Möglichkeiten dieser Methode recht begrenzt, da nur exakte Treffer gefunden werden. Die Nutzer wissen jedoch oft nicht genau wonach sie suchen, darüber hinaus kann es weitere Störfaktoren, wie beispielsweise Tippfehler geben.

Volltextsuche mit PostgreSQL

Um die Volltextsuche so zu gestalten, dass sprachliche Variationen von Wörtern mit einfließen können, muss also eine andere Lösung her. Mit der bei Zweitag standardmäßig eingesetzten Datenbank PostgreSQL ist es möglich eine effiziente, moderne Volltextsuche direkt mit der Datenbank durchzuführen. Dazu kommt der spezielle Datentyp tsvector (Text Search Vector) zum Einsatz, welcher mittels einer PostgreSQL Extension aktiviert werden kann. Dieser ermöglicht es, diverse Transformationen auf einem Text durchzuführen, sodass dieser für die Volltextsuche indiziert werden kann. Dabei werden zum Beispiel Stoppwörter mit geringem semantischen Wert wie z. B. „der“, „die“, „das“ entfernt und mittels Wörterbüchern die Stammformen der verbleibenden Wörter gebildet. So werden dann aus dem englischen Satz „I like to go swimming“ lediglich die relevanten Zeichenketten nebst einer Gewichtung extrahiert, welche sich getrennt vom ursprünglichen Text indizieren und durchsuchen lassen.

SELECT to_tsvector('I like to go swimming');
--------------------------
 'go':4 'like':2 'swim':5

Wenn nun ein Benutzer nach der Zeichenfolge „People who like to swim“ sucht, wird dieselbe Transformation angewendet. Das Ergebnis führt dann bei der Abfrage zu einer hohen inhaltlichen Übereinstimmung, obwohl der Suchbegriff nicht unmittelbar im durchsuchten Text auftaucht. Selbstverständlich sind die Anforderungen an die Transformationen direkt von der Sprache der Texte abhängig. Die standardmäßig aufs Englische optimierte Konfiguration ist z. B. für deutsche Texte völlig ungeeignet:

SELECT to_tsvector('Ich würde gerne schwimmen gehen');
----------------------------------------------------
 'gehen':5 'gern':3 'ich':1 'schwimmen':4 'würde':2

Hier sind noch unwichtige Stoppwörter wie „ich“ und “würde” enthalten, welche das Ergebnis verwässern und den Index unnötig vergrößern würden. Außerdem funktioniert das Stemming (die Reduktion von Wörtern auf ihre Stammform) nicht richtig. Um dies zu umgehen, ist es möglich die Sprache für die Transformation mit anzugeben. Hier die Transformation im Vergleich mit der richtigen Konfiguration für deutsche Texte:

SELECT to_tsvector('german', 'Ich würde gerne schwimmen gehen');
------------------------------
 'geh':5 'gern':3 'schwimm':4

Nun werden auch Stammformen und Stoppwörter wieder korrekt verarbeitet. Wie man also sieht, ist es wichtig zu wissen, in welcher Sprache die Inhalte verfasst sind.

Speziell bei Ruby on Rails kann man das Gem pg_search einsetzen, welches die Erstellung der korrekten Datenbankabfragen übernimmt, sodass man nur noch die zu durchsuchenden Felder konfigurieren muss. Möchte man beispielsweise deutsche Blogartikel nach ihrem Inhalt (body) durchsuchen, genügt es Folgendes zum Model hinzuzufügen:

class Post < ActiveRecord::Base
  include PgSearch
  pg_search_scope :search,
    against: :body,
    using: {tsearch: {dictionary: 'german'}}
end

Die Volltextsuche mit PostgreSQL ermöglicht also die effiziente Volltextsuche direkt in der Datenbank. Der Reiz dieser Methode liegt besonders darin, dass die Abfragen direkt in der primären Datenbank gemacht werden können und somit keine zusätzliche Software nötig ist.

Elasticsearch

Elasticsearch ist ein Open-Source Suchserver, welcher auf der etablierten Suchengine Apache Lucene basiert. Elasticsearch läuft in einem eigenen Prozess und hält dabei eine Kopie der zu durchsuchenden Datensätze vor, damit es daraus optimierte Indizes erstellen kann, welche für die effiziente Suche nötig sind. Mit Elasticsearch ist es zum einen möglich Volltextsuchen wie mit PostgreSQL zu implementieren; die wahren Stärken von Elasticsearch kommen jedoch erst dann zum Vorschein, wenn man die fortgeschrittenen Funktionen ausnutzt. Dazu zählen Aggregationen, erweiterte Textanalyse und vieles mehr. Die Auslagerung der Suchlogik in ein eigenes Teilsystem bringt aber leider auch Nachteile mit sich. Vor allem die Synchronisation der Datensätze mit einer bestehenden (meist relationalen) Datenbank ist eine Herausforderung, die man im Laufe des Entwicklungsprozesses zu meistern hat.

Vorteile von Elasticsearch

Der offensichtlichste Vorteil von Elasticsearch ist die Geschwindigkeit, mit der Suchanfragen verarbeitet werden. In der Regel lassen sich durch die verteilte Architektur von Elasticsearch sogar mehrere Gigabyte große Indizes effizient durchsuchen. Darüber hinaus bietet Elasticsearch jedoch noch weitere Vorteile. Insbesondere bietet es einige Features, die sich mit PostgreSQL nur sehr schlecht und mit unverhältnismäßigem Aufwand umsetzen lassen.

In vielen Anwendungen werden die Ergebnisse eine Suchanfrage auf mehrere Seiten verteilt, was auch als Paginierung bezeichnet wird. Somit muss man nicht auf die Rückgabe aller Datensätze warten und kann schneller auf die Ergebnisse zugreifen. In PostgreSQL lässt sich dies mit den LIMIT- und OFFSET-Befehlen implementieren, jedoch leidet die Performance bei großen Datenmengen. Die Paginierung praktisch beliebig langer Ergebnislisten ist in Elasticsearch effizient umgesetzt, sodass man sich die Ergebnisse ohne zusätzlichen Aufwand in Teillisten beliebiger Größe ausgeben lassen kann.

Besonders bei Text-Attributen mit kurzen Werten oder einer festen Liste an möglichen Ausprägungen bietet es sich an, den Nutzern bereits vor Durchführung der eigentlichen Suchanfrage eine Auto-Vervollständigung der möglichen Werte anzubieten. Dadurch können in vielen Fällen fehlerhafte Suchanfragen durch den Nutzer behoben werden und führen ihn so schneller zum Ziel. Elasticsearch bietet eine dedizierte API, um Vorschlagswerte für Suchanfragen zu generieren.

Auch für die Implementierung einer facettierten Suche bietet Elasticsearch eine flexible Lösung. So ist es möglich dem Nutzer mehrere Filter anzubieten, die er dann beliebig untereinander kombinieren kann, um die Ergebnisse einzuschränken. Hier zahlt sich die durchdachte Konfiguration der Indizes aus, sodass alle erdenklichen Datentypen einzeln sinnvoll abgefragt werden können.

Für manche Anwendungen ist es erforderlich, die Reihenfolge von Indizierung und Suchanfrage umzukehren. Somit kann man Benachrichtigungen erzeugen, wenn neue zu einer Suchanfrage passende Dokumente in den Index aufgenommen wurden. Klassischerweise ist dafür bei jeder Änderung im Index das Durchsuchen aller Datensätze mit allen Suchanfragen nötig. Die Perkolation in Elasticsearch ermöglicht es jedoch, Suchanfragen abzuspeichern und dann Dokumente auf diese gespeicherten Anfragen effizient anzuwenden. Als Ergebnis erhält man dann eine Liste der Anfragen, welche den Datensatz zum Ergebnis haben würden.

Weitere Features von Elasticsearch, um nur einige zu nennen, sind die Detektion von Synonymen, Suche über mehrere Indizes, Suche in HTML/XML-Dokumenten, Geospatiale Suche, positives/negatives Boosting, benutzerdefinierte Analyzer/Tokenizer, Failover, Sharding und Replikation. Einen Überblick über alle Features kann man sich auf der offiziellen Homepage verschaffen. Für die Integration in Ruby On Rails kann man das Gem elasticsearch-rails einsetzen.

Integration mit einem bestehenden System

Um die Vorteile von Elasticsearch nutzen zu können, müssen die zu durchsuchenden Daten als JSON über die REST-API von Elasticsearch bereitgestellt werden. Zunächst einmal ist es nötig die bestehende Applikation so zu erweitern, dass die zu durchsuchenden Datensätze im JSON-Format serialisiert werden können. Hierarchisch organisierte Teilstrukturen in der Datenbank können gemeinsam in einem Index abgelegt werden, in etwa so wie bei dokumentenbasierten Datenbanken. Um beliebige Beziehungen zwischen Objekten modellieren zu können, kann es jedoch erforderlich sein, mehrere Indizes zu erstellen.

Synchronisation mit der Datenbank

Aus der Trennung von Datenbank und Suchserver ergibt sich die Notwendigkeit der Synchronisation dieser beiden Systeme. Wenn sich ein Datensatz ändert, hinzugefügt wird oder gelöscht wird, dann muss auch der dazu gehörige Eintrag in Elasticsearch entsprechend angepasst werden. Dies kann vor allem dann schwer in den Griff zu bekommen sein, wenn man in Beziehung stehende Datensätze mit in den Suchindex aufgenommen hat. Die naive Lösung für dieses Problem ist, den Suchindex regelmäßig neu zu importieren. Dies ist aus zeitlichen Gründen allerdings nur bei einer relativ kleinen Menge an Daten praktikabel.

Um performant zu bleiben, ist es daher erforderlich in die Anwendung, welche Datenbank und Suchserver miteinander verbindet, Mechanismen aufzunehmen die bei Veränderungen in den Daten die entsprechenden Informationen an Elasticsearch weitergeben. Dadurch wächst die Problematik in ihrer Komplexität ähnlich wie bei einer Cache-Invalidierung. Die Mechanismen der Invalidierung sind für jede Anwendung individuell zu gestalten und daher mit hohem manuellem Aufwand verbunden und dadurch anfälliger für Fehler. Daher empfiehlt es sich, trotzdem in regelmäßigen Abständen den gesamten Index neu zu importieren, z.B. monatlich. Alternativ kann man zur Synchronisation auch andere Ansätze wie Event Sourcing einsetzen.

Aufgrund der Synchronisations-Problematik sind einige Betreiber dazu übergegangen, Elasticsearch direkt als primäre Datenbank zu nutzen. Dies ist allerdings nur praktikabel, wenn sich die Datensätze gut in einem dokumentenbasierten Modell abbilden lassen. Für ein Datenmodell mit vielfältigen Beziehungen zwischen den Objekten ist eine hybride Architektur mit relationaler Datenbank wohl weiterhin die bessere Wahl.

Konfigurieren der Indizes und Import von Datensätzen

Beim Datenimport ist besonders das sogenannte Mapping, also die Konfiguration der Indizes von Interesse, wobei zwischen dynamischem und statischem Mapping zu unterscheiden ist. Beim dynamischen Mapping überlässt man es Elasticsearch anhand der ersten importierten Datensätze selbstständig zu entscheiden, welche Datentypen für welche Felder verwendet werden sollen, und wie diese zu indizieren sind. Um die Möglichkeiten von Elasticsearch voll ausschöpfen zu können ist es jedoch empfehlenswert ein statisches Mapping zu erstellen, bei dem die Datentypen und Index-Optionen für jedes Attribut einzeln festgelegt werden. So ist es z.B. möglich auf Zeichenketten diverse Transformationen wie Kleinschreibung, Stemming und Transliteration anzuwenden. Daneben können ein oder mehrere Indizes für jedes Attribut erstellt werden. Dies ist vor allem dann nützlich, wenn ein Attribut auf verschiedene Arten durchsucht werden soll. Man kann hier z.B. einen Index für die Suche nach exakten Treffern, einen für unscharfe Suche und einen für die Suche von Teil-Zeichenketten (N-Gramme) konfigurieren. Dies ermöglicht später äußerst fein abgestimmte Suchanfragen.

Fazit

Es existieren zwei unterschiedliche Ansätze, um eine Volltextsuche in eine Anwendung zu integrieren. Zum einen gibt es die Möglichkeit eine simple Volltextsuche direkt mit einer bestehenden Datenbank umzusetzen, wobei hier besonders durch den Einsatz von PostgreSQL mit seinen Volltext-Features ein gutes Ergebnis erzielt werden kann. Sollte der Funktionsumfang der Datenbank nicht ausreichen oder nicht performant genug sein, gibt es die Möglichkeit auf einen externen Suchserver wie Elasticsearch auszuweichen. Solche dedizierten Systeme sind auf die Volltextsuche spezialisiert und lassen dahingehend keine Wünsche offen, sind jedoch in der Regel aufwendiger in der Handhabung. Die Entscheidung, welche Technologie bzw. welcher Ansatz für ein bestimmtes Projekt die optimale Lösung darstellt, hängt dementsprechend von den konkreten Anforderungen ab. Wie dieser Artikel gezeigt hat, gibt es jedoch auch beim Thema Suche für jeden Topf den passenden Deckel.