Forumsuche -> Verbesserungsvorschläge

[Jester]

Tobias3 schrieb:

Das geht glaub ich sogar recht effizient - also man hasht quasi die Suchbegriffe, so dass Suchbegriffe mit Buchstabenverdrehern den selben Hash haben.

das heißt hash(abc) = hash(bac) = hash(acb) und hups, das könnten ja auch wörter sein, also wieder beliebig vertauschen... = hash(cab) = hash(cba), also bildest du nur noch einen hash über das anagram. Oder wie darf ich das verstehen?

@Ben04: zwischen 3 und 8 ist denke ich realistisch, die Daten habe ich derzeit zwar nicht, kann ich aber sicher bekommen. 8^2 ist zwar nicht riesig, aber auch nicht zu vernachlässigen. Das kann den Unterschied zwischen funktioniert zügig und Suche ist zu langsam bedeuten.

Aber letztlich sind das hier alles theoretische Überlegungen. Die Randbedingungen sind im Wesentlichen wie folgt: Wir haben eine mySQL-Datenbank, in der ein Index liegt. Die müssen wir via PHP mit geeigneten Suchanfragen versorgen. Eine C++-Implementierung irgendwelcher toller Datenstrukturen ist sicher eine wunderbare Lösung, aber leider nicht für dieses Problem.

Die Hauptaufgaben sehe ich derzeit in folgenden Bereichen:

1. Die SQL-Abfragen so umschreiben, dass sie für mySQL leichter verdaulich sind.
2. Den Index bzw. den Indexer so überarbeiten, dass ein besserer Index herauskommt. Dabei kann kleiner gleichzeitig auch besser bedeuten: entfernen von unnötigen Wortendungen und ähnlichem verbessert auch die Qualität der Suchergebnisse

zu 1) habe ich schon einiges gemacht. allerdings läuft es immer noch nicht vernünftig. ich werde mich demnächst mal auf die Suche nach dem genauen Flaschenhals machen.

Ein großes Problem ist der Code vom phpBB, der ist so furchtbar und unaufgeräumt, dass jede Änderung eine Qual ist.

[Marc++us]

Tobias3 schrieb:

(ist aber bestimmt in C++ schneller als in PHP ).

Glaube ich kaum, da das Bottleneck die Datenbank ist, bzw. die Geschwindigkeit der Festplatten.

[Ben04]

Wie wäre es mit folgendem Ansatz:
Die volle Stichwortliste wird nach dem String geordnet damit Anfragen ohne Wildcard schnell sind. Das müsste die mySQL-DB doch hinkriegen oder?

Sämtliche Stichwörter nach denen mal gesucht wurde werden in einer Liste gespeichert. Diese ist chronologisch geordnet und wird bei Bedarf einfach unten abgeschnitten. Wildcardsuche beschränkt sich auf diese Stichwörter.

Wird diese Liste klein gehalten kann man Wildcards mit einem Linearen Scan implementieren (so wie das jetzt schon der Fall ist). Ansonsten muss man eventuell auf Tobias3s Ansatz zurück greifen. Hierfür wäre ein cron-Job welcher die Pre- und/oder Postfix Tabellen neu generiert wahrscheinlich eine gute Idee. Wie man eine solche Tabelle am besten bei mySQL umsetzt weiß ich nicht.

Im Endeffekt ist es ja nur eine Abbildung String => ID. Wahrscheinlich reicht es dem String eine Obergrenze für die Länge zu geben und zum Primary-Key zu erklären. Kann man dem SQL irgendwie sagen, dass er Zeilen beliebig umordnen kann?

[Jester]

Natürlich der string ist sowieso primary-key in der stichwort-tabelle, die anfragen darin sind ziemlich sicher schnell. Eigentlich kann mySQL ja auch wildcards...

ich denke, um bei kleinen schritten zu bleiben könnten wir zunächst auch ohne wildcards arbeiten. Insbesondere im Hinblick darauf, dass wir mit einem verbesserten Index auch wildcards weniger nötig haben. Eigentlich gibt es nämlich keinen Grund, warum man mit "*main*" viel mehr finden sollte als mit "main".

Caching zur Verbesserung der Performance ist sicher eine gute Idee. Ich bin mir allerdings nicht sicher, wie gut es ist die Ergebnisse davon abhängig zu machen, was zuvor häufig gesucht wurde. Das ist dann schlecht reproduzierbar und erschwert die Fehlersuche. Sowas ist auf jeden Fall mit Vorsicht zu genießen.

Generell würde ich sagen: UND-Operation ist die wichtigste, Wildcards sind nice-to-have, aber nicht eminent wichtig. da verspreche ich mir von einem aufgeräumten Index mehr. Marc++us, wie siehst Du das?

[Tobias3]

Ben04 schrieb:

Tobias3s Ansatz erlaubt wenn ich das richtig sehe nur Wildcards am Anfang und am Ende. Wenn das kein Problem ist dann ist er wahrscheinlich nicht schlecht. Ich würde jedoch auf Hashtabellen zurückgreifen und nicht auf eine sortierte Liste und je eine für Prefixe und Postfixe anlegen.

Für ein Wort der Länge n sind das etwa 2*n Einträge, also etwa 16. Da ein Eintrag jedoch etwa nur aus 2 Pointer/IDs und dem String selbst besteht würde ich mal sagen, dass die Indexstruktur etwa 24Byte pro Eintrag braucht. Bei 30 Mio Einträgen komme ich auf etwa 10 GB allein für die Indexstruktur. Klingt nach viel aber für 30 Mio Einträgen und einer schnelle Suche ist das glaub ich drunter zu haben.

Jepp, erlaubt nur Wildcards am Anfang und am Ende. In der Mitte nicht. Man muss die wildcards auch nicht mit angeben, die Suchergebnisse mit Wildcards werden automatisch nach den exakten Ergebnissen ausgegeben.

Mein Anstatz braucht ja pro Key nur n Einträge, also braucht er die Hälfte der Datenmenge.
bei 15 Mio Einträgen braucht er bei der binären Suche ca. 20 Vergleiche. Nun sind nur Festplattenzugriffe relevant. D.h. die ersten 4 Stufen werden gecached -> 16 Zugriffe. Und vllt. sind die letzten 3 Zugriffe und das Scannen nach Wörtern mit selbem Präfix im selben Sektor -> 14 Zugriffe.
Mein Verfahren lohnt sich also bei so viel Einträgen noch. Bei mehr könnte sich allerdings wirklich Hashen lohnen.
Hashing benötigt immer 2*n Festplattenzugriffe.

Jester schrieb:

das heißt hash(abc) = hash(bac) = hash(acb) und hups, das könnten ja auch wörter sein, also wieder beliebig vertauschen... = hash(cab) = hash(cba), also bildest du nur noch einen hash über das anagram. Oder wie darf ich das verstehen?

Meinte eher so was wie http://de.wikipedia.org/wiki/Soundex aber wahrscheinlich gibts da wirklich zu große Buckets.

[Badestrand]

Nur mal ne Zwischenfrage: Wenn noch mit der originalen phpBB-Suche gearbeitet wird, wieviele Einträge hat denn die phpbb_search_worldlist-Tabelle? Und die 30 Mio Einträge beziehen sich auf die phpbb_search_wordmatch-Tabelle?

[Tobias3]

Nachdem sich Jester schon ne Zeit lang nicht zurückgemeldet hat führ ich hier mal vor, wie das aussehen würde.

Habe das Programm schon mal für ein anderes Projekt gebraucht und hab mal ein klein wenig von c-plusplus.net indexiert:

http://urpc.dyndns.org/bbsuche/

Bitte bei der Beurteilung der Geschwindigkeit berücksichtigen, dass das ganze auf einem Laptop mit Pentium III 500 Mhz läuft. Die Zugriffszeiten der Festplatte dürften deswegen auch nicht optimal sein.

Ich finde schon mit dem kleinen Index gibt es gute Suchergebnisse (neuere Beiträge sind nicht indexiert).

[Badestrand]

Yeah, was ich besonders super finde: Es wird bei Threads, welche sich über mehrere Seiten erstrecken, gleich auf die richtige Seite und zum richtigen Beitrag gesprungen. Das ist momentan eine ätzende Sucherei, in >5 Seiten das Schlüsselwort zu finden.

[nman]

Tobias3: Naja, klar gibts mit wenig Daten leicht brauchbare Performance.

Badestrand: phpbb_search_wordlist hat etwas über 1,1 Mio, die phpbb_search_wordmatch hat so um die 32 Mio.

[Badestrand]

Wenn für euch die Daten-Herausgabe OK wäre, du genug Zeit hast und irgendwo ausreichend Webspace findest, wäre es total cool, wenn du diese beiden Tabellen mal als csv dumpen und hosten würdest, dann könnte man (oder wenigstens ich :)) mal ein wenig damit herumexperimentieren.

edit: Um es komfortabler für dich zu machen, musst du nicht mal die Syntax nachschlagen (falls du sie nicht sowieso aus dem Kopf weißt):

SELECT * INTO OUTFILE '/.../wordlist.txt'
  FIELDS TERMINATED BY ';'
  LINES TERMINATED BY '\r\n'
  FROM phpbb.phpbb_search_wordlist;

SELECT * INTO OUTFILE '/.../wordmatch.txt'
  FIELDS TERMINATED BY ';'
  LINES TERMINATED BY '\r\n'
  FROM phpbb.phpbb_search_wordmatch;

[nman]

Badestrand schrieb:

edit: Um es komfortabler für dich zu machen, musst du nicht mal die Syntax nachschlagen (falls du sie nicht sowieso aus dem Kopf weißt):

Danke, das ist sehr nett, das macht es auf alle Fälle nochmal bequemer.

Aber schreibst Du mal eine Mail an admin@c++.de? Das ist eine Sache, die Marcus entscheiden muss, ist ein wenig heikel…

[Tobias3]

nman schrieb:

Tobias3: Naja, klar gibts mit wenig Daten leicht brauchbare Performance.

Badestrand: phpbb_search_wordlist hat etwas über 1,1 Mio, die phpbb_search_wordmatch hat so um die 32 Mio.

Durch die partiellen Einträge hat der Index von oben 11 057 526 Einträge. Ich kann auch noch alles indexieren, weiß aber nicht, ob das so gut ist, wenn ich hier so viel Traffic erzeuge (wäre allerdings über Nacht...).

Ich weiß halt, dass man mit der orig. MySQL Datenbank nie an die Performance von oben hinkommt - dann nur mit dem MySQL-Fulltext-Search und da kann man wiederum keine Wildcards verwenden.

Gebt mal oben "C java" ein und sucht: Er findet sinnvolle Sachen. (Was man bei der orig. Forensuche nicht behaupten kann.

[Marc++us]

Tobias3 schrieb:

Gebt mal oben "C java" ein und sucht: Er findet sinnvolle Sachen. (Was man bei der orig. Forensuche nicht behaupten kann.

Zumindest nach dem Coloring nicht:

Hallo, ich hoffe es ist hier das richtige Forum, da ich ja von JAVA zu C portieren
will... Ich habe folgenden JAVA code,...

Oder ist das nur ein Färbefehler der Ausgabe, und Du hast in Wirklichkeit die "c" im "ich" gar nicht gefunden

[Tobias3]

Marc++us schrieb:

Tobias3 schrieb:

Gebt mal oben "C java" ein und sucht: Er findet sinnvolle Sachen. (Was man bei der orig. Forensuche nicht behaupten kann.

Zumindest nach dem Coloring nicht:

Hallo, ich hoffe es ist hier das richtige Forum, da ich ja von JAVA zu C portieren
will... Ich habe folgenden JAVA code,...

Oder ist das nur ein Färbefehler der Ausgabe, und Du hast in Wirklichkeit die "c" im "ich" gar nicht gefunden

Die "Wildcards" sind natürlich per default dabei, d.h. das C im ich wird gefunden allerdings nicht so hoch gewertet, wie ein alleinstehendes C.
Ist ja nur logisch. Zuerst kommen die Suchergebnisse mit exakten Ergebnissen, dann mit partiellen Matches. In dem Fall hat halt noch das Suchergebnis mit exaktem Treffer partielle Ergebnisse.

[Tobias3]

Ich weiß ja nicht wie ihr das seht aber ich fände es wichtig, dass man auf diesem Gebiet arbeitet.
Offensichtlich braucht die Suchfunktion viel CPU-Power sonst würden bekannte Foren, wie z.B. linuxforen.de o.ä. die Suchfunktion für nicht registrierte Benutzer nicht deaktivieren.
Das finde ich übrigens abscheulich - einerseits sich darüber beschweren, dass keiner die Suchfunktion benutzt und andererseits so was...
Noch schlimmer finde ich die Captachas, die man inzwischen manchmal an dieser Stelle auffindet.

Ich würde konkret folgendes vorschlagen:
Die oben genannte URL wird anstatt der google-Suche eingebettet (halt noch mit Auswahl ob man nur im Titel suchen will und in welchem Unterforum). Ich verbessere das Programm soweit, dass es möglichst bugfrei ist und performancemäßig passt. Dann sehen wir einfach weiter - ich hätte auch kein Problem damit den Sourcecode weiterzugeben...

[Tobias3]

Ich weiß ja auch nicht wieso ich keine Antwort hier bekomme. Es wäre nett wenn man wenigstens Ablehnen würde, vllt. weil der Aufwand zu groß ist oder so.

Das wäre akzeptierbar, allerdings nicht anzuraten:

z.B. hatte ich vor ner Zeit ein Problem, dass sich mal ausnahmsweise nicht durch durchsuchen von Foren/Google lösen lies. Bei einer Windowsanwenung erstellt mit Borland C++ Builder unter Vista flackerte die Fortschrittsanzeige.
Wenn jetzt jemand das selbe Problem hat - nämlich jemand der eine Anwendung mit Forschrittsbalken unter Vista mal getestet hat - dann sucht er hoffentlich erst mal im Forum.
Er beschränkt das Subforum natürlich auf VCL. Dann gibt er vllt. ein:
Vista Fortschrittsanzeige
Vista ProgressBar
Progressbar flackern

Die Suchfunktion findet mit keiner Suchanfrage nichts, mit google(im Forum) auch nicht. Wahrscheinlich liegt das ganze gerade an Bug #3 und wird bald behoben. Aber meine Suche ist schon mal besser als die von google, denn sie findet für die 2 unteren Suchbegriffe den gewünschten Eintrag und für den oberen liefert sie bei "Vista Fortschritt" das richtige zurück - für objektivere Test bin ich gerne offen. Allerdings müsste ich dafür vorher das ganze Forum indizieren.
Also könnte man doch auf jeden Fall die google Suche damit ersetzen, oder?
Ich fände es nett, wenn ein Verantworlicher seine Meinung dazu äußern würde.

[scrub]

Versuch einfach, Deine Vorstellung von Reaktionszeit hier um den Faktor 100 zu steigern. Es dauert halt manchmal ein bißchen.

[Jester]

Ich hab das Thema im Moderatoren-Forum nochmal angestoßen. Es kann allerdings trotzdem eine Weile dauern, schließlich sind viele von uns berufstätig oder anderweitig stark eingebunden.

Damit's trotzdem irgendwie vorangeht antizipiere ich einfach mal ein paar Fragen, die mit Sicherheit gestellt werden:

Kannst Du vielleicht noch ein paar Details nennen? Wieviele Beiträge sind derzeit indexiert? Wie groß ist die Suchtabelle dafür? Wie funktioniert das Programm? Hält es die Tabelle die ganze Zeit im Speicher? Wieviel Speicher würde ein kompletter Index des Forums ungefähr benötigen? Kannst Du die Suchzeiten dafür schätzen?

[nman]

Tobias3: Sorry, aber hier dauert alles einfach ein bisschen länger.

Noch eine Frage für Jesters Katalog: Welche Voraussetzungen hat Deine Suche an den Server softwareseitig? (Libraries, DB, …)

[Tobias3]

ok, hier ein paar Details:

-Es sind 922583 Beiträge und 129241 Themen indexiert. Auf der Hauptseite wird eine Gesamtanzahl von 1365687 Beiträgen angezeigt, also sind bereits 67% der Beiträge im Index.
-Grundlegen besteht der Index aus 3 Dateien. Eine sqlite-Datenbank, die mit der o.g. Anzahl ca. 800MB groß ist und in der die Beiträge und Themen gespeichert sind, eine 85MB große Datei, die den Index für die Suchdatenbank darstellt und eine 2,88 GB große Datei in der die Suchbegriffe mitsamt ids der Nachrichten in der sie Vorkommen gelistet sind.
-Durch umkonfigurieren kann man alles so einstellen, dass nichts im Speicher ist - Es wird aber gecached.
-Ein komletter Index würde wohl dann kaum mehr Speicher brauchen, dann wäre die sqlite Datenbank etwas über 1GB groß, der Index vergrößert sich ja nicht linear also würde ich da etwas über 3GB schätzen
-Die Suchzeiten kann ich gut abschätzen: Wenn man momentan nach einem Zuchbegriff sucht der häufig vorkommt, dann erreicht man das Limit der maximalen Einträge, dann dauert eine Suche max. 1s (maximale Dauer für einen Suchbegriff) - diese Zeit ist beinahe linear mit der Anzahl der Suchbegriffe. Bitte hierbei berücksichtigen, dass das ganze auf einem PIII 500Mhz mit Laptopfestplatte läuft. Die Verlangsamung der binären Suche kann man ja Aufgrund von O(log n) bei einer Vergrößerung des Indexes beinahe vernachlässigen.
-Abhängig ist das ganze von Boost::Threads und sqlite3. Läuft auf linux und Windows.