Wie kann google so schnell sein?

Hallo zusammen,

ich stelle mir schon ewig die Frage wie google es schaft so verdammt schnell Ergebnisse auf eine Suchanfrage zu liefern.

Gebe ich z.B. das Wort "und" eine, bekomme ich sage und schreibe 1.560.000.000 Ergibnisse... das allerdings in Rekortzeit von 0,16 Sekunden.

Wenn ich mir überlege ich hätte eine Datenbank mit 1.560.000.000 Milliarden Datensätzen und würde die anfrage mit zb.:

SELECT * FORM tabelle WHERE datensatz LIKE '%und%'

stellen, dann bin ich mir sicher das ich mehere Sekunden brauchen würde.

Wie macht das aber google das sie so schnell suchen können?
Wo ist der Trick?

@Mods: Ich weiß nicht ob es der richtige Bereich ist, wenn nicht einfach verschieben...

Gruß Nordin

Erstmal bekommst du ja nicht alle ergebnisse, sondern nur einen teil. Die gesamtangabe ist, wie man auch lesen kann, nur eine schätzung. Google fährt darüber hinaus im ertremen clusterbetrieb. Deswegen können die ergebnisse sich von datacenter zu datacenter teilweise auch erheblich unterscheiden. Wie genau die daten möglichst synchron gehalten werden ist googles geheimnis. Es könnte da verschiedene ansätze geben. Bemüh einfach mal google

oO geheimnis?
map/reduce heißt das zauberwort.
die synchronisation ist wohl auch nicht anders als bei anderen extrem verteilten systemen (wikipedia) ..
(btw: Hier gibts einen vortrag von prof. reinefeld vom zib über ein geniales system für verteilte data stores auf p2p basis (chord#), womit seine ag eine signifikant schnellere wikipedia gebaut haben. die slides dazu hier. einfach nur sehr sehr geil!)

googles eigentliches geheimnis und erfolgsrezept ist der ranking algorithmus!

und deinen query könntest du auch schneller machen, in dem du einfach ein "LIMIT 0,20" hinten dran hängst..

MapReduce ist erstmal nur ein Konzept. Die genaue Implementierung (das "genau" hier war auch das "genau" was ich in meiner vorherigen Beitrag meinte) ist Googles Geheimnis. Und von Erfolgsgeheimnis hat erstmal keiner was gesagt. Obwohl ich darüberhinaus den PageRank Algo nicht als "Erfolgs"-Geheimnis ansehen würde. Das war ganz sicher nicht das, was Google groß gemacht hat.

Obwohl ich darüberhinaus den PageRank Algo nicht als "Erfolgs"-Geheimnis ansehen würde. Das war ganz sicher nicht das, was Google groß gemacht hat.

Nee denke ich auch nicht... Ich sage das war das Konzept mit der Werbung. Aber gut das schleift vom Thema ab *g*

Wenn ich das mit "LIMIT 0,20" noch mache dann muss ich ja 2 Anfragen an die datenbank stellen.

Zum einen wieviele einträge habe ich alo:
mysql_num_rows => SELECT * FORM tabelle WHERE datensatz LIKE '%und%'

Zum anderen die anzeige der ergebnisse zb. für die ersten 20 ergebnisse:
SELECT * FORM tabelle WHERE datensatz LIKE '%und%' LIMIT 0, 20

Oder hab ich nen denk Fehler?

Zunächst mal solltest du SELECT COUNT(*) verwenden statt mysql_num_rows(). Das geht schneller.

Aber prinzipiell hast du Recht, du brauchst zwei Queries; eine zum Zählen der Treffer und eine zum Rausziehen von x Treffern. Die Queries können in Summe aber immernoch schneller sein, als eine einzige.

Und du kannst optimieren. Beispielsweise könnte man die Trefferzahl vorab berechnen - bei jedem INSERT/UPDATE/REPLACE/DELETE wird der Datensatz in Wörter zerlegt und die Werte in einer Tabelle searchindex(word, count) entsprechend angepasst. Dann genügt ein SELECT count FROM searchindex WHERE word = ... um die Treffer zu zählen.

Dieser Ansatz ist natürlich nur für Einwortsuchen brauchbar. Aber man kann ihn ausbauen, bis dahin, dass man gar kein LIKE mehr benutzt. Bei Interesse kann ich das gern auch noch weiter ausführen. Jetzt muss ich aber erstmal weg.

Zunächst mal solltest du SELECT COUNT(*) verwenden statt mysql_num_rows(). Das geht schneller.

Super Tip wusste ich garnicht.

Und du kannst optimieren. Beispielsweise könnte man die Trefferzahl vorab berechnen - bei jedem INSERT/UPDATE/REPLACE/DELETE wird der Datensatz in Wörter zerlegt und die Werte in einer Tabelle searchindex(word, count) entsprechend angepasst. Dann genügt ein SELECT count FROM searchindex WHERE word = ... um die Treffer zu zählen.

Genau so hab ich mir das schon geadcht. Nur konnte ichj mir nicht vorstellen das man das so macht weil wenn ich weiter denke kome ich auf folgendes Beispiel:

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ß. wie siht es dann mit der performace aus oder ist es dann egal weil es so schneller geht?

Dieser Ansatz ist natürlich nur für Einwortsuchen brauchbar. Aber man kann ihn ausbauen, bis dahin, dass man gar kein LIKE mehr benutzt. Bei Interesse kann ich das gern auch noch weiter ausführen. Jetzt muss ich aber erstmal weg.

Sehr gern. Das ist eine Frage die ich mir schon lange stelle. von daher kann ich auch warten

Was mir da noch einfällt,

wozu brauch ich mysql_num_rows dann noch wenn COUNT() schneller ist?
(jetzt nicht speziell für eine suchmaschiene, sondern im allgemein)

btw wenn Du immer select * from table machst wunder Dich nicht wenns mal etwas länger dauert. Du wirst ein Snickers Junkie werden

Google benutzt halt kein MySQL. Ursprünglich wurde Google ja an der Uni Stanford entwickelt und dementsprechend sind die Forschungsergebnisse von damals auch veröffentlicht worden: http://infolab.stanford.edu/pub/papers/google.pdf

Original geschrieben von Nordin
Super Tip wusste ich garnicht.


Genau so hab ich mir das schon geadcht. Nur konnte ichj mir nicht vorstellen das man das so macht weil wenn ich weiter denke kome ich auf folgendes Beispiel:

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ß. wie siht es dann mit der performace aus oder ist es dann egal weil es so schneller geht?

Sehr gern. Das ist eine Frage die ich mir schon lange stelle. von daher kann ich auch warten

das phpbb arbeitet ähnlich.
wenn du einen neuen beitrag postest werden alle wörter in einer extra tabelle hinterlegt und wo diese wörter zu finden sind.

bei ca 5000 beiträgen ist diese tabelle gerne 50000-100000 datensätzen groß

btw wenn Du immer select * from table machst wunder Dich nicht wenns mal etwas länger dauert. Du wirst ein Snickers Junkie werden

Nein nein... das ist nur ein besispiel... ich gebe immer namen ann... bei login zb. select name, passwd


Die PDF gefällt mir auch gut nur ist mein anglisch nicht so gut das ich es mit einen klax durchlesen kann hab sie mal überlogen... ne feine sache...

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.

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).

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.

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.

Super!

Das ist eine guter Ansatz. So wär ich da garnicht drauf gekommen.
Ich werdem ir das bei gelegenheit mal anschauen und mal testen. Aber das ist echt top... da hab mich mal wieder voll verkehrtrum gedacht. *g*