Volltextsuche in MySQL-Datenbanken

Dieser Beitrag zeigt, welche Möglichkeiten MySQL zur Suche in Texten bietet und wie man diese justieren kann, um optimale Suchergebnisse zu erhalten. Dies ist ein Gastbeitrag von Robert Westenkirchner.

Am Beispiel der Open Source Technologien

MySQL (Datenbank / Backend)
PHP (Middleware / Klebstoff zwischen Front- und Backend)
XHTML als Front-End.

Lernziele:

Verständnis für das Gebiet Volltextsuche gewinnen
Volltextsuche mit allereinfachsten Mitteln realisieren: LIKE %suchwort% (Performance: niedrig)
Volltextsuche mit internem MySQL Volltext realisieren MATCH AGAINST (Performance: mittel / skaliert mittelmäßig)
Professionelle Volltextsuche (wie Suchmaschine) mit drei Extra-Tabellen kennenlernen: 1. Suchwort-Tabelle 2. Suchindex-Tabelle (Verknüpfung Suchwort mit Fundstelle / Viele-zu-Viele Beziehung) 3. Such-Zeitstempel Tabelle für Neu-Indizierung bei Änderungen der Artikel (Performance: hoch) – skaliert gut

Was ist eine Volltextsuche? (Variante I)

Eine Volltextsuche findet beispielsweise die drei Suchwörter „Berlin London Paris“ wenn die Wörter nicht nur genau in dieser Reihenfolge im Text vorkommen, sondern jeweils an beliebiger Stelle im Text vorkommen. Eine Einwortsuche kann simpel mit

SELECT * FROM articles WHERE body LIKE %Berlin%

realisiert werden.

Wollen wir nun nach „Berlin London Paris“ suchen, dann müssen wir den Suchstring in Einzelwörter zerlegen und obige LIKE Abfrage dreimal für die jeweiligen Suchwörter durchführen. Das ist nicht sehr performant, da für jedes Suchwort eine Abfrage durchgeführt werden muss und wird an dieser Stelle nicht weiter vertieft. Kommen wir lieber zur zweiten, interessanten Methode: MATCH AGAINST

Volltextsuche mit MySQL Bordmitteln (Variante II)

steht nur in Tabellen von Typ MyISAM zur Verfügung. Damit kann man sehr schön nach Wörtern in Textblöcken suchen, z.B. in Artikeln.

Mit dem folgenden SQL-Code erstellst Du eine MyISAM-Tabelle mit Volltextindex:

CREATE TABLE article ( articleID int not null auto_increment primary key, 
        title varchar(255) , url varchar(255), body text, fulltext (title, body, url) );

Die Volltextsuche führst Du wie folgt aus:

SELECT title FROM article WHERE MATCH (title, body, url) AGAINST ('Berlin London Paris');

Beachte, dass wir alle Artikel finden, die mindestens eines der Wörter enthalten. Der Artikel muss nicht alle drei Wörter enthalten.

Leider unterstützt MySQL gegenwärtig keine Wortstämme. Die Suche nach „Ausgehen“ und „Ausgang“ müssten wir separat durchführen. Die Wortstammunterstützung ist eine Technik, die in vielen anderen Volltext-Suchsystemen implementiert ist. Sie kann verschiedene Wortabwandlungen eines Stammwortes wie oben beschrieben erkennen.

Ranking optimieren

Jedem gefundenen Treffer wird ein Relevanzwert zugeordnet. Die Ergebnisse können dann in Übereinstimmung mit diesem Relevanzwert automatisch sortiert werden. In der von mir entwickelten www.LinkMatrix.de kommt die MySQL Volltextsuche zum Einsatz, allerdings das automatische Sortieren der Treffer war nicht zufriedenstellend, außerdem hat man darauf kaum Einfluss. In der Regel hat man aber eine genaue Vorstellung welche Ergebnisse zuerst ausgegeben werden sollen.

Beispielsweise soll die Suche nach „PHP“ die Seite www.php.net weit vorne liegen und nicht Seiten, die sehr häufig das Suchwort PHP im Artikeltext beinhalten.

Die Reihenfolge, also das Ranking, ist sehr wichtig für die Zufriedenheit der Anwender.
In einem Online-Shop oder bei einer Auktions-Plattform soll bei den Treffern möglichst der Artikel vorne liegen, den der Anwender mit seinen Suchwörtern finden will. Das ist eine Kunst für sich, dazu werden viele Doktorarbeiten geschrieben.

Daher solltest Du das Ranking optimieren. Ein Artikel, der das Suchwort in der URL oder im Titel beinhaltet wird höher gerankt als wenn das Suchwort nur im Text vorkommt. Ganz simpel kann man das Ranking mit nem Punktesystem ermitteln, z.B.:

200 Punkte für Vorkommen des Suchwortes in der URL
50 Punkte für Vorkommen des Suchwortes im Titel
10 Punkte für Vorkommen des Suchwortes im Fließtext (body)

Vorgehensweise:
Erstmal lässt Du Dir irgendeinen Algorithmus wie oben beschrieben einfallen und dann testet Du diesen auf Deinem Datenbestand und guckst, ob das so hinhaut. Meist muss man das immer wieder optimieren. Die erfolgreichste Suchmaschine der Welt, Google verbesserte die Qualität des Rankings seiner Treffer dramatisch durch diesen einfachen Trick:
Wie macht man das in der Wissenschaft? Welcher Artikel ist relevant, ist wertvoll? Mit dem das meiste Geld verdient wurde? Nein. Der Wert der Veröffentlichungen von Wissenschaftlern misst sich einfach daran, wie oft dieser zitiert wird. Auch wie bedeutend der jenige ist, der ihn zitiert hat. Das hat sich Google abgeguckt und die Idee aufs Netz erfolgreich übertragen.

Einschränkungen bei der MySQL-Volltextsuche

Leider findet man mit obiger Methode nur Wörter, die vier oder mehr Buchstaben haben. Wenn man nach „Rom“ sucht, gibts immer null Treffer, auch wenn Rom in Tabellenfeldern vorkommt.

Lösungsvarianten für kurze Worte

Kurze Worte werden nicht indiziert, d.h. Worte mit weniger als vier Zeichen werden standardmäßig ignoriert. Kurze Wörter wie die Abkürzungen PHP oder XML sind aber wichtig für das Suchen, daher muss man die MySQL-Volltextsuche an der Stelle verbessern.

Lösungsvariante I:
– mit der Variablen ft_min_word_len kann man diese Beschränkung überwinden.

Lösungsvariante II:
– bei LinkMatrix hab ich einfach auf die bereits oben beschriebene Suche mit LIKE zurückgegriffen. Sicherlich gibts noch weitere, bessere Lösungsvarianten.

Performance steigern durch Stop-Wörter

Volltextindizes verwenden Stop-Wörter. Ein Stop-Wort ist ein Wort ohne semantische Bedeutung. Normalerweise handelt es sich dabei um häufige Wörter, die für den Satzaufbau wichtig, aber in der Regel bedeutungslos für die Suche sind. „bald“ „sehr“ „ganz“ „oder“ sind für die Suche ungeeignet. MySQL enthält hierfür nicht nur Standard-Wortlisten, sondern bietet auch die Möglichkeit, für die jeweils benötigte Sprache eigene Stop-Wortlisten zu erstellen.

Leistungseinbußen bei sehr großen Tabellen

Laut MySQL ist die Performance der eingebauten Volltextsuche bis 1.000.000 Zeilen gut einsetzbar. Bei kleinen Anwendungen wird dies keine Probleme bereiten – bei größeren jedoch solltest Du diese Tatsache im Hinterkopf behalten.

Hierfür ist die dritte Lösungsvariante am besten geeignet, allerdings ist diese auch mit mehr Aufwand verbunden, weil das was MySQL mit der eingebauten Volltextsuche für einen erledigt, muss man sich hier selber kümmern:

Professionelle Volltextsuche wie bei Suchmaschinen mit drei Extra-Tabellen (Variante III)

Volltextsuche auf Basis eines Indizes mit allen Suchworten. Bei der vorherigen eingebauten MySQL Volltextsuche war das beim Erstellen der Tabelle mit dem Zusatz „fulltext“ erledigt. Jetzt müssen wir uns da selber drum kümmern, gewinnen dadurch aber mehr Einfluss.

Nach diesem Prinzip arbeiten alle Suchmaschinen: Ein Crawler, Spider oder auch Bot (von Roboter) genannte Software hangelt sich von Link zu Link durchs Netz und sammelt alle Texte ein, die er findet und schreibt sie in eine Datenbank. Wir gehen davon aus, das wir schon eine Datenbank mit Inhalten haben und für diese bauen wir uns eine maßgeschneiderte Volltextsuche.

Volltextsuche mit drei Zusatz-Tabellen

 
  +-----+----------+   +----+-------------------+   +---+------------------+ 
  | swid| Suchwort |   | id | swid doc_id count |   | id| doc_id timestamp |   
  +-----+----------+   +----+-------------------+   +---+------------------+ 
  |     |          |   |    |                   |   |   |                  | 
  | 1   | Berlin   |   |  1 |   3    23      3  |   | 1 | 23   2009-01-22  | 
  | 2   | London   |   |  2 |   1    17      1  |   | 2 | 17   2009-01-22  | 
  | 3   | Paris    |   |  3 |   2    12      1  |   | 3 | 12   2009-01-22  | 
  |     |          |   |    |                   |   |   |                  | 
  +-----+----------+   +----+-------------------+   +---+------------------+ 
  1. Suchwort-Tabelle     2. Such-Index-Tabelle     3. Such-Zeitstempel Tab.

Zu der vorhanden Artikel Tabelle brauchen wir drei zusätzliche Tabellen:

Suchwort-Tabelle (mit allen Suchworten wie Berlin, London, Paris – Stop-Worte wie „oder“ kommen nicht in die Suchwort-Tabelle)
Such-Index-Tabelle (enthält die Verknüpfung zwischen den Suchworten und den Tabellen-Zeilen, in denen die Suchworte enthalten sind)
Such-Zeitstempel-Tabelle (wann wurde diese Dokument das letzte Mal indiziert)

Da das schon im Netz ausführlich auf www.phpbar.de [1] beschrieben wurde, verweise ich da nur drauf.