@leo's

Kann man Graphen und Bäume mit SQL durchsuchen? Ja, man kann. Wenn auch mit einigen Einschränkungen, insbesondere muss die Suchtiefe bereits von Beginn weg festgelegt werden.

Aber erst einmal von vorne. Ein Baum (oder Graph) wird in einer Datenbank meist in einer Tabelle abgelegt die über (mindestens) zwei Felder verfügt. Zum einen währen dies ein Feld für die ID des Elternknotens und ein Feld für die ID des Kindknotens. Jeder Knoten kann nun beliebig viele Einträge in dieser Tabelle haben.

Der erste Schritt ist nun noch sehr einfach. Um alle Knoten auf Level 1 zu durchsuchen brauchen wir nicht mehr als eine einfach SQL-Abfrage.

SELECT t.parent AS "Level 0", 
t.child AS "Level 1"
FROM tree AS t
WHERE t.parent = 1
AND t.child = 10;

Wenn wir nun bis Level 2 Durchsuchen wollen müssen wir die Tabelle mit sich selbst verknüpfen. 

SELECT t1.parent AS "Level 0", 
t2.parent AS "Level 1", 
t2.child AS "Level 2"
FROM tree AS t1
RIGHT OUTER JOIN tree t2
ON t1.child = t2.parent
WHERE t1.parent = 1
AND (t1.child = 10
t2.child = 10);

Das ganze kann man dann selbstverständlich nach belieben auf die Spitze treiben. Unten mit einer Suche bis zu Level 4.

SELECT t1.parent AS "Level 0", 
t2.parent AS "Level 1", 
t3.parent AS "Level 2", 
t4.parent AS "Level 3", 
t4.child AS "Level 4"
FROM tree AS t1
RIGHT OUTER JOIN tree t2
RIGHT OUTER JOIN tree t3
RIGHT OUTER JOIN tree t4
ON t3.child = t4.parent
ON t2.child = t3.parent
ON t1.child = t2.parent
WHERE t1.parent = 1
AND (t1.child = 10
OR t2.child = 10
OR i3.child = 10
OR i4.child = 10);

Diese Suche hat natürlich einige Nachteile, so ist es beim Fund eines Knotens nicht möglich die Suche abzubrechen. Alle weiteren Knoten müssen durchsucht werde. Dies kann, wenn man nicht alle Lösungswege braucht, aus Sicht der Performance verheerend sein. Ausserdem muss die Suchtiefe vorbestimmt werden. Allerdings sollte es kein Problem darstellen die Suche dynamisch, zur Laufzweit für die entsprechende Suchtiefe zu generieren, so kann man auch eine nicht erfolgreiche Suche mit einer höheren Tiefe noch einmal laufen lassen.

Der Grosse Vorteil bei der Suche auf der Datenbank ist natürlich das man eine grössere Geschwindigkeit ereichen kann, als wenn jeder Knoten zu einem Clientprogramm transferiert werden muss.

Unter Denormalsieren versteht man die "bewusste Rücknahme einer Normalisierung zum Zweck der Verbesserung des Laufzeitverhaltens einer Datenbankanwendung." (Wikipedia) Hin und wieder ist es nötig Daten zu duplizieren um Abfragen schneller zu machen. Doch wie macht man das mit MySQL?

In MySQL gibt es mit dem INSERT...SELECT-Befehl ein mächtiges Werkzeug um Daten aus verschiedenen Tabellen in eine Neue einzufügen. Vor dem Einfügen können die Daten natürlich durch alle in SELECT verfügbaren Möglichkeiten manipuliert werden.

Leider ist es momentan in MySQL nicht möglich auf eine Tabelle im SELECT-Teil zuzugreifen und in die gleiche Tabelle zu schreiben. Deshalb gelingt das unten stehendes Beispiel nicht. (Nicht überprüft.)
 

INSERT INTO pagelinks (pl_to)
  SELECT page.page_id
  FROM page, pagelinks
  WHERE page.page_namespace = pagelinks.pl_namespace
  AND pagelinks.pl_title = page.page_title;

Dieses Problem kann allerdings relativ leicht umgangen werden. Man erstellte einfach eine neue Tabelle die ein Abbild jener ist die ergänzt werden soll. Der SQL-Code einer Datenbank kann mit "mysqldump -u benutzer -p datenbank -d tabelle" ausgelesen werden. Der Code muss danach angepasst werden (Tabellennamen ersetzen) und in die Datenbank eingespielt werden. Mit dem INSERT...SELECT-Befehl können danach die neue Tabelle wieder mit Daten aufgefüllt werden. Daraus ergibt sich dann in meinem Fall (mit der neuen Tabelle idlinks und da ich nicht ganz alle Daten brauche).

INSERT INTO idlinks (il_from,il_to)
  SELECT pagelinks.il_from, page.page_id
  FROM page, pagelinks
  WHERE page.page_namespace = pagelinks.pl_namespace
  AND pagelinks.pl_title = page.page_title;

Nun haben wir immer noch ein Problem. Bei vielen Daten bricht die Operation irgendwann mit der Fehlermeldung "ERROR 1206 (HY000): The total number of locks exceeds the lock table size" ab. Dies liegt daran das der InnoDB-Buffer-Pool zu klein ist. Der Puffer kann in der Datei my.cnf wie folgt angepasst werde. (Neustarten der Datenbank nicht vergessen.)

[mysqld]
# Set buffer pool size to 50-80% of your computer's memory
innodb_buffer_pool_size=70M
innodb_additional_mem_pool_size=10M

Danach sollte diese Operation auch recht zügig ablaufen. Denormalisieren von Daten in MySQL ist nicht ganz eifach, mit ein wenig "pröblen" kommt man aber, wie dieser Artikel zeigt, auf gute Resulate.

Nochmals was von meiner krass-viel-daten Projekt. Die Keys nachträglich zu erstellen verschnellert zwar das Einfügen massiv, das Einfügen der Keys dauert aber vermutlich dann etwa gleich lange:

mysql> show processlist;
+----+---------+-----------+---------+---------+--------+-------------------+------------------------------------------------------------------------------------------------------+
| Id | User    | Host      | db      | Command | Time   | State             | Info                                                                                                 |
+----+---------+-----------+---------+---------+--------+-------------------+------------------------------------------------------------------------------------------------------+
| 19 | xyz     | localhost | xyz     | Query   | 340517 | copy to tmp table | ALTER TABLE `pagelinks`
  ADD UNIQUE KEY `pl_from` (`pl_from`,`pl_namespace`,`pl_title`),
  ADD KEY  |
| 45 | root    | localhost | wikiway | Query   |      0 | NULL              | show processlist                                                                                     |
+----+---------+-----------+---------+---------+--------+-------------------+------------------------------------------------------------------------------------------------------+
2 rows in set (0.06 sec)

Also noch etwa 100 Stunden um die Keys zu erstellen. Und leider dauern die Abfragen immer noch zu lange. Desshalb werde ich als nächstes Denormalisieren.

Viele Daten sind ein Fluch, besonders wenn man nicht die Möglichkeit hat einfach einen dickeren Rechner hinzustellen. Mein Laptop rechnet sich für eine Testinstallation momentan dumm und dämlich. Tagelange Insert-Batch gehören in zwischen zum Normalfall.

Dank dem Tipp von Chregu habe ich heute mal die Key's nachräglich hinzugefügt. Das hat das einfügen einiges schneller gemacht. Das Einfügen der Schlüssel dauert dann aber auch ein Weilchen. Das sieht dann so aus:

Query OK, 1097721 rows affected (2 hours 45 min 31.85 sec)
Records: 1097721  Duplicates: 0  Warnings: 0

Mehr zu Krass-viel-Daten vieleicht irgendwann mal später hier in diesem Blog.