3. Forumsuche -> Verbesserungsvorschläge

Forumsuche -> Verbesserungsvorschläge

  • J

    Die phpBB-Suche packt ein % in den Suchstring und delegiert das Problem mittels "WHERE blablabl LIKE "tes*" an die mySQL-Datenbank weiter. 🙂

    Die UND-Verknüpfung stelle ich mir in dieser Weise problematisch vor... genau das macht die phpBB-Suche derzeit auch. Leider führt das dazu, man keine Ergebnisse kriegt, wenn man ein häufiges und ein seltenes Wort sucht, da aus Performance-Gründen nur die ersten x Treffer in die Liste aufgenommen werden.

    0
  • M

    Wow, aber unser Index hat ja jetzt schon 30 Mio Einträge oder, der wird mit so einer Idee ja nicht wirklich kleiner.

    0
  • T

    Jester schrieb:

    Die phpBB-Suche packt ein % in den Suchstring und delegiert das Problem mittels "WHERE blablabl LIKE "tes*" an die mySQL-Datenbank weiter. 🙂

    Die UND-Verknüpfung stelle ich mir in dieser Weise problematisch vor... genau das macht die phpBB-Suche derzeit auch. Leider führt das dazu, man keine Ergebnisse kriegt, wenn man ein häufiges und ein seltenes Wort sucht, da aus Performance-Gründen nur die ersten x Treffer in die Liste aufgenommen werden.

    Und dann geht er 30 Mio Einträge mit einem Full-Table-Scan durch? 😮
    Kein Wunder musstet ihr das deaktivieren...

    Das mit der UND-Verknüpfung ist aber in der Tat problematisch ich nehm da halt auch nur ne begrenzte Anzahl (5000) und durch die Vorsortierung werden auch nur die relevanteren genommen. Will man aber alle durchgehen, dauert das einfach zu lang (ist aber bestimmt in C++ schneller als in PHP 😉 ).

    Marc++us schrieb:

    Wow, aber unser Index hat ja jetzt schon 30 Mio Einträge oder, der wird mit so einer Idee ja nicht wirklich kleiner.

    Jepp, das ist da natürlich schon ein Problem. Habe mal so 400MB Textdaten indiziert und es ist ein 4GB großer Index herausgekommen. Natürlich steigt die Indexgröße auch immer langsamer an, weil Wörter öfters indiziert werden.
    Hier wird halt Performance durch mehr Speicherplatzverbrauch erkauft - Sollte heutzutage kein Problem mehr sein...

    0
  • J

    Tobias3 schrieb:

    Das mit der UND-Verknüpfung ist aber in der Tat problematisch ich nehm da halt auch nur ne begrenzte Anzahl (5000) und durch die Vorsortierung werden auch nur die relevanteren genommen. Will man aber alle durchgehen, dauert das einfach zu lang (ist aber bestimmt in C++ schneller als in PHP 😉 ).

    wie machst du die Relevanz-Sortierung?

    edit: ich halte es nicht für sehr realistisch, die suche auf C++ umzustellen, das birgt imo zuviele Risiken. aber wenn du lust hast dich bezüglich der Suchfunktion zu engagieren, schreib mir mal ne mail (über das profil).

    0
  • B

    Wie wichtig sind eigentlich Wildchars? Eventuell könnte man mit einem metrischen Baum und der Editierdistanz etwas effizientes machen nur vertragen sich Wildchar und Editierdistanz so weit ich weiß nicht wirklich.

    Ob man die Und-Verknüpfung effizient implementiert kriegt, weiß ich nicht. Ich kenne mich nicht genug mit den einzelnen Bäumen aus um das zu beurteilen.

    0
  • J

    ich denke wildcards sind schon interessant. allerdings würde ich nicht die UND-Verknüpfung dafür opfern wollen. editierdistanz klingt für mich nicht gerade nach höchster effizienz, obwohl's natürlich trotzdem nett wäre. Allerdings scheint mir Editierdistanz noch freier zu sein als wildcards... da sagt man wenigstens schonmal wo die unterschiede sind.

    0
  • T

    Jester schrieb:

    wie machst du die Relevanz-Sortierung?

    Bei einem Forum das nicht über so etwas geschicktes wie einen Pagerank verfügt, kommt da eigentlich nur die Häufigkeit des Stichwortes und die Position also entweder Titel und Beitragstext in Frage.
    Also zuerst alle Suchbegriffe im Titel und dann erst die im Beitragstext.

    Wegen der Editierdistanz:
    Das geht glaub ich sogar recht effizient - also man hasht quasi die Suchbegriffe, so dass Suchbegriffe mit Buchstabenverdrehern den selben Hash haben.
    Aber wenn ich von meinen Suchgewohnheiten ausgehe brauche ich eher die *Suchbegriff* Wildcards. Soll ja keine Rechtschreibhilfe sein...

    Ich glaube google und co. optimieren die verUNDung vorallem dadurch, dass sie Suchanfragen auswerten und dann die verUNDdete Begriffe in einen eigenen Index aufnehmen - anders kann ich mir das nicht vorstellen.

    So relevant ist das bei so einem vergleichsweise kleinem Datenbestand auch nun wieder nicht. Dann vergleicht man halt mal 100000 integer werte und sucht sich die raus die doppelt vorkommen.

    0
  • B

    Wie lange sind eigentlich die Stichwörter die es zu durchsuchen sind minimal, maximal und im Durchschnitt? Jetzt mal grob über den Daumen gepeilt würde ich auf 3, 8, 15 tippen aber eventuell liege ich da völlig daneben.

    Die Idee mit dem M-Baum stirb wohl schon an fehlenden frei zugänglichen und durch optimierten Standardimplementierungen. Die Forumsuche ist meiner Meinung nach den Aufwand einer Implementierung nicht wert. Die Editierdistanz zu berechnen sehe ich nicht als Problem da 8^2 noch human ist. Ich glaub eher, dass die Standard-Editierdistanz zu grobe ist, das heißt zu wenig verschiedene Werte liefert (alle werte liegen zwischen 0 bis 15 und sind ganzzahlig). Dadurch dürften die Strings alle nahe beieinander liegen und man kann sie nicht in Kugeln packen ohne dabei große Überlappungen zu verursachen.

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

    Man könnte natürlich versuchen bei den 30 Mio Einträgen ein paar weg zu schmeißen oder nur ein paar in den Index auf zu nehmen. Eventuell ist eine Kombi Lösung aus Index für häufig gesuchte Stichwörter und einem linearen Scan für den Rest eine Idee.

    Die Verundung ist natürlich ein Problem, allerdings fällt mir auf Anhieb keine Datenstruktur ein welche die effizient behandeln kann.

    0
  • J

    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.

    0
  • M

    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.

    0
  • B

    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?

    0
  • J

    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?

    0
  • T

    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.

    0
  • B

    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?

    0
  • T

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

    0
  • B

    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.

    0
  • N

    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.

    0
  • B

    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;
    0
  • N

    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…

    0
  • T

    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.

    0
Anmelden zum Antworten