IPC 2014

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

       +-------------------------+     +-----------------------+
       |                         |     |                       | 
       |                         v     v                       | 
   +-----+----------+   +----+-------------------+   +---+------------------+
   | 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:

  1. Suchwort-Tabelle (mit allen Suchworten wie Berlin, London, Paris – Stop-Worte wie "oder" kommen nicht in die Suchwort-Tabelle)
  2. Such-Index-Tabelle (enthält die Verknüpfung zwischen den Suchworten und den Tabellen-Zeilen, in denen die Suchworte enthalten sind)
  3. 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.

0256-food-hot_dog

Zusammenfassung

  • Verständnis für das Gebiet Volltextsuche gewonnen
  • Volltextsuche mit allereinfachsten Mitteln realisiert
  • Volltextsuche mit internem MySQL Volltext realisiert
  • Professionelle Volltextsuche (wie Suchmaschine) mit drei Extra-Tabellen kennengelernt

Viel Spaß beim kreativen Experimentieren!

Weiterführende Informationen zum Thema Volltextsuche:

[1] http://www.phpbar.de/w/Volltextsuche
[2] Welling, L.; Thomson, L.: "MySQL Tutorial – Die kompakte Einführung in die Arbeit mit MySQL", Reihe MySQL Press, Addison-Wesley (Pearson Education) München, 2004
Seite 155-158: Volltextsuche in MyISAM-Tabellen
[3] Zawodny, J., Balling D.: "High Performance MySQL – Optimierung, Datensicherung, Replikation & Lastverteilung", O'Reilly Koelln, 2005
[4] http://www.linkmatrix.de/volltextsuche

Robert Westenkirchner
Creative Commons License
Such, Bello, such! 3 x Volltextsuche in Datenbanken von Robert Westenkirchner steht unter einer Creative Commons Namensnennung-Weitergabe unter gleichen Bedingungen 3.0 Deutschland Lizenz.
Über diese Lizenz hinausgehende Erlaubnisse erhalten Sie möglicherweise unter www.linkmatrix.de.


Schlagwörter: , ,

17 Kommentare bisher »

  1. matthias sagt

    am 23. Januar 2009 @ 08:34

    Für den Fall, dass man sich die Datenbank aussuchen kann würde ich PostgreSQL empfehlen. Ab Version 8.3 ist Tsearch2 integriert und bisher habe ich damit in eigenen Projekten gute Erfahrungen gesammelt.

    Infos zu Tsearch2:
    http://www.sai.msu.su/~megera/postgres/gist/tsearch/V2/

  2. nQuee sagt

    am 25. Oktober 2009 @ 07:36

    Hallo,

    in meinem Blog hab ich auch eine deutsche Stoppwortliste zum Download zur Verfügung gestellt:

    http://blog.nquee.com/2008/02/mysql-volltextsuche-mit-deutscher-stoppwortliste/

    MfG

  3. Max sagt

    am 12. Februar 2010 @ 20:36

    angenommen ich habe jetz ca. 23 Einträge gefunden, wie kann ich die einträge den Zählen? …

  4. GhostGambler sagt

    am 13. Februar 2010 @ 08:38

    Wie immer?!
    mysql_num_rows() oder SELECT COUNT(…) …

  5. Max sagt

    am 14. Februar 2010 @ 22:13

    Hey bei mir geht gar nichts mehr steht immer nur noch:

    "MySQL lieferte ein leeres Resultat zurück (d. h. null Zeilen). ( die Abfrage dauerte 0.0070 sek. )"

    Obwohl ich mindestes 5 passende in der tabelle hab…
    gestern kam bei nur einem passenden immer eins raus wenn ich aber zwei hatte die passden kam nichts mehr an. ich habe aber nichts am code verändert.

    Gruß, Max.

  6. Adrian sagt

    am 18. April 2010 @ 13:26

    Ich finde die Volltextsuche in MySQL eine einzige Katastrophe, weil es so unglaublich schwierig ist, auf das Ranking Einfluss zu nehmen (viele Szenarien wie die Priorisierung der genauen Fundstelle sind gar nicht umsetzbar). Deshalb bin ich jetzt auf Sphinx umgestiegen. Ist sicher nicht für alle Anwendungsbereiche machbar (weil Sphinx als eigener Daemon läuft), aber die Suchergebnisse sind wirklich um Welten besser, weil ich genau einstellen kann, nach welchen Kriterien die Ergebnisse gerankt werden.

  7. Suchergebnisse schon beim Eintippen mit jQuery « Blog « Advitum Webdesign sagt

    am 24. September 2010 @ 19:15

    […] Volltextsuche in MySQL-Datenbanken […]

  8. MySQL Volltextsuche mit deutscher Stoppwortliste sagt

    am 31. Dezember 2010 @ 15:40

    […] Informationen zum Thema Volltextsuche in MySQL haben will, den Empfehle ich diesen Artikel… Tweet Erstellt in PHP & MySQL Tags: MySQL, Volltextsuche « Wann ist ein Proxy […]

  9. F. Burian sagt

    am 31. Dezember 2010 @ 15:44

    Eine deutsche Stoppwortliste und wie diese implementiert wird, findet man in meinem Artikel: http://burian.appfield.net/entwicklung/php-mysql/mysql-volltextsuche-mit-deutscher-stoppwortliste.htm

    Viele Grüße
    F. Burian

  10. Hiddi sagt

    am 8. April 2012 @ 11:49

    Danke für den super Artikel. Hat mir sehr weitergeholfen.

  11. Martin sagt

    am 4. Mai 2012 @ 16:59

    danke für den artikel. kann ich gleich nem kollegen weiterempfehlen, der auf der suche nach einem suchskript ist!

  12. Robert sagt

    am 1. Juni 2012 @ 20:03

    Freut mich wenn der Artikel einigen weiter geholfen hat. Happy Coding!

  13. Adrian sagt

    am 26. März 2013 @ 00:51

    Schade dass bei der letzen und interesanntesten Variante kein Code mitgeliefert wird, bzw. zur Interesannten Seite verlinkt wird. phpbar.de ist gross, wo genau finde ich denn den jeweiligen Artikel bzw. die erläuterung?

  14. Robert sagt

    am 26. März 2013 @ 10:37

    @Adrian:
    Du findest den Artikel mit Code auf phpbar.de hier:
    http://www.phpbar.de/w/Volltextsuche

    Weiterhin findest Du interessante Links zur Volltextsuche z.B. mit dem wesentlich leistungsfaehigeren Tsearch2 – full text extension for PostgreSQL hier:
    http://www.linkmatrix.eu/search/q/volltextsuche
    Happy coding!

  15. Thor Duisenberg sagt

    am 3. September 2013 @ 22:48

    Danke für den Tipp mit der professionellen Volltextsuche. Ich habe das mit den drei Tabellen umgesetzt und dabei festgestellt, dass das Konzept mit Suchen gar nichts zu tun hat. Bei zwei Millionen Index-Einträgen und zirka 1000 Suchergebnissen, macht das Klick und die Daten sind auf dem Bildschirm. Echt spitze!

  16. Torsten.E sagt

    am 26. Februar 2014 @ 09:44

    Ich bin heute auch auf diesen Artikel gestoßen. Sehr interessant, wenn man in diese Materie einsteigen will.
    Bisher habe ich wie vermutlich die meisten alles mit LIKE (MySQL) umgesetzt. Auf PostgreSQL (wie von Robert beschrieben) kann ich leider nicht umsteigen.

    Die Suchart mit den 3 Tabellen ist mir aus früheren Entwicklungen bereits bekannt, habe ich jedoch in MySQL bisher nicht umgesetzt.

    Was mich viel mehr interessiert ist, wie man die Relevanz verbessern kann. D.h. die Sortierung im Suchergebnis. Die Anzahl der Vorkommen eines Wortes, sowie die letzte Indizierung sagen noch nichts über die Qualität des gefundenen Artikels aus.
    Wir haben z.B. versucht mitzuprotokollieren, wie oft ein Artikel angeklickt wird um diesem eine höhere Relevanz zu geben. Aber das ist alles nur "Versuch und Irrtum".
    Mich würde interessieren, wie man so etwas professioneller umsetzen könnte.

    Grüße

    Torsten.E

  17. Robert sagt

    am 26. Februar 2014 @ 12:15

    @Torsten:

    Geschichte:

    Fuer die Relevanz also das Ranking brauchst Du greifende Kiterien. Google ist mit dem Ranking seiner Suchmaschine erfolgreich geworden weil das Ranking besser war als beim Wettbewerb. Google hat das Prinzip des Rankings bei Buechern uebernommen. Wer am hauefigsten zitiert wird ist am relevantesten. Im Web also Links, wobei gewichtet wird wer auf die Seite gelinkt hat. Das sog. PageRank Verfahren ist relativ geheim u. wird permanent verbessert. Meines Wissens verwendet G. sowohl Algorithmen als auch manuelle Stellschrauben. (Bei Musik ist m.W. Yesterday von den Beatles das relevanteste Lied weil es am haeufigsten gecovert wurde, also aehnliches Relevanz-Prinzip wie bei Buechern.)

    Theorie:

    Die Reihenfolge die MySQL out-of-the-box liefert ist meine Zwecke ziemlich unbrauchbar und muss optimiert werden. Wie haengt immer von den jeweiligen Daten ab.

    Algorithmen sind gut weil sie sich auf alle Daten anwenden lassen aber Ausnahmen bestaetigen die Regel und die Welt ist komplexer als mathematische Modelle sie abbilden koennen. Der Mix aus Regeln + Einzeifallbehandlung bringt m.E. die besten Ergebnisse. Aber es ist ein ewiger Wettlauf mit der Realtitaet nachzubessern bzw. findet man wieder Ausnahmen, Sonderfaelle bzw. Zweideutigkeiten. Das Suchwort Turkey liefert Treffer zur die Tuerkei, wenn in den USA aber Erntedankfest (Thanksgiving) ist, dann Rezepte zu gefuelltem Truthahn. Also auch der zeitliche Kontext spielt eine Rolle.

    Beispiel: $my_ranking

    Bei den Treffern meiner kleinen einfachen LinkMatrix Suchfunktion will ich z.B. beim Suchwort PHP die offizielle PHP.net an erster Stelle haben. Um das Ranking zu verbessern habe ich Ranking Punkte von 0 bis 10000 zu vergeben. Vorgabe ist erstmal 0 Punkte fuer alle Treffer. Wenn das Suchwort in der Domain vorkommt werden +500 addiert. Wenn nur in Unterverzeichniss vorkommt dann +100, im Dateinamen +50. Wenn es im Langtext vorkommt pro Vorkommen +5 (maximal aber gedeckelt auf 50 Punkte weil es sonst wieder das Ergebnis verfaelschen koennte). Dieses algorithmische Ranking-Verfahren hat meine Suchergebnisse deutlich verbessert.
    Google z.B. wertet Suchbegriffe im HTML-Title und in H1-Ueberschriften hoeher als im Fliesstext.
    Google wertet auch die Reihenfolge der Suchwoerter unterschiedlich.

    Manuelle Relevanz-Stellschrauben:

    Weiterhin hab ich auch nen Hit-Counter. Der fliesst auch gewichtet mit ein. Der dient mir auch dazu, wenn ich bei einem speziellen Treffer will dass der ganz vorne in der Trefferliste auftaucht, dann setzte ich den Counter in der DB manuell ganz hoch und erziele damit – allerdings nur in diesem Einzelfall – die gewuenschte Relevanz. Man sollte in seiner DB-Tabelle immer ein Relevanz-Feld einbauen damit man manuell die Treffer-Reihenfolge beeinflussen kann. Weiterhin ist zu ueberlegen was mit Suchwoertern gemeint ist (auch im Kontext, wobei das immer schwierig ist herzustellen bzw. abzugrenzen) und dann das IST-Ergebnis mit dem gewuenschten bzw. erwarteten SOLL-Ergebnis zu vergleichen und ueberlegen wie man das besser machen kann. Das ist eine Wissenschaft fuer sich. Mir macht das viel Spass. Moeglicherweise muss man weitere Felder oder Tabellen oder Kontext wie Zeit oder aehnlices hinzufuegen um bessere Ergebnisse zu erzielen. Es haengt immer vom Use Case ab, welche Loesung optimal ist.

    Das ganze ist in einer PHP-Klasse "Search" die fuer jeden Treffer aus den Rohdaten die Relevanz-Punkte berechnet. Die Funktion heisst nach dem grossen Vorbild pagerank(). Die Reihenfolge der Treffer wird dann danach neu sortiert und ausgegeben. Nach dem ersten Wert in einem assoziativen Array, also Key-Value-Pairs / Schluessel-Werte-Paare kann man wunderbar mit der PHP Funktion rsort($data) sortieren. Dann die besten 10 ausgeben.

    Mein Pagerank zaehlt und addiert zu $my_ranking gewichtet:

    $domain_hits
    $url_hits
    $title_hits
    $body_hits
    plus gewichtetem Hit-Counter

    Hoffe Anregung zu eigenen Konzepten + Loesungen gegeben zu haben.

    Happy Coding!

    http://www.LinkMatrix.eu
    – Open Education Search & Download -

Komentar RSS · TrackBack URI

Hinterlasse einen Kommentar

Name: (erforderlich)

eMail: (erforderlich)

Website:

Kommentar: