Warum SQLite Bytecode verwendet

Allgemeine Funktionsweise von SQL-Datenbank-Engines

• Alle SQL-Datenbank-Engines arbeiten auf ähnliche Weise
  • Sie wandeln die eingegebene SQL-Anweisung in ein „Prepared Statement“ um
  • Das Prepared Statement wird dann „ausgeführt“, um Ergebnisse zu erzeugen
• In SQLite wird ein Prepared Statement als Instanz des Objekts sqlite3_stmt dargestellt
• Grundsätzlich gibt es zwei Arten, ein Prepared Statement darzustellen
  • Bytecode-Ansatz: wird von SQLite verwendet
  • Objektbaum-Ansatz: wird von MySQL und PostgreSQL verwendet

Vorteile des Bytecode-Ansatzes

• Leicht zu verstehen
  • Er besteht aus einer Auflistung einfacher Befehle und lässt sich daher leicht ausgeben
  • Mit dem Schlüsselwort EXPLAIN kann der Bytecode einer SQL-Anweisung eingesehen werden
• Einfach zu debuggen
  • Die Parsing-/Analysephase und die Ausführungsphase sind klar voneinander getrennt
  • In Debug-Builds lässt sich die Bytecode-Ausführung mit dem Befehl PRAGMA vdbe_trace=ON verfolgen
• Inkrementelle Ausführung möglich
  • In Bytecode geschriebene SQL-Anweisungen können zeilenweise ausgeführt, angehalten und später fortgesetzt werden
  • Beim Objektbaum-Ansatz wird der gesamte Baum auf einmal ausgeführt, wodurch inkrementelle Ausführung schwierig ist
• Geringerer Speicherverbrauch
  • Bytecode ist kleiner als ein AST
  • Prepared Statements werden oft lange im Speicher gecacht, daher ist der Speicherverbrauch wichtig
• Hohe Ausführungsgeschwindigkeit
  • In jedem Schritt müssen weniger Entscheidungen getroffen werden, was die Ausführung beschleunigt

Vorteile des Objektbaum-Ansatzes

• Der Query-Plan kann zur Laufzeit verändert werden
  • Ein Objektbaum lässt sich auch während der Ausführung leicht modifizieren
  • Dadurch ist dynamische Optimierung je nach Fortschritt der Query möglich
• Leicht zu parallelisieren
  • Jeder Verarbeitungs-Knoten kann einem eigenen Thread zugewiesen werden
  • Es muss nur die Datenübergabe zwischen den Knoten synchronisiert werden
  • Das ist vorteilhaft, wenn große analytische Abfragen (OLAP) auf mehreren Kernen ausgeführt werden

Meinung von GN⁺

• Da das Hauptziel von SQLite die Transaktionsverarbeitung (OLTP) in IoT-Umgebungen ist, scheint der Bytecode-Ansatz gut geeignet zu sein. Er ist einfach, leichtgewichtig und kann zugleich hohe Performance bieten.
• MySQL und PostgreSQL werden dagegen häufig auch für die Analyse großer Datenmengen eingesetzt, sodass dort die Vorteile des Objektbaum-Ansatzes stärker zum Tragen kommen können, etwa die dynamische Optimierung von Query-Ausführungsplänen und die Parallelisierung.
• Allerdings hat der Objektbaum-Ansatz auch den Nachteil, dass Debugging und Performance-Analyse schwieriger sind. Außerdem kann er bei einfachen Queries wegen der Kosten der Baumtraversierung unter Umständen sogar langsamer sein als Bytecode.
• Wichtig ist, den passenden Ansatz entsprechend Einsatzzweck und Ziel zu wählen. Bei einem universellen RDBMS wäre auch ein hybrider Ansatz denkbar, der die Vor- und Nachteile beider Methoden ausbalanciert.

[GN⁺]

Hacker-News-Kommentare

• Dass SQLite zur Ausführung von SQL-Abfragen eine Bytecode-VM statt eines abstrakten Syntaxbaums (AST) verwendet, ist eine interessante Designentscheidung für eine Datenbank. Bytecode hat gegenüber einem AST folgende Vorteile:

  • Kompaktheit: Bytecode ist kompakter als ein AST, da keine versteckten malloc-/Objekt-Header und Zeiger für Unterausdrücke nötig sind.
  • Leistung: Die Ausführung von Bytecode ist schneller, weil die Cache-Nutzung besser ist und es weniger Cache-Misses durch Pointer-Chasing gibt.
  • Inkrementelle Ausführung: Mit einem expliziten Stack lässt sich die Ausführung mit Bytecode leichter anhalten und fortsetzen, ohne den normalen Stack abwickeln zu müssen.

• Bytecode-VMs und Interpreter werden oft mit allgemeinen Programmiersprachen in Verbindung gebracht, können aber auch in anderen Kontexten überraschend nützlich sein:

  • eBPF: Ein Erweiterungsmechanismus für den Linux-Kernel.
  • DWARF-Ausdruckssprache: Wird von Debuggern wie GDB und LLDB verwendet.
  • RAR-Dateiformat: Enthält Bytecode-Kodierung für benutzerdefinierte Datentransformationen.

• Microsoft SQL Server verwendet intern einen Objektbaum, aber die Ausgabe des Query-Plans bleibt dennoch tabellarisch, was zeigt, wie schwierig es ist, einen Objektbaum als Tabelle darzustellen.

• Programmierer wissen oft genau, welche Index-Lookups in einer Schleife stattfinden sollen. Daher kann es in manchen Fällen vorteilhaft sein, statt SQL direkt Bytecode zu schreiben oder eine imperative Hochsprache zu verwenden. Das in SQL auszudrücken, kann mühsam sein.

• Wenn der Flaschenhals nicht in der Bytecode-Ausführung liegt, sondern zum Beispiel bei Speicher- oder Festplattengeschwindigkeit, ist eine Umwandlung in nativen Code per JIT-Kompilierung möglicherweise nicht notwendig.

• Viele Programmiersprachen wie Python, Ruby und Lua verwenden intern Bytecode oder ASTs. Aufgrund von Designentscheidungen in Datenbanken können leicht parsebare Anweisungen auch für fehleranfällige Third-Party-Bibliotheken oder ORM-Implementierungen nützlich sein.