php-resource



Zurück   PHP-Scripte PHP-Tutorials PHP-Jobs und vieles mehr > Entwicklung > PHP Developer Forum
 

Login

 
eingeloggt bleiben
star Jetzt registrieren   star Passwort vergessen
 

 

 


PHP Developer Forum Hier habt ihr die Möglichkeit, eure Skriptprobleme mit anderen Anwendern zu diskutieren. Seid so fair und beantwortet auch Fragen von anderen Anwendern. Dieses Forum ist sowohl für ANFÄNGER als auch für PHP-Profis! Fragen zu Laravel, YII oder anderen PHP-Frameworks.

Antwort
 
LinkBack Themen-Optionen Bewertung: Bewertung: 3 Stimmen, 5,00 durchschnittlich.
  #1 (permalink)  
Alt 12-12-2008, 08:04
Nordin
 Registrierter Benutzer
Links : Onlinestatus : Nordin ist offline
Registriert seit: Aug 2005
Ort: DE / S-A
Beiträge: 415
Nordin befindet sich auf einem aufstrebenden Ast
Standard 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.:
Code:
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
Mit Zitat antworten
  #2 (permalink)  
Alt 12-12-2008, 08:20
unset
  Moderator
Links : Onlinestatus : unset ist offline
Registriert seit: Jan 2007
Ort: Düsseldorf
Beiträge: 3.782
unset befindet sich auf einem aufstrebenden Ast
Standard

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
Mit Zitat antworten
  #3 (permalink)  
Alt 12-12-2008, 18:09
frodenius
 Registrierter Benutzer
Links : Onlinestatus : frodenius ist offline
Registriert seit: Sep 2006
Ort: Germany, Frankfurt/Main
Beiträge: 156
frodenius ist zur Zeit noch ein unbeschriebenes Blatt
Standard

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..
__________________
blllubb
Mit Zitat antworten
  #4 (permalink)  
Alt 12-12-2008, 18:51
unset
  Moderator
Links : Onlinestatus : unset ist offline
Registriert seit: Jan 2007
Ort: Düsseldorf
Beiträge: 3.782
unset befindet sich auf einem aufstrebenden Ast
Standard

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.
Mit Zitat antworten
  #5 (permalink)  
Alt 12-12-2008, 19:16
Nordin
 Registrierter Benutzer
Links : Onlinestatus : Nordin ist offline
Registriert seit: Aug 2005
Ort: DE / S-A
Beiträge: 415
Nordin befindet sich auf einem aufstrebenden Ast
Standard

Zitat:
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?
Mit Zitat antworten
  #6 (permalink)  
Alt 12-12-2008, 19:29
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

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.
Mit Zitat antworten
  #7 (permalink)  
Alt 12-12-2008, 19:38
Nordin
 Registrierter Benutzer
Links : Onlinestatus : Nordin ist offline
Registriert seit: Aug 2005
Ort: DE / S-A
Beiträge: 415
Nordin befindet sich auf einem aufstrebenden Ast
Standard

Zitat:
Zunächst mal solltest du SELECT COUNT(*) verwenden statt mysql_num_rows(). Das geht schneller.
Super Tip wusste ich garnicht.


Zitat:
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?

Zitat:
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
Mit Zitat antworten
  #8 (permalink)  
Alt 12-12-2008, 19:44
Nordin
 Registrierter Benutzer
Links : Onlinestatus : Nordin ist offline
Registriert seit: Aug 2005
Ort: DE / S-A
Beiträge: 415
Nordin befindet sich auf einem aufstrebenden Ast
Standard

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)
Mit Zitat antworten
  #9 (permalink)  
Alt 12-12-2008, 19:45
MelloPie
 PHP Master
Links : Onlinestatus : MelloPie ist offline
Registriert seit: Jan 2002
Ort: Hessen
Beiträge: 4.380
MelloPie ist zur Zeit noch ein unbeschriebenes Blatt
Standard

btw wenn Du immer select * from table machst wunder Dich nicht wenns mal etwas länger dauert. Du wirst ein Snickers Junkie werden
__________________
Beantworte nie Threads mit mehr als 15 followups...
Real programmers confuse Halloween and Christmas because OCT 31 = DEC 25
Mit Zitat antworten
  #10 (permalink)  
Alt 12-12-2008, 19:48
Hopka
 PHP Expert
Links : Onlinestatus : Hopka ist offline
Registriert seit: May 2003
Ort: Köln
Beiträge: 2.172
Hopka ist zur Zeit noch ein unbeschriebenes Blatt
Hopka eine Nachricht über ICQ schicken
Standard

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
Mit Zitat antworten
  #11 (permalink)  
Alt 12-12-2008, 20:02
UzumakiNaruto
 Registrierter Benutzer
Links : Onlinestatus : UzumakiNaruto ist offline
Registriert seit: Nov 2004
Beiträge: 642
UzumakiNaruto befindet sich auf einem aufstrebenden Ast
Standard

Zitat:
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ß
__________________
Gruß
Uzu

private Homepage
Mit Zitat antworten
  #12 (permalink)  
Alt 12-12-2008, 20:16
Nordin
 Registrierter Benutzer
Links : Onlinestatus : Nordin ist offline
Registriert seit: Aug 2005
Ort: DE / S-A
Beiträge: 415
Nordin befindet sich auf einem aufstrebenden Ast
Standard

Zitat:
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...
Mit Zitat antworten
  #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
  #14 (permalink)  
Alt 13-12-2008, 13:37
Nordin
 Registrierter Benutzer
Links : Onlinestatus : Nordin ist offline
Registriert seit: Aug 2005
Ort: DE / S-A
Beiträge: 415
Nordin befindet sich auf einem aufstrebenden Ast
Standard

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*
Mit Zitat antworten
Antwort

Lesezeichen


Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)
 

Themen-Optionen
Thema bewerten
Thema bewerten:

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are an


PHP News

ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlicht
ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlichtDie bekannte Marktplatzsoftware ebiz-trader ist in der Version 7.5.0 veröffentlicht worden.

28.05.2018 | Berni

Wissensbestand in Unternehmen
Wissensbestand in UnternehmenLebenslanges Lernen und Weiterbilden sichert Wissensbestand in Unternehmen

25.05.2018 | Berni


 

Aktuelle PHP Scripte

PHP Server Monitor

PHP Server Monitor ist ein Skript, das prüft, ob Ihre Websites und Server betriebsbereit sind.

11.09.2018 Berni | Kategorie: PHP/ Security
PHP WEB STATISTIK ansehen PHP WEB STATISTIK

Die PHP Web Statistik bietet Ihnen ein einfach zu konfigurierendes Script zur Aufzeichnung und grafischen und textuellen Auswertung der Besuchern Ihrer Webseite. Folgende zeitlichen Module sind verfügbar: Jahr, Monat, Tag, Wochentag, Stunde Folgende son

28.08.2018 phpwebstat | Kategorie: PHP/ Counter
Affilinator - Affilinet XML Produktlisten Skript

Die Affilinator Affilinet XML Edition ist ein vollautomatisches Skript zum einlesen und darstellen der Affili.net (Partnerprogramm Netzwerk) Produktlisten und Produktdaten. Im Grunde gibt der Webmaster seine Affilinet PartnerID ein und hat dann unmittelb

27.08.2018 freefrank@ | Kategorie: PHP/ Partnerprogramme
 Alle PHP Scripte anzeigen

Alle Zeitangaben in WEZ +2. Es ist jetzt 19:30 Uhr.