(PERL)Suchmaschienen-Stuktur

[Michael Schröpl]

Hi Andres,

Technische Mittel zur Umsetztung (eigentlich irellevant, oder?):
-Postgre oder Mysql je nach Einsatzort

wenn Du Deine Tabellen selbst bauen willst (also kein mySQL-FULLTEXT etc.), sollte das egal sein.

2: es gibt jeweils eine Tabelle für Wortanfänge mit aa, ab, ac,...zz und eine Tabelle für Sonderzeichen (Ja, ich weiß, dass das viele Tabellen werden)

Ich verstehe, daß Du die jeweilige Datenmenge klein halten willst; aber wenn Du über die Worte einen Indexbaum legst, dann macht die Datenbank das von ganz alleine. Ich vermute, Du wirst einen sehr kleinen Performance-Gewinn erzielen, aber die Wartung Deiner Datenstrukturen nicht gerade vereinfachen.
Wo eine solche Idee gut funktionieren könnte, das wäre ein Ansatz, der die Suchmaschine auf mehrere Rechner verteilen würde (bei seeeehr großen Datenmengen - Deine 500 MB reichen dafür noch nicht).

4: um eine präfix-Suche zu ermöglichen, wird jedes Wort mit mehr als drei Buchstaben, von vorne gekürzt, dh. in der DB steht dann z.B. Hallo, allo und llo.

Du meinst "Substring" statt "Präfix", ja? (Präfix-Suche auf Postfixe ist Substring auf Worte.)

5: In der Suchmaschiene steht statt Sonderzeichen wie ä immer ae usw, um die verschiedenen Schreibweisen zu berücksichtigen.

Hm. Warum nicht das Wort mit Umlaut zweimal indexen? So oft kommt das ja nicht vor.

7: Weitere Spalten enthalten, falls vorhanden und notwendig, zusätliche Informationen wie Datum, kategorie, autor......

Hm. Deine nachfolgende Frage zeigt Dir das Problem ja selber: Konsistenz durch redundanzfreie Datenhaltung.

8: Um ein ranking zu erhalten wird zuerst nach exakt dem Suchbegriff gesucht, später auch nach solche mit einem Anhängsel (Postfix mittels %) dann auch indem jetzt auch nach Wörtern gesucht wird bei denen eine 1 bei postfix steht, auch nach präfixen.

Dazu kann ich nur "spannend" sagen. Ranking ist Magie - und sehr datenabhängig, fürchte ich.

9: in der WHERE Klausel wird zuerst nach (falls vorhanden) Kategorie, autor, erstellungsdatum usw. gesucht, um die Geschwindigkeit zu erhöhen.

Das kannst Du vergessen. Die Geschwindigkeit hängt nicht von der Reihenfolge der WHERE-Terme ab, sondern vor allem von der Verwendung verfügbarer Indexe. (Und täte sie es, dann würde jeder ordentliche Query Optimizer die Terme besser sortieren können als Du selbst.)

10: Um die Wortnmenge nicht ganz so hoch werden zu lassen werden begriffe wie 'und', 'die', Zahlen generell usw nicht eingetragen.

Die erzielbare Einsparung durch solche Maßnahmen solltest Du auch nicht überschätzen. Laß es 10-15% sein, das wäre schon recht ordentlich. Und da Du dann noch den Logarithmus auf die Änderung anwenden mußt, ist der erzielbare Geschwindigkeitsgewinn kaum noch meßbar. (Beim Platzbedarf schlagen diese Prozente hingegen voll durch.)

a: Habt ihr Verbesserungsvorschläge, Kritik, Fragen zur generellen Struktur?

Ich glaube nicht an das Prinzip mit den vielen Tabellen - es sei denn, bei Verteilung auf viele Maschinen. Aber auch dann würde man eine besser streuende Hash-Funktion nehmen und nicht die extrem ungleich verteilten Anfangs-Buchstabenpaare.
Ich habe allerdings selbst ein vergleichbares Prinzip implementiert - allerdings nicht mit lexikographischer Unterteilung, sondern mit inhaltlicher. Also beispielsweise eine Tabelle aller Nachrichten von heute, eine für gestern, eine für diese Woche, eine für diesen Monat etc. - weil es Erfahrungswerte für die Verteilung der Abfragen in dieser Dimension gibt. (Und vor allem, weil ich über diese Teilmengen _auch_ full table scans brauche.)

b: Zu 7, oder sollten diese ganzen Informationen in eine zusätzliche Tabelle? Wäre zwar sinvoll, aber machen die zusätzlichen Kosten für die Abfragen nicht den Vorteil zunichte?

Tja, das ist ein trade-off zwischen Performance und Wartbarkeit. Wenn Dein Tabellensystem nicht der Primärdatenträger ist, sondern aus diesem lediglich wie ein Cache geladen wird, dann kann das Sinn machen.

c: Zu 10, oder sollten diese Wörter nur mit einem anderem Wort zusammen suchbar sein? Oder wie z.B. bei Google nur mit einem '+' davor?

Auch das ist "Magie". Solche Entscheidungen kannst Du in einer sehr späten Designphase treffen, ggf. sogar erst nach einer ersten Implementierung. Wie Dein GUI _aussieht_, ist erst später wichtig - aber welche Semantik es umsetzen soll, das mußt Du schon beim Tabellenentwurf wissen.

d: Wie soll ich suchen wenn mehr als ein Suchbegriff eingegeben wird? Soll ich suchen welche das gleich Ziel haben, und diese nach dem zweiten Suchbegriffdurchsuchen? Oder das Ziel des ersten Suchbegriffes über Perl öffnen und mittels Regexen durchsuchen?

Genau darüber haben Andreas und ich lange diskutiert. ;-)
Das Problem ist: Wenn beide Terme viele Ergebnisse liefern, dann wird das JOIN zwischen beiden mörderisch und macht die schöne Indexstruktur wertlos.
Mein Vorschlag dazu war es, eine Meßfunktion für die Projektivität der Terme zu haben (die selbst dann möglichst wenig kosten darf) und damit Performance-Katastrophen wenigstens erkennen kann.

e: Macht es Sinn die Reihenfolge der where Klausel nach Länge der der Suchbegriffe zu sortieren? So dass lange, da sie vermutlich seltener vorhanden sind, zuerst gesucht werden?

Das hängt vom verwendeten RDBMS ab - ich würde aber pauschal "nein" sagen.

Bedenke auch, daß Du dann ggf. den längeren Term sehr oft prüfen lassen mußt, was ja schließlich auch etwas kostet ... wenn Du mit dem ersten Term über den Index einsteigst und von dort aus eine Schleife ansteuerst, den zweiten Term auszuwerten, _kann_ das eventuell prima sein - nur nutzt Du dann für den zweiten Term Deine Indextzstruktur überhaupt nicht mehr.

Viele Grüße
      Michael