DBI, Rekursion, prepared statements

[Cruz]

Hallo Allerseits,

Es ist ja bekannt, das man SQL queries, die man häufiger verwendet einmal preparen sollte,
um dann bei jeder verwendung mit execute die variablen einzubinden. Das geht dann nämlich viel schneller,
als den statement bei jeder benutzung neu zu preparen und zu executen.

Bei einem einfachen loop ist es ja kein Problem. Man preparet erstmal und bei jedem durchgang executet
man dann mit einer anderen Variable und loopt dann über die results mit fetchrow.

Die technik schein allerdings nicht für eine Rekursion zu funktionieren, weil dabei die preparierten
statements anscheinend irgendwie verloren gehen. Es funktioniert nur so lange, bis die Rekursion die
tiefste Ebene erreicht und zum ersten mal in ein Unterprogramm zurückspringt, von wo sie aufgeraufen
wurde.

Ok das ist ziemlich kompliziert, daher kommt jetzt mal ein plastisches beispiel. Hier ist ein eine
Routine, die eine auflistung von einem Kategoriebaum erstellt, typischerweise verwendet für
Verzeichnisstrukturen.

Als erstes preparen wir mal einen SQL query, der die Unterverzeichnisse zu dem übergegebenem Verzeichnis
ausgibt. Wir executen das dann mit der ID des übergebenen Verzeichnisses und wir erhalten die besagte
Liste der Unterverzeichnisse. Wir drehen eine Schleife um all die Unterverzeichnisse, und rufen die
selbe Funktion für jedes Unterverzeichnis aus, um auch deren Unterverzeichnisse aufzulisten.

generates a category_tree

sub open_all_categories
{
 my $parent = $_[0];

my $select = $dbh->prepare($sql);
 $select->execute($parent);
 if ($DBI::err) {&error($DBI::errstr)}

while ( ($cat_id, $category_name) = $select->fetchrow() )
 {

# add a line to the category tree
  $category_tree .= $category_name;

# follow recursion
  &open_all_categories($cat_id);
 }

$select->finish();
}

In dieser Form klappt das hervorragend. Allerdings wird hier jedes einzelne SQL query prepared.
Ich habe versucht den prepare() Aufruf aus der Funktion rauszunehmen und nur das execute() mit
der ID des Verzeichnisses drinzulassen. Dann passiert aber nur folgendes:

Die Funktion schlängelt sich durch solange sie über die gefundenen Verzeichnisse loopt oder sich
selbst aufruft, um eine Ebene tiefer zu gehen. Beim ersten "zurückspringen" auf einen höhere Ebene,
(d.h. keine Unterverzeichnisse gefunden) hört sie dann auf. Das preparte Statement scheint verloren
gegangen zu sein.

Hat jemand sowas schon mal hingekriegt?

Gruß
Cruz

[Michael Schröpl]

Hi Cruz,

Die Funktion schlängelt sich durch solange sie über die gefundenen Verzeichnisse loopt oder sich
selbst aufruft, um eine Ebene tiefer zu gehen. Beim ersten "zurückspringen" auf einen höhere Ebene,
(d.h. keine Unterverzeichnisse gefunden) hört sie dann auf. Das preparte Statement scheint verloren
gegangen zu sein.

ich kann mir gut vorstellen, daß das Probleme machen könnte.

Dein Programm führt ja _eine_ Session mit der mySQL-Datenbank.
Diese weiß nicht, daß Du ggf. dasselbe Statement aus mehreren Ebenen
abfeuern und damit parallele "prepares" vorrätig halten willst.

Die Frage ist einfach, nach welchen Kriterien mySQL Dich mehrere Statements
parallel im prepare-Zustand vorrätig halten läßt. Das kostet ja Ressourcen

• und zwar nicht Deinen Task, sondern den mySQL-daemon.
  Die Struktur innerhalb der Datenbank, die Deine vorbereiteten Statements
  speichern sollte, müßte genau wie Dein eigener Code reentrant sein (Deine
  Statement-Handles sind ja lokale und damit disjunkte Variablen - aber ihre
  Abbilder innerhalb des mySQL-Servers vielleicht nicht). Das wäre ggf. teuer.

Kannst Du Deinen Algorithmus so umgestalten, daß Du die Rückkehr aus der
Rekursion nicht brauchst?
(Beispielsweise, indem Du zuerst alle rows einer Ebene in einen Array auf-
sammelst und erst von diesem aus alle rekursiven Aufrufe fütterst. Das wäre
dann immer noch dieselbe Traversierungsreihenfolge in Deinem Baum.)

Viele Grüße
      Michael

[Cruz]

Hallo Michael,

nach weiterem Kopfzerbrechen meine ich den Grund dafür gefunden zu haben warum es nicht funktioniert, allerdings habe ich noch immer keine Lösung.

Wenn ich ein prepartes Statement mit einer Variable execute, dann kriege ich ein Resultset, worüber ich mit fetchrow loopen kann.
Innerhalb des loops execute ich das selbe preparte statement nochmal und dabei schmeißt denke ich mysql das erste Resultset weg, sodaß wenn meine Rekursion wieder an die Stelle zurück kehrt, nix mehr zum loopen übrig ist. Das deckt sich sehr gut mit deiner Theorie, nur mit dem Unterschied, nicht das preparierte Statement vorrätig gehalten wird, sondern das Resultset.
Also die Frage ist, wie kann ich ein Resultset aufheben? execute() gibt leider nix gescheites zurück, womit ich auf das Resultset referenzieren könnte.
Gut ich könnte nach jedem execute erstmal komplett durchloopen und alles in einem Array festhalten, aber irgendwie drängt es mich noch zu einer eleganteren Lösung. :)

Wenn ich die Rekursion ohne Rückkehr gestalte, dann brauche ich die Rekursion gar nicht mehr. Dann ist es nur noch ein sequentielles vorgehen von Ebene zu ebene und das würde viel komplizierter enden, weil ich immer darauf achten muss, wie ich die Ergebnisse der neuen Ebene einordne, damit es optisch auch die Baumstruktur ergibt.

Ciao,
Cruz

[Michael Schröpl]

Hi Cruz,

Gut ich könnte nach jedem execute erstmal komplett durchloopen
und alles in einem Array festhalten,

genau das wirst Du wohl tun müssen - eine nicht reentrante Datenstruktur
in eine reentrante übertragen.
Falls die dabei vorrätig zu haltenden Daten um Größenordnungen mehr
Platz benötigen als deren Primärschlüssel (oder bereits die kompletten
Daten eines Traversierungspfades inklusive der jeweils lokalen Listen
Deinen Hauptspeicher sprengen), könnte es sich im Extremfall sogar
lohnen, nur die Primärschlüssel zu speichern und die Zugriffe auf die
einzelnen Attribute bei Bedarf zu wiederholen. (Das würde natürlich
langsamer, aber ...)

aber irgendwie drängt es mich noch zu einer eleganteren Lösung. :)

Falls Du eine findest, würde sie mich durchaus interessieren. Ich sehe
da einen prinzipiellen Zusammenhang zwischen der Rekursionsfähigkeit
Deines Programms und der reentrant-Eigenschaft Deiner Datenstruktur.
Aber ich lerne auch gerne etwas dazu ...

Wenn ich die Rekursion ohne Rückkehr gestalte, dann brauche ich die
Rekursion gar nicht mehr. Dann ist es nur noch ein sequentielles
vorgehen von Ebene zu ebene und das würde viel komplizierter enden,
weil ich immer darauf achten muss, wie ich die Ergebnisse der neuen
Ebene einordne, damit es optisch auch die Baumstruktur ergibt.

Das kommt darauf an, was Du mit den Ergebnissen anfängst.
Du könntest Dir ja auch eine komplette Baumstruktur im Hauptspeicher
aufbauen (sofern das Deine verfügbaren Ressourcen nicht sprengt) und
diese erst am Ende komplett abarbeiten.
Aber offensichtlich möchtest Du die ressourcen-schonende depth-first-
Traversierung haben - und dafür brauchst Du eben Datenstrukturen mit
den entsprechenden Eigenschaften. Deine lokalen Variablen haben diese.

Viele Grüße
      Michael

P.S.: Wie breit sind eigentlich Deine Bäume? Bringt Dir das gecachete
      prepare() denn überhaupt meßbare Vorteile?
      Ich habe das bisher noch nicht genutzt (hm, könnte aber heute noch
      kommen ... meine Anwendung eignet sich eigentlich sehr dafür),
      würde aber damit rechnen, daß es erst ab einer bestimmten Anzahl
      von Wiederholungen etwas bringt. Das Anlegen der Struktur dürfte
      ja wohl einen gewissen Overhead kosten, oder?

[Cruz]

P.S.: Wie breit sind eigentlich Deine Bäume? Bringt Dir das gecachete prepare() denn überhaupt meßbare Vorteile?

Hi Michael,

eine elegantere Lösung, als mit fetchrow alle ergebnisse erstmal in einen array zu loopen habe ich nicht gefunden. Ich gebe jetzt auf danach zu suchen, weil es ziemlich hoffnungslos aussieht.

Ich habe aber die array lösung umgesetzt und performance tests durchgeführt. Als Testdaten  habe ich einen Kategoriebaum mit 59 Kategorien. Ich selecte nur sehr wenig Daten, und zwar einfach nur ids und Kategorienamen.
Das ist natürlich nur ein mikriges Testumfeld, wo man nur kaum merkbare Veränderungen der Laufzeit erzielen kann. Die durchschnittliche Laufzeit meines Skriptes beträgt 0.85 Sekunden und das beinhaltet nich nur die SQL Abfragen, sondern auch das Einlesen eines Templates, das Parsen von etwa 100 Variablen und die Ausgabe an den Browser. Ok jetzt kennst du das Umfeld, hier nun die Testergebnisse als Zahl:

Mit prepared statements zeigte das Skript einen eindeutigen Performanceanstieg um 0.03 Sekunden, das sind etwa 3% - 4% der gesamten Laufzeit.

Gut die 0.03 Sekunden machen die Kuh jetzt nicht fett, aber ich denke bei steigender Anzahl von Kategorien und selektierten Daten steigt auch der prozentuale Anteil des Performancegewinns. Bei komplexen Kategoriestrukturen mit einer hohen Userlast können es ganz schnell 3 - 4 Sekunden werden und die sind im Internet Gold wert.

Grüße
Cruz

[Michael Schröpl]

Hi Cruz,

aber ich denke bei steigender Anzahl von Kategorien und selektierten
Daten steigt auch der prozentuale Anteil des Performancegewinns.
Bei komplexen Kategoriestrukturen mit einer hohen Userlast können
es ganz schnell 3 - 4 Sekunden werden und die sind im Internet Gold
wert.

Das gerade glaube ich eben nicht.

Ich vermute, der _prozentuale_ Performance-Gewinn wird immer proportional
zur Breite Deines Baums sein, nicht zur Gesamtzahl der Knoten.

Der _absolute_ Performance-Gewinn mag in der Tat proportional zur absoluten
Größe des Baums sein, aber wenn der Baum so groß ist, daß 3-4% etwas aus-
machen, dann hast Du ohnehin ein Problem.

Viele Grüße
      Michael

[Cruz]

Ich vermute, der _prozentuale_ Performance-Gewinn wird immer proportional
zur Breite Deines Baums sein, nicht zur Gesamtzahl der Knoten.

Hi Michael,

ich glaube der Performance Gewinn hat sehr wohl etwas mit der Anzahl der Knoten zu tun, weil nämlich bei jedem Knoten ein neues Statement prepared wird und gerade da lohnt es sich ja. Je mehr Knoten, umso mehr prepared statements (d.h. jedesmal performance gewinn). Und je mehr Knoten, umso größer ist der Anteil der gesamten Laufzeit, d.h. der _prozentuale_ Gewinn müsste auch steigen.

Grüße,
Cruz

[Michael Schröpl]

Hi Cruz,

Ich vermute, der _prozentuale_ Performance-Gewinn wird immer proportional
zur Breite Deines Baums sein, nicht zur Gesamtzahl der Knoten.
ich glaube der Performance Gewinn hat sehr wohl etwas mit der Anzahl
der Knoten zu tun

der absolute, ja. Der relative, nein.

weil nämlich bei jedem Knoten ein neues Statement prepared wird und
gerade da lohnt es sich ja. Je mehr Knoten, umso mehr prepared
statements (d.h. jedesmal performance gewinn).

Ja.

Und je mehr Knoten, umso größer ist der Anteil der gesamten Laufzeit,

Nein. Wieso auch? Oder hat Dein Programm irgend einen nennenswerten
Grund-Overhead? Ich bin ganz automatisch davon ausgegangen, daß seine
Laufzeit O(n) bezüglich der Knotenzahl ist, da Du anscheinend den ganzen
Baum traversieren willst.

d.h. der _prozentuale_ Gewinn müsste auch steigen.

Wenn Du lauter binäre Knoten hast, dann spart das prepare relativ wenige
Operationen.
Hast Du aber eine Verzweigung von hunderten von Kind-Knoten pro Ebene
(etwa einen DOM-Baum eines HTML-Dokuments), dann reduzierst Du die Zahl
der Statement-Analysen von <n> auf 1. Das kann viel ausmachen - und genau
das ist der optimale Einsatzfall für Dein Vorgehen: Eine auf spezielle
Eigenschaften der Daten ausgelegte Optimierung.
Bei einem Baum mit einem Verzweigungsgrad von 1 (i. e. einer linearen
Liste) gewinnst Du _nichts_ - egal, wie groß oder klein der Baum ist.
Deshalb hängt der _relative_ Gewinn vom Verzweigungsgrad des Baums ab,
nicht von seiner Größe.
Deshalb fragte ich nach der mittleren Breite eines Knotens.

Insbesondere halte ich binäre Bäume für relativ häufig, und bei denen wäre
Dein Gewinn relativ klein. Deine Anwendung könnte natürlich 'degenerierte'
Daten haben - aber die von Dir genannten Zahlen lassen mich auf 'schlanke'
Bäume schließen.

Viele Grüße
      Michael