- SQLite ist ein zeilenorientierter Speicher, der auf der Festplatte in einer B-Baum-Struktur gespeichert wird, und führt Abfragen mit einer virtuellen Maschine namens VDBE aus. Es ist plattformunabhängig und kann single-threaded in nahezu jeder Umgebung ausgeführt werden
- Obwohl es eine Datenbank für allgemeine Zwecke ist, eignet sie sich besonders gut für OLTP-Workloads. Forschende der University at Buffalo stellten 2015 fest, dass die meisten Abfragen entweder einfache Key-Value-Lookups oder komplexe OLAP-Abfragen sind
- Forschende der University of Wisconsin–Madison arbeiteten daran, analytische Abfragen zu beschleunigen. Sie verglichen die Performance mit DuckDB und dem Star Schema Benchmark (SSB)
Ursache
- Um herauszufinden, warum SQLite langsam ist, wurde die Option
VDBE_PROFILE verwendet, um die von jeder VDBE-Instruktion verbrauchten CPU-Zyklen zu messen.
- Zwei Opcodes namens
SeekRowID und Column erwiesen sich als Hauptursache.
Datenbank-Joins
- Datenbanken implementieren Joins unter anderem mit Nested-Loop-Joins, Hash-Joins und Sort-Merge-Joins.
- SQLite verwendet den einfachsten Ansatz, den "Nested-Loop-Join". Dieser ähnelt einer B-Baum-Suche und ist kostenintensiv.
Bedeutung der Join-Optimierung
- Bei Join-Operationen ist die Reihenfolge der Tabellen wichtig. Durch eine andere Reihenfolge lässt sich die Anzahl der Operationen stark reduzieren. Das ist ein NP-schweres Problem.
- Es gibt zwei Join-Algorithmen, die besser sind als Nested-Loop-Joins, aber Hash-Joins verbrauchen viel Speicher, und SQLite läuft oft in Umgebungen mit Speicherbeschränkungen.
- Die Forschenden nutzten Bloom-Filter, um die Platzeffizienz zu erhöhen und sie an CPU-Cache-Lines anzupassen. Dafür wurden zwei Opcodes namens
Filter und FilterAdd hinzugefügt.
Ergebnisse
- Nach der Optimierung waren in der Analyse der CPU-Zyklen die großen blauen Balken fast vollständig verschwunden.
- SQLite wurde 7- bis 10-mal schneller. Diese Forschungsergebnisse wurden in SQLite v3.38.0 übernommen.
- Bloom-Filter passen mit minimalem Speicher-Overhead gut zur einfachen Implementierung von SQLite und funktionieren innerhalb der bestehenden Query-Engine
3 Kommentare
Wenn ich jetzt die Version prüfe, sehe ich, dass mein System 3.42.0 verwendet. Derzeit ist 3.47.2 die neueste Version.
Ich sollte wohl einmal nachsehen, welche SQLite-Version ich gerade verwende.
Tatsächlich erstelle ich außerdem mit openpyxl Excel-Dateien, aber das dauert ziemlich lange, daher sollte ich wohl nachsehen, ob es eine andere Bibliothek gibt.
Wäre es nicht sinnvoll, erst einmal ein Profiling durchzuführen?