Einzelnen Beitrag anzeigen
  #13 (permalink)  
Alt 13-12-2008, 13:22
Benutzerbild von onemorenerd onemorenerd
  Moderator
Links : Onlinestatus : onemorenerd ist offline
Registriert seit: Mar 2005
Ort: Berlin
Beiträge: 9.471
onemorenerd wird schon bald berühmt werdenonemorenerd wird schon bald berühmt werden
Standard

Zitat:
Original geschrieben von Nordin
Wenn der user in der suche eingibt "sdgfgsd" und ein anderer "gddcler" dann sind das ja alles wort die im "searchindex" landen. lezten endes wird dieser index ja dann auch über ein paar milliarden einträge groß.
Wenn ein User einen Suchbegriff eingibt, landet dieser nicht im Suchindex. Das hast du falsch verstanden.

Wir haben eine Applikation, sagen wir mal ein CMS. Da werden Texte eingegeben und in der DB gespeichert in der Tabelle texte(id, title, body).
Wir wollen diese Texte durchsuchen, aber nicht mit "SELECT COUNT(*) ..." und "SELECT ... LIKE '%Suchbegriff%' LIMIT 0,10". Das skaliert einfach nicht. Wenn wir sehr viele Texte haben, wird die Suche sehr langsam sein. Wir wollen eine Suche, deren Performance nicht von der Anzahl der durchsuchten Texte abhängt.

Das geht nur mit etwas Vorbereitung. Wir bauen einen Suchindex auf. Der besteht aus der Tabelle search_count(word, count). Unser CMS erweitern wir so, dass sofort nach dem Speichern eines Textes in texte eine Routine aufgerufen wird, welche den Text in einzelne Wörter zerlegt. Für jedes Wort wird dann ein Eintrag in search_count angelegt bzw. der Count-Wert um 1 erhöht.
Code:
texte:
id | title         | body
-------------------------------------------
1  | Hallo Welt    | Mein erster Text.
2  | Nochmal hallo | Mein zweiter Text.
3  | Schluss       | Mein Text-Text.

search_count:
word    | count
--------------------------
hallo   | 2
welt    | 1
mein    | 3
erster  | 1
text    | 4
nochmal | 1
zweiter | 1
schluss | 1
Mit diesem Trick können wir auf das "SELECT COUNT(*) ..." schon verzichten, denn die Anzahl der Treffer für einen Suchbegriff ist sein Count-Wert. Für das Retrieval der Treffer müssen wir aber immernoch mit "LIKE '%Suchbegriff%'" arbeiten. Deshalb erweitern wir den Index um eine Tabelle search_index(word, texte_id).
Code:
search_index:
word    | texte_id
--------------------------
hallo   | 1
hallo   | 2
welt    | 1
mein    | 1
mein    | 2
mein    | 3
erster  | 1
text    | 1
text    | 2
text    | 3
nochmal | 2
zweiter | 2
schluss | 3
Damit brauchen wir keine LIKE-Queries mehr. Unsere Suche ist jetzt schon ziemlich performant. Aber sie ist auch schwach, denn sie findet nur exakte Übereinstimmungen einzelner Wörter und alle Treffer sind gleich relevant.
Dröseln wir das mal auf. Wir haben folgende Probleme:
1. nur exakte Übereinstimmungen, Suche nach "erste" liefert keine Treffer
2. nur einzelne Wörter, Suche nach "hallo text" zwar machbar, aber keine Aussage über Anzahl Treffer möglich
3. keine Relevanz, bei Suche nach "text" ist texte:3 ein besserer Treffer

Die Lösung zu 1. ist einfach: Alle Wörter im Suchindex werden klein geschrieben und - das ist neu - durch einen Stemmer auf ihren Wortstamm reduziert. Das selbe machen wir dann mit den Wörtern der Suchanfrage.
Die Lösung zu 2. ist noch einfacher: Wir benutzen search_count bei Mehrwortsuchen nicht, sondern machen ein "SELECT COUNT(*) FROM search_index". (Es geht auch besser, aber das führt jetzt zu weit.)
Die Lösung zu 3. ist auch einfach: Wir erweitern search_index um eine Spalte count, die angibt, wie oft ein Wort im jeweiligen Text vorkommt. Diese neue Spalte nutzen wir als Sortierkriterium bei der Anzeige der Treffer.
Code:
search_index:
word    | texte_id | count
--------------------------
hallo   | 1        | 1
hallo   | 2        | 1
welt    | 1        | 1
mein    | 1        | 1
mein    | 2        | 1
mein    | 3        | 1
erster  | 1        | 1
text    | 1        | 1
text    | 2        | 1
text    | 3        | 2   <- siehe!
nochmal | 2        | 1
zweiter | 2        | 1
schluss | 3        | 1
Wie du siehst, ist die Schwierigkeit beim Suchen nicht das Finden, sondern die geschickte Indizierung (Zerlegung eines Textes, Stemming, Relevanzberechnung) sowie die Optimierung für komplexe Suchanfragen (Mehrwortsuche, Phrasensuche, NOT-Suche). Mit Google kann unser CMS natürlich nicht mithalten. Aber unsere Suche ist schnell und vor allem ausbaufähig.

Übrigens ist Google nicht die einzige schnelle Suche. Das Besondere ist nur, dass Google so einen riesigen Index hat. Den können Wald-und-Wiesen-Systeme gar nicht verwalten. Es steckt viel Know-How in der Verteilung der Daten und Anfragen.
Allerdings kommt das in unserem Arbeitsumfeld nicht vor; wir haben keine so riesigen Datenmengen. Wenns brenzlig wird, nehmen wir Solr/Lucene, weil das bis jenseits unseres Horizonts skaliert. (Übrigens OSS, man kann sich also anschauen wie es gemacht wird.) Im Normalfall arbeiten wir aber sogar "nur mit MySQL", denn das ist auf jedem Webspace verfügbar. Die Skalierung überlassen wir dem DBA ... soll er doch mehr RAM drauf werfen oder noch ein paar Slaves zuschalten.
Mit Zitat antworten