SQLite-Indizes visualisieren

 (mrsuh.com)
3 Punkte von GN⁺ 2024-11-16 | 1 Kommentare | Auf WhatsApp teilen
  • Zur Untersuchung, wie SQLite-Indizes tatsächlich auf Datenträger und im Arbeitsspeicher angeordnet sind, wurde die B-Tree-Struktur analysiert; Indexdaten wurden gedumpt und visualisiert
  • Indizes bestehen aus Pages und Cells; eine Page enthält den Link zum rechten Kind sowie Cell-Daten, eine Cell enthält Indexdaten, rowId und den Link zum linken Kind
  • Da Page-Größe, Anzahl der Einträge, B-Tree-Tiefe und Anzahl genutzter Pages aus sqlite3_analyzer nicht ausreichten, wurden dem SQLite-Quellcode Debug-Funktionen hinzugefügt
  • Die Experimente vergleichen Datensatzanzahl, ASC/DESC, ausdrucksbasierte Indizes, UNIQUE mit NULL, Partial Index, mehrere Spalten sowie Kombinationen aus Text, REAL und Integer+Text
  • Bei 1.000.000 Datensätzen ergaben sich 3.342 Pages, wenn der Index vor dem Einfügen erstellt wurde, und 2.930 Pages, wenn er nach dem Einfügen erstellt wurde; nach VACUUM oder REINDEX sank die Zahl ebenfalls auf 2.930 Pages

Warum ich SQLite-Indizes selbst untersucht habe

  • Dies ist ein Experiment, das über die Grundstruktur von Indizes hinaus die tatsächlichen Datenstrukturen, Algorithmen und die Speicherung auf Datenträger untersucht
  • Ziel ist zu sehen, wie ein DBMS Indizes auf Datenträger und im Arbeitsspeicher speichert und wie es beim Suchen darauf zugreift
  • SQLite wurde aus folgenden Gründen als Untersuchungsobjekt gewählt
    • Es ist ein in Browsern, mobilen Apps und Betriebssystemen weit verbreitetes DBMS
    • Es lässt sich ohne separaten Server nur mit einer Client-Anwendung einfach debuggen
    • Die Codebasis ist kleiner als bei MySQL oder PostgreSQL, verwendet für Indizes aber ähnliche Datenstrukturen
    • Es ist Open Source

Ein B-Tree aus Pages und Cells

  • Laut SQLite-Dokumentation werden Indizes als B-Tree-Struktur gespeichert
  • Die Einheit, die in SQLite einem Node entspricht, ist die Page
    • Eine Page speichert Cell-Daten
    • Eine Page besitzt einen Link zur rechten Kind-Page
  • Eine Cell enthält Indexdaten, rowId und den Link zur linken Kind-Page
  • Jede Zeile einer SQLite-Tabelle hat standardmäßig eine eindeutige rowId, die wie ein Primärschlüssel funktioniert, wenn kein expliziter Primärschlüssel vorhanden ist
  • Jede Page hat eine feste Größe; der Größenbereich liegt bei 512 bis 65.536 Bytes
  • Page- und Cell-Header verwenden 4 Bytes zum Speichern von Kind-Links
    • Um die Nummer der Kind-Page zu ermitteln, muss der Header separat mit der Funktion get4byte(...) gelesen werden
  • Beispiele für interne SQLite-Strukturen:
    • MemPage: enthält unter anderem die Page-Nummer pgno, die Anzahl der Cells nCell, den Cell-Indexbereich aCellIdx und den Zeiger auf das Datenträgerabbild der Page-Daten aData
    • CellInfo: enthält unter anderem pPayload, das auf die Startposition des Payloads zeigt

Grenzen von sqlite3_analyzer und Debug-Funktionen

  • Mit sqlite3_analyzer lassen sich allgemeine Informationen zu Indizes anzeigen
    • Beispielausgaben enthalten etwa die Page-Größe 4096, die Anzahl der Einträge 1000, die B-Tree-Tiefe 2 und die Anzahl der genutzten Pages 4
  • Dieses Tool liefert jedoch nur Übersichtsinformationen und reicht nicht aus, um die internen Cells und Payloads eines Index direkt zu untersuchen
  • Nach mehreren Wochen Experimentieren wurde eine Funktion zur Indexanalyse geschrieben
    • Code: sqlite.patch
    • sqlite3DebugGetMemoryPayload(Mem *mem)
    • sqlite3DebugGetCellPayloadAndRowId(BtCursor *pCur, MemPage * pPage, int cellIndex)
    • sqlite3DebugBtreeIndexDump(BtCursor *pCur, int pageNumber)
  • Diese Funktion liest den Inhalt des ausgewählten Index und gibt ihn auf STDOUT aus
    • Der Ablauf ist SQL query -> selected index -> stdout
    • Die Ausgabe enthält Page-Nummer, Nummer der rechten Kind-Page, Cell-Nummer, Nummer der linken Kind-Page, Payload und rowId
  • Die Experimentierumgebung kann mit Docker ausgeführt werden
    • docker run -it --rm -v "$PWD":/app/data --platform linux/x86_64 mrsuh/sqlite-index bash
    • sh bin/dump-index.sh database.sqlite "SELECT * FROM table INDEXED BY index WHERE column=1" dump.txt

Wandel der Visualisierungsmethode

  • Anfangs wurde d3-org-tree verwendet, um die Indexstruktur zu visualisieren
  • Als der Baum tiefer wurde und die Zahl der Pages pro Ebene wuchs, ließ sich der Abstand zwischen Pages nur schwer anpassen; die Bilder wurden zu groß und schwer lesbar
  • Es wurde versucht, dies mit JavaScript und CSS anzupassen, was jedoch nicht gut passte; zeitweise wurde daher auf eine textbasierte Strukturdarstellung umgestellt
  • Die Textausgabe zeigt die Gesamtzahl der Pages, die Gesamtzahl der Cells, die Anzahl von Pages und Cells pro Ebene sowie Page-Informationen, Cell-Informationen und Payloads
  • Später wurde daraus eine Bildausgabe mit feinerer Kontrolle über Design und Abstände mithilfe der PHP-Erweiterung ImageMagick
  • Das finale Bild enthält folgende Informationen
    • Oben links werden die allgemeinen Informationen des Index angezeigt
    • Für jede Ebene werden die Gesamtzahl der Pages und Cells angezeigt
    • Für jede Page werden Page-Nummer, rechter Kind-Link sowie Informationen zur ersten und letzten Cell angezeigt
    • Pro Ebene werden nur einige Pages angezeigt, einschließlich der ersten und letzten Page
    • Die Root-Page befindet sich auf der ersten Ebene
  • Der Befehl zum Erzeugen eines Bildes aus dem Dump lautet:
    • php bin/console app:render-index --dumpIndexPath=dump.txt --outputImagePath=image.webp

Wie die Anzahl der Datensätze die Indexform verändert

  • Auf einer Tabelle mit column1 INT NOT NULL wurde ein Index column1 ASC erstellt und die Struktur bei unterschiedlicher Datensatzanzahl untersucht
  • Ein Index mit 1 Datensatz besteht aus 1 Ebene, 1 Page und 1 Cell
  • Auch ein Index mit 1.000 Datensätzen wurde auf dieselbe Weise erstellt und visualisiert
  • Ein Index mit 1.000.000 Datensätzen hat folgende Struktur
    • 3 Ebenen
    • 2.930 Pages
    • 1.000.000 Cells
  • Da die Daten der Reihe nach hinzugefügt wurden, gilt bei rowId = 1: column1 = 1

Sortierrichtung und Ausdrucksindizes

  • Für dieselben Daten wurden idx_asc und idx_desc erstellt, um ASC/DESC-Indizes zu vergleichen
  • Der ASC-Index entspricht dem vorherigen Index, da die Standardsortierung ASC ist
    • Der Eintrag mit rowId=1,000,000, column1=1,000,000, payload=1,000,000 befindet sich in der letzten Cell der ganz rechten Page
    • Der Eintrag mit rowId=1, column1=1, payload=1 befindet sich in der ersten Cell der ganz linken Page
  • Der DESC-Index ist umgekehrt angeordnet
    • Der Eintrag mit rowId=1, column1=1, payload=1 befindet sich in der letzten Cell der ganz rechten Page
    • Der Eintrag mit rowId=1,000,000, column1=1,000,000, payload=1,000,000 befindet sich in der ersten Cell der ganz linken Page
  • Ausdrucksbasierte Indizes speichern die vom Ausdruck erzeugte Zeichenkette
    • Im Beispiel wird aus JSON-Text $.timestamp extrahiert und anschließend mit strftime('%Y-%m-%d %H:%M:%S', ..., 'unixepoch') umgewandelt, um einen ASC-Index zu erstellen
    • Auch komplexere Ausdrücke können verwendet werden; im Index wird nur ihr Ergebnis gespeichert

NULL, Partial Index und mehrere Spalten

  • SQLite unterstützt UNIQUE-Indizes mit NULL-Werten
    • Im Beispiel werden die Werte 1, mehrere NULL und 1000000 eingefügt und CREATE UNIQUE INDEX idx ON table_test (column1 ASC) ausgeführt
    • Der visualisierte Index wirkt so, als speichere er nur Werte ungleich NULL
  • Ein Partial Index mit der Bedingung WHERE column1 IS NOT NULL filtert NULL-Werte heraus
    • Dieser Index enthält nur eine Page
    • Er führt zu schnelleren Suchen als das vorherige UNIQUE-Beispiel
  • Mehrspaltige Indizes speichern die Daten aller Felder nacheinander in der Cell
    • Das Beispiel ist ein Index auf (column1 ASC, column2 ASC)
    • In der Visualisierung sind die Felder durch einen Doppelpunkt : getrennt

Zeitpunkt der Indexerstellung und Effekt der Neuaufbau-Operationen

  • Verglichen wurde der Fall, dass der Index vor dem Einfügen der Daten erstellt wird, mit dem Fall, dass er erst nach dem Einfügen aller Daten erstellt wird
  • Wenn neue Daten hinzugefügt werden, muss der Baum sich selbst neu ausbalancieren
  • Einen Index für bereits vorhandene Daten auf einmal zu erzeugen, kann deutlich effizienter sein
  • Beide Indizes sehen ähnlich aus, doch der zweite Index mit weniger Pages kann schneller sein
  • Das Vergleichsergebnis für 1.000.000 Cells lautet:
Kategorie Total Pages Total Cells
Vor dem Einfügen erstellt 3342 1000000
Nach dem Einfügen erstellt 2930 1000000
  • Eine ähnliche Optimierung lässt sich mit VACUUM oder REINDEX durchführen
    • VACUUM erstellt Indizes und Tabellen zusammen mit den Daten neu
    • REINDEX idx erstellt nur den Index neu
  • Beide Befehle reduzierten im Beispiel die Page-Zahl von 3342 auf 2930

Indexspeicherung nach Datentyp

  • Textdaten: Kurze Zeichenketten werden direkt in Index-Cells gespeichert, lange Texte müssen jedoch separat gespeichert werden
    • Im Beispiel werden Werte von text-1 bis text-1000000 eingefügt und ein Index column1 ASC erstellt
    • Man kann sehen, dass die tatsächlichen Zeichenketten direkt im Index gespeichert sind
  • Auch REAL-Daten wurden im Index gespeichert und visualisiert
    • Im Beispiel werden die Werte 1.14, 2.14, ..., 1000000.14 verwendet
  • Außerdem wurde ein zusammengesetzter Index aus Integer und Text untersucht
    • Im Beispiel wird auf einer Tabelle (column1 INT, column2 TEXT) ein Index (column1 ASC, column2 ASC) erstellt
    • Integer und Zeichenkette werden wie bei der Indexerstellung angegeben gemeinsam in derselben Cell gespeichert

Reproduktion und nächste Schritte

  • Das Experiment zeigt, wie SQLite-Indizes strukturiert sind, wie Datensatzdaten im Speicher abgelegt werden und wie der B-Tree Daten organisiert und darauf zugreift
  • Die Visualisierung wird verwendet, um unterschiedliche Indizes zu analysieren und zu vergleichen
  • Alle Beispiele lassen sich mit folgenden Befehlen reproduzieren
    • docker run -it --rm -v "$PWD":/app/data --platform linux/x86_64 mrsuh/sqlite-index bash
    • sh bin/test-index.sh
  • Code und Beispiele befinden sich in mrsuh/sqlite-index
  • Als Nächstes folgen die Visualisierung indexbasierter Suche und die Untersuchung einiger SQL-Abfragen

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-11-16
Meinungen auf Hacker News

  • Es hieß, jede Zeile in einer SQLite-Tabelle habe standardmäßig eine eindeutige rowId und verhalte sich wie ein Primärschlüssel, wenn kein expliziter Primärschlüssel vorhanden ist; tatsächlich verwendet SQLite aber auch dann rowid, wenn es einen Primärschlüssel gibt
    Es wäre interessant, den Primärschlüssel-Index einer WITHOUT ROWID-Tabelle zu visualisieren. Solche Indizes sind besonders spannend
    Auch wenn zwei Indizes ähnlich aussehen, heißt das nicht sofort, dass der zweite Index schneller ist, nur weil er weniger Seiten hat. Entscheidend ist die Höhe des Baums; danach kommt die Frage, ob man nach dem Finden eines Werts im Index die übrigen Daten aus einer separaten Tabelle (rowid) lesen muss oder ob die Daten wie bei WITHOUT ROWID direkt vorhanden sind. Besonders bei Bereichsabfragen wie where 50 <= col <= 100 ist der Unterschied groß

    • Bei einem einzelnen Zugriff stimmt, dass die Baumhöhe maßgeblich ist; wenn der Index aber häufig angesprochen wird, kann auch die Gesamtgröße für die Cache-Trefferquote sehr wichtig sein
    • Dass auch bei vorhandenem Primärschlüssel rowid verwendet wird, hat eine Ausnahme: Wenn man INTEGER PRIMARY KEY anlegt, verwendet SQLite stattdessen diesen [1]
      [1]: https://sqlite.org/rowidtable.html

  • SQLite ist in fast jeder Hinsicht ziemlich eigen, und das gilt meiner Ansicht nach besonders für die Query-Verarbeitung
    SQLite neigt dazu, Einfachheit gegenüber Performance zu bevorzugen, weshalb vieles anders implementiert ist als in anderen Datenbanken, mit denen ich gearbeitet habe. SQLite konkurriert weniger mit anderen Datenbanken als mit persistent gespeicherten JSON/XML-Dateien. Deshalb lernt man aus der SQLite-Implementierung nicht unbedingt viel darüber, wie echte Datenbanken dieselbe Aufgabe lösen

    • Es konkurriert mit beidem. SQLite wird eindeutig als lokaler persistenter Speicher genutzt, konkurriert aber auch mit anderen relationalen Datenbankmanagementsystemen, wenn kein separater Serverprozess nötig ist
      Das heißt zwar, dass die Anforderungen ziemlich anders sind, aber die Nutzung beschränkt sich nicht nur darauf, JSON/XML-Dateien zu ersetzen
    • SQLite ist eine echte Datenbank-Engine. Gemeint ist vermutlich eher, dass es nicht mit Datenbankservern konkurriert
    • Es ist nicht besonders weit davon entfernt, wie Server anderer Datenbankmanagementsysteme Speicher und Indizes handhaben. Die Prinzipien sind weitgehend dieselben, besonders wenn SQLite im WAL-Modus läuft

  • Die Website ist so gut lesbar, dass man sie tatsächlich lesen möchte

    • Auf dem iPhone ist die Schriftgröße des Fließtexts viel zu groß. Der wichtige Text in den Diagrammen ist deutlich kleiner, sodass man das Telefon für den Fließtext vom Gesicht wegschieben und zum Lesen der Diagramme wieder näher heranholen muss; das fühlt sich unpraktisch an
    • Es ist wirklich angenehm, Inhalte ohne dicht gedrängte Werbung lesen zu können. Der Artikel ist außerdem sehr gut

  • „indexes“ ist sowohl die 3. Person Singular Präsens des Verbs „to index“ als auch die Pluralform des Substantivs „index“. „indices“ dagegen ist die traditionelle Pluralform und wird besonders in mathematischen und wissenschaftlichen Kontexten häufig verwendet
    Im allgemeinen Englisch ist „indexes“ üblich, aber in technischen Bereichen wird aus sprachlicher Genauigkeit manchmal indices bevorzugt. In diesem Kontext kann „indices“ die Klarheit erhöhen, weil es den Indexierungsvorgang vom Plural von Index unterscheidet

    • Beides ist in Ordnung (https://www.nasdaq.com/articles/indexes-or-indices-whats-the...). Auch die Dokumentation von SQLite und PostgreSQL verwendet als prominente Beispiele indexes
    • Versucht mal, „time series“ in den Plural zu setzen; das ist nicht einfach
      In Finnland habe ich Fälle gesehen, in denen „time series“ als Plural und „time serie“ als Singular verwendet wurde
    • Ich weiß nicht, mit welcher Autorität das behauptet wird
      Alle großen relationalen Datenbankmanagementsysteme verwenden den Begriff indexes
    • Es hängt von der Zielgruppe ab. Wenn man sich an die Wissenschaft richtet, nimmt man indices; bei einem allgemeinen Publikum kann „indices“ prätentiös wirken

  • Es wäre auch interessant zu sehen, wie PostgreSQL dieselbe Aufgabe erledigt. Aus dem Vergleich ließe sich vermutlich viel lernen

  • Um mit weniger Aufwand verschiedene Layouts zu sehen, könnte man auch TGF für yEd ausgeben lassen