Klassischer Forenbaum, Sub-Tree selektieren

[Peter]

Tach auch,

ich benutze (leider) MySQL in der Version 4.0.18 - sub-selects sind daher nicht möglich.

Jetzt zum Problem:

Die klassische Forums-Tabelle mit im wesentlichen:

id
parentid
threadid
titel
text

Jedes Posting hat eine eindeutige id.
Außerdem die ID des Postings, auf das sich die Antwort bezieht (0 für das Startposting) als parentid.
Außerdem haben noch alle Postings eines Threads in der threadid die id des Ausgangspostings.

Wenn ich jetzt nur die id eines beliebigen Postings habe, möchte ich dazu rekursiv alle Antworten haben.

Wie bekomme ich das mit möglichst wenig DB-Anfragen hin?

Klar, ich kann im ersten Schritt alle die Postings selektieren, die die gegebene id als parent haben.
Im zweiten Schritt dann die, die eine der ids aus dem ersten Schritt als Parent haben.
Im dritten Schritt dann die, die eine der ids aus dem zweiten Schritt als Parent haben usw. bis ein Schritt keine Ergebnisse mehr bringt.

Das gibt also pro Antwortebene eine DB-Anfrage - nicht sehr effektiv.

Eine andere Möglichkeit wäre, daß ich mir den gesamten Thread hole
per
SELECT f.id, f.parentid, f.threadid FROM forumtable as f LEFT JOIN forumtable as t ON f.threadid = t.threadid WHERE t.id = 4711;
und dann die parentid-Einträge in der Programmlogik durchsuche.

Das gibt zwar erstmal nur eine DB-Anfrage, aber bei Riesen-Threads, aus denen nur ein winziger Sub-Tree gebraucht wird, wird haufenweise Zeugs von der DB zum Programm übertragen, nur um dann weggeschmissen zu werden.

Meine Frage: gibt es - ohne Subselects - eine Möglichkeit, mit einer DB-Abfrage den gesamten Subtree zu erwischen?
(von mir aus auch 2 - ich könnte mir vorstellen, daß erstmal eine benötigt wird, um die threadid zu bekommen)

Danke schon mal, bis später!
Peter

[Tom]

Hello,

ist das Design schon auf rekursiv festgenagelt?

Sonst liegt die Lösung vielleicht in der Einschränkung.

Ein einziges ID-Feld, dass pro Ebene nur eine bestimmte Anzahl Postings zulässt.

000001.001.001.001.001.001.001.

usw.

Dann benötigst Du zur Abfrage überhaupt keine Rekursion mehr.
Die schlimmste Beschränkung liegt dann aber in der Schachtelungstiefe.
Allerdings mag ich diese "Rechtsläufer-Threads" hier im Forum auch überhaupt nicht.
Durch etwas mehr Disziplin könnten viele davon wesentlich flacher bleiben und wären wahrscheinlich dann auch leichter lesbar.

Harzliche Grüße aus http://www.annerschbarrich.de

Tom

[Peter]

Tach,

ist das Design schon auf rekursiv festgenagelt?

Ja - es ist ein schon lange bestehendes System, das jetzt um einige Funktionalitäten erweitert werden soll. Gibt schon einige Hunderttausend Postings ...

Trotzdem danke für die Anregung.

Peter

[Tom]

Hello,

im Prinzip hat also jedes Mutterposting mit seinen Kindern und Kindeskindern einen eigenen Baum, oder? Wieviele Einzelpostings gehören denn maximal zu einem Mutterposting (ist das die ThreadID?)

Es wäre also möglich, das Probelem aus dem DBMS herauszulösen.

Selektiere alle Postings, die zum Mutterposting gehören.
Dazu ist nur ein einziges Query nötig.
Du benötigst ja nur Post_ID und Thread_ID (wenn ich das jetzt richtig verstanden habe)

Dann kannst Du Dir ein Array aufbauen mit diesen Daten.
In diesem Array musst Du dann "nur" den Einsprungspunkt suchen, der die gesuchte ID trägt und von dort aus tätig werden.

Wenn du disen Baum dann serialisiert hast, kannst Du das zweite Query mit dem Set der IDs abgeben, um die eigentlichen Daten zu beschaffen und diese ins Array einzuhängen.

Die rekursive Ausgabe des Arrays ist dann ein Kinderspiel.

Das ganze basiert also auf einem Wechselspiel zwischen Datenbank und Arbeitsspeicher und findet wahrscheinlich auch in der Begrenzug des Arbeitsspeichers seine Grenzen.

Du musst Dir aber ggf. Gedanken über die Synchronisation machen. Solange der Vorgang läuft, dürfen keine Postings verschoben werden in der Datenbank.

Harzliche Grüße aus http://www.annerschbarrich.de

Tom

[Christian Seiler]

Hallo Tom,

Ein einziges ID-Feld, dass pro Ebene nur eine bestimmte Anzahl Postings zulässt.
000001.001.001.001.001.001.001.

Dir ist klar, dass das zum einen unendlich viel Platz verschwendet und dass Abfragen auf ein derartiges ID-Feld elends lahm sind, sobald der Datenbestand etwas größer ist?

Die einzig sinnvolle alternative Datenstruktur (in einer relationalen Datenbank), die sich anböte, wären Nested Sets; allerdings sind Nested Sets nur schnell, wenn es ums Auslesen von Daten geht - wenn es ums Schreiben von Daten geht, werden diese bei zunehmender Größe der Bäume langsam (und die Sortierreihenfolge ist festgelegt).

Viele Grüße,
Christian

[Tom]

Hello,

Dir ist klar, dass das zum einen unendlich viel Platz verschwendet und dass Abfragen auf ein derartiges ID-Feld elends lahm sind, sobald der Datenbestand etwas größer ist?

Nö. Ist mir nicht klar.
Wenn das Feld eine fixe Länge hat, ist der Index mit 255 Zeichen Länge im Feld nicht messbar langsamer als der Index mit 20 Zeichen im Feld, vorausgesetzt natürlich, dass der Arbeitsspeicher für den Index-Algorithmus ausreicht und nicht geswapped werden muss.

Das mehr Platz benötigt wird, ist mir klar.

Ob der "verschwendet" wird, ist Philosophie.

Du kannst davon ausgehen, dass ich diese Technik bereits selber auf Faltfiles implementiert habe  und solange das Dateisystem mitspielte, beste Ergebnisse erzielt habe. Bis zuneiner Anzahl von ca. 13.000.000 Datensätzen hat das gut geklappt. Danach spielt meinen Seitenbildungs-Algorithmus noch nicht mit. Der braucht einfach ca. 21% Luft auf jeder Seite für sauberes Arbeiten.

Harzliche Grüße aus http://www.annerschbarrich.de

Tom

[Christian Seiler]

Hallo,

Dir ist klar, dass das zum einen unendlich viel Platz verschwendet und dass Abfragen auf ein derartiges ID-Feld elends lahm sind, sobald der Datenbestand etwas größer ist?

Nö. Ist mir nicht klar.
Wenn das Feld eine fixe Länge hat,

Unabhängig davon, dass die fixe Länge irrelevant ist: Wie soll das bei MySQL gehen? (siehe Ausgangsposting) MySQL wandelt CHAR(n) mit n > 4 automatisch in VARCHAR(n) um, siehe Manual.

ist der Index mit 255 Zeichen Länge im Feld nicht messbar langsamer als der Index mit 20 Zeichen im Feld,

Natürlich, solange Du ein konkretes Posting selektierst, ist das ganze auch kein Problem. Wenn Du jedoch alle Postings ab einer bestimmten Unterebene haben willst, kannst Du eben keinen Index verwenden und musst einen Full Table Scan machen - und das ist bei vielen Datensätzen sehr, sehr langsam.

Du kannst davon ausgehen, dass ich diese Technik bereits selber auf Faltfiles implementiert habe

Der Ausgangsposter redete hier von einer Datenbank und nicht von Flatfiles. Vergleiche bitte nicht Äpfel mit Birnen.

Viele Grüße,
Christian

[Tom]

Hello,

Unabhängig davon, dass die fixe Länge irrelevant ist: Wie soll das bei MySQL gehen? (siehe Ausgangsposting) MySQL wandelt CHAR(n) mit n > 4 automatisch in VARCHAR(n) um, siehe Manual.

Den Index auf das Feld auch? Das Feld selber interessiert ja eigentlich niemanden.

ist der Index mit 255 Zeichen Länge im Feld nicht messbar langsamer als der Index mit 20 Zeichen im Feld,

Natürlich, solange Du ein konkretes Posting selektierst, ist das ganze auch kein Problem. Wenn Du jedoch alle Postings ab einer bestimmten Unterebene haben willst, kannst Du eben keinen Index verwenden und musst einen Full Table Scan machen - und das ist bei vielen Datensätzen sehr, sehr langsam.

Wieso kann ich da keinen Index mehr verwenden?
Unterstüzt MySQL etwa so einfache Techniken wir "near" nicht?
Das wäre ja ein Armutszeugnis.

Wenn ich mit "Like feld%" über einen Index abfrage, wird der doch wohl vom Optimizer auch benutzt? Ich kann mir nicht vorstellen, dass die Entwickler von MySQL derartig simple Grenzbildungen einfch ignorieren.

Der Ausgangsposter redete hier von einer Datenbank und nicht von Flatfiles. Vergleiche bitte nicht Äpfel mit Birnen.

Kommt darauf an, was eher da war. Die Äpfel oder die Birnen. Wenn ein Thomas Schmieder das in seinem Flatfilesystem berücksichtigen kann (ich bin doch hier der Doofe *g*, oder?) dann werden doch die hochschlauen Erzeuger von MySQL das schon lange gekonnt haben, oder? Pass auf, was Du jetzt antwortet, damit Du Dir von MySQL AB keine faulen Eier einfängst. *ggg*

Harzliche Grüße aus http://www.annerschbarrich.de

Tom

[Christian Seiler]

Hallo Tom,

Wenn Du jedoch alle Postings ab einer bestimmten Unterebene haben willst, kannst Du eben keinen Index verwenden und musst einen Full Table Scan machen - und das ist bei vielen Datensätzen sehr, sehr langsam.

Ich korrigiere mich, meine Erfahrung war, dass DMBSe immer einen Full Table Scan gemacht haben (das kann aber an meiner sonstigen Abfrage / am Füllstand der Tabelle gelegen haben), es geht auch mit einem Index.

Nichtdestotrotz stellt Deine Struktur unnötige künstliche Limits für die Daten dar: Maximaltiefe, maximale Anzahl an Antworten auf ein Posting. Und je weiter man die Limits ausdehnt, desto mehr Platz braucht Dein System - die anderen beiden Systeme (Nested Sets, ParentID) skalieren da _deutlich_ besser.

Viele Grüße,
Christian

[Tom]

Hello,

Nichtdestotrotz stellt Deine Struktur unnötige künstliche Limits für die Daten dar: Maximaltiefe, maximale Anzahl an Antworten auf ein Posting. Und je weiter man die Limits ausdehnt, desto mehr Platz braucht Dein System - die anderen beiden Systeme (Nested Sets, ParentID) skalieren da _deutlich_ besser.

Das sage ich ja, dass Wertebereiche/Nummernkreise vorhanden sind.

Wenn die aber in das allgemeine Bild passen, ist das schneller, als nested Sets.
Allerdings stammen meine Erfahrungen schon aus der Zeit von 1984. Könnte ja sein, dass die heutre nicht mehr gelten ;-))

Harzliche Grüße aus http://www.annerschbarrich.de

Tom

[MudGuard]

Hi,

Wenn das Feld eine fixe Länge hat, ist der Index mit 255 Zeichen Länge im Feld nicht messbar langsamer als der Index mit 20 Zeichen im Feld, vorausgesetzt natürlich, dass der Arbeitsspeicher für den Index-Algorithmus ausreicht und nicht geswapped werden muss.

Solange nur eine ID wie bei Peter vorgesehen drinsteht, reicht vermutlich ein integer (bevor die IDs ausgehen, wird wohl eher die Tabellengröße aus dem Ruder laufen).
Bei Deiner Variante muß es ein String sein.
Bei den heutzutage üblichen Computern ist es so, daß Integers schneller und einfacher verarbeitet werden können als Strings.

cu,
Andreas

[Tom]

Hello,

Bei Deiner Variante muß es ein String sein.
Bei den heutzutage üblichen Computern ist es so, daß Integers schneller und einfacher verarbeitet werden können als Strings.

Wie kommst Du drauf, dass man von meiner Variante kein Integer-Äquivalent bilden könnte? Hängt doch immer vom Wertebereich ab.

Harzliche Grüße aus http://www.annerschbarrich.de

Tom

[MudGuard]

Hi,

Bei Deiner Variante muß es ein String sein.
Bei den heutzutage üblichen Computern ist es so, daß Integers schneller und einfacher verarbeitet werden können als Strings.
Wie kommst Du drauf, dass man von meiner Variante kein Integer-Äquivalent bilden könnte? Hängt doch immer vom Wertebereich ab.

Mit den heutzutage üblichen Integer-Größen nur mit extremer Einschränkung der Ebenen/Antworten pro Postings, so daß das nur in extremen Ausnahmefällen überhaupt anwendbar ist. Ein Forum - das ist ja das, worum es hier im Thread geht - ist kein solcher extremer Ausnahmefall.

cu,
Andreas

[Christian Seiler]

Hallo,

Wie bekomme ich das mit möglichst wenig DB-Anfragen hin?

Du hast schon die beiden einzigen Möglichkeiten bei gegebener Datenstruktur beschrieben, die es gibt.

Allerdings könntest Du Dir das Leben einfacher machen, indem Du erst nur id und parentid aus dem Thread extrahierst, dort dann per Programmlogik alle IDs rausfischst, die Du brauchst und dann SELECT * FROM postings WHERE id IN (1, 2, 3, ...) machst. Dann würde wirklich nur das allernötigste zwischen der Datenbank und Deinem Script transferiert werden und Du hättest nur 2 Datenbankabfragen. Die andere Methode (mehrere SELECTs) ist nur dann effizient, wenn Du nur eine Handvoll Unterebenen hast - was bei einem Forum nicht der Fall sein dürfte.

Viele Grüße,
Christian

[Peter]

Tach,

Wie bekomme ich das mit möglichst wenig DB-Anfragen hin?
Du hast schon die beiden einzigen Möglichkeiten bei gegebener Datenstruktur beschrieben, die es gibt.

Ok, danke für die Bestätigung, dann werd ich wohl die zweite Version nehmen.

Allerdings könntest Du Dir das Leben einfacher machen, indem Du erst nur id und parentid aus dem Thread extrahierst, dort dann per Programmlogik alle IDs rausfischst, die Du brauchst und dann SELECT * FROM postings WHERE id IN (1, 2, 3, ...) machst.

Das werde ich nicht tun - zumindest das mit dem SELECT * ...

Es geht einerseits darum, einen Subtree zu löschen - da brauch ich nicht erst alles selektieren, andrerseits darum, aus einem Subtree einen eigenständigen Thread - da muß nur beim Anfangsposting die parentid auf 0 und bei allen Nachfahren die threadid gesetzt werden - die restlichen Daten sind ebenfalls nicht nötig.

Peter