2022-07-27

Persistente Speicherung von Adaptive Radix Trees (ART) in DuckDB

Pedro Holanda

DuckDB nutzt ART-Indexes, um Primary-Key-(PK-), Foreign-Key-(FK-) und Unique-Constraints zu halten. Sie beschleunigen außerdem Point-Queries, Range-Queries (mit hoher Selektivität) und Joins. Vor der Bleeding-Edge-Version (oder V0.4.1, je nachdem, wann Sie diesen Beitrag lesen) persistierte DuckDB ART-Indexes nicht auf der Platte. Beim Speichern einer Datenbankdatei wurden nur die Informationen über bestehende PKs und FKs gespeichert; alle anderen Indexes waren transient und existierten beim Neustart der Datenbank nicht. PKs und FKs wurden beim Neuladen der Datenbank vollständig rekonstruiert, was zu dem Ärgernis hoher Ladezeiten führte.

Es gibt viel wissenschaftliche Arbeit zu ART-Indexes, vor allem zu Synchronisation, Cache-Effizienz und Evaluation. Bis zu diesem Punkt gibt es aber keine öffentliche Arbeit zum Serialisieren und Buffer-Managen eines ART-Trees. Manche sagen, dass Hyper, die Datenbank in Tableau, ART-Indexes persistiert, aber wieder: Es gibt keine öffentlichen Informationen, wie das gemacht wird.

Dieser Blogpost beschreibt, wie DuckDB ART-Indexes speichert und lädt. Insbesondere, wie der Index lazy geladen wird (d. h. ein ART-Knoten wird nur dann in den Speicher geladen, wenn er nötig ist). Im Abschnitt ART-Index gehen wir durch, was ein ART-Index ist, wie er funktioniert, und ein paar Beispiele. Im Abschnitt ART in DuckDB erklären wir, warum wir uns für einen ART-Index in DuckDB entschieden haben, wo er genutzt wird, und diskutieren die Probleme, ART-Indexes nicht zu persistieren. Im Abschnitt ART-Speicherung erklären wir, wie wir ART-Indexes in DuckDB serialisieren und buffer-managen. Im Abschnitt Benchmarks vergleichen wir DuckDB v0.4.0 (vor ART Storage) mit der Bleeding-Edge-Version von DuckDB. Wir zeigen den Unterschied bei den Ladekosten von PKs und FKs in beiden Versionen und die Unterschiede zwischen dem Lazy-Laden eines ART-Index und dem Zugriff auf einen vollständig geladenen ART-Index. Schließlich diskutieren wir im Abschnitt Roadmap die Nachteile unserer aktuellen Implementierungen und die Pläne in der Liste der ART-Index-Goodies für die Zukunft.

ART-Index

Adaptive Radix Trees sind im Kern Tries, die vertikale und horizontale Kompression anwenden, um kompakte Indexstrukturen zu erzeugen.

Trie

Tries sind Baumdatenstrukturen, bei denen jede Baumebene Informationen über einen Teil des Datensatzes hält. Sie werden üblicherweise mit Strings veranschaulicht. In der Abbildung unten sehen Sie eine Trie-Darstellung einer Tabelle mit den Strings „pedro“, „paulo“ und „peri“. Der Wurzelknoten repräsentiert das erste Zeichen „p“ mit Kindern „a“ (von paulo) und „e“ (von pedro und peri) und so weiter.

Um Lookups auf einem Trie auszuführen, müssen Sie jedes Zeichen des Schlüssels mit der aktuellen Ebene des Tries matchen. Suchen Sie zum Beispiel nach pedro, müssen Sie prüfen, ob die Wurzel den Buchstaben p enthält. Wenn ja, prüfen Sie, ob eines ihrer Kinder den Buchstaben e enthält, bis Sie einen Blattknoten erreichen, der den Pointer auf das Tuple hält, das diesen String enthält. (Siehe Abbildung unten).

Der Hauptvorteil von Tries ist, dass sie O(k)-Lookups haben, das heißt im schlechtesten Fall entsprechen die Lookup-Kosten der Länge der Strings.

In der Realität können Tries auch für numerische Datentypen genutzt werden. Sie zeichenweise wie Strings zu speichern wäre aber verschwenderisch. Nehmen Sie zum Beispiel den Datentyp UBIGINT. In Wirklichkeit ist UBIGINT ein uint64_t, der 64 Bits (d. h. 8 Bytes) Platz braucht. Der Maximalwert eines uint64_t ist 18,446,744,073,709,551,615. Würden wir ihn wie im Beispiel oben darstellen, bräuchten wir 17 Ebenen im Trie. In der Praxis werden Tries auf einem Bit-Fan-out erzeugt, der angibt, wie viele Bits pro Ebene des Tries dargestellt werden. Ein uint64_t-Trie mit 8-Bit-Fan-out hätte maximal 8 Ebenen, die jeweils ein Byte repräsentieren.

Für realistischere Beispiele sind ab hier alle Darstellungen in diesem Beitrag Bit-Darstellungen. In DuckDB ist der Fan-out immer 8 Bits. Der Einfachheit halber haben die folgenden Beispiele in diesem Blogpost aber einen Fan-out von 2 Bits.

Im Beispiel unten haben wir einen Trie, der die Werte 7, 10 und 12 indexiert. Sie sehen auch die Binärdarstellung jedes Werts in der Tabelle daneben. Jeder Knoten besteht aus den Bits 0 und 1, mit einem Pointer daneben. Dieser Pointer kann gesetzt (dargestellt durch *) oder null (dargestellt durch Ø) sein. Ähnlich wie beim String-Trie zuvor repräsentiert jede Ebene des Tries zwei Bits, und der Pointer neben diesen Bits zeigt auf ihre Kinder. Die Blätter zeigen schließlich auf die eigentlichen Daten.

Man merkt schnell, dass diese Trie-Darstellung auf zwei Fronten verschwenderisch ist. Erstens haben viele Knoten nur ein Kind (d. h. einen Pfad), das durch vertikale Kompression (d. h. Radix Tree) zusammengeklappt werden könnte. Zweitens haben viele Knoten Null-Pointer und speichern Platz ohne Information, was sich mit horizontaler Kompression lösen ließe.

Vertikale Kompression (d. h. Radix Trees)

Die Grundidee der vertikalen Kompression ist, dass wir Pfade mit Knoten, die nur ein Kind haben, zusammenklappen. Dafür speichern Knoten eine Präfix-Variable mit dem zusammengeklappten Pfad zu diesem Knoten. Eine Darstellung davon sehen Sie in der Abbildung unten. Man sieht zum Beispiel, dass die ersten vier Knoten nur ein Kind haben. Diese Knoten können zum dritten Knoten (d. h. dem ersten, der sich verzweigt) als Präfixpfad zusammengeklappt werden. Bei Lookups muss der Schlüssel alle Werte im Präfixpfad matchen.

Unten sehen Sie den resultierenden Trie nach vertikaler Kompression. Diese Trie-Variante ist allgemein als Radix Tree bekannt. Obwohl schon viel verschwendeter Platz mit dieser Trie-Variante eingespart wurde, haben wir immer noch viele Knoten mit ungesetzten Pointern.

Horizontale Kompression (d. h. ART)

Um die Designentscheidungen hinter ART-Indexes vollständig zu verstehen, müssen wir den 2-Bit-Fan-out zuerst auf 8 Bits erweitern, den üblicherweise in Datenbanksystemen gefundenen Fan-out.

Unten sehen Sie dieselben Knoten wie zuvor in einem Trie-Knoten von 8 Bits. In Wirklichkeit speichern diese Knoten (2^8) 256 Pointer, wobei der Schlüssel die Array-Position des Pointers ist. Im in diesem Beispiel dargestellten Fall haben wir einen Knoten mit (256 Pointer * 8 Bytes) 2048 Byte Größe, der aber nur 24 Bytes tatsächlich nutzt (3 Pointer * 8 Bytes), das heißt 2016 Bytes sind vollständig verschwendet. Um diese Situation zu vermeiden, bestehen ART-Indexes aus 4 verschiedenen Knotentypen, die davon abhängen, wie voll der aktuelle Knoten ist. Unten beschreibe ich jeden Knoten kurz mit einer grafischen Darstellung. In der grafischen Darstellung zeige ich eine konzeptuelle Visualisierung des Knotens und ein Beispiel mit den Schlüsseln 0, 4 und 255.

Node 4: Node 4 hält bis zu 4 verschiedene Schlüssel. Jeder Schlüssel wird in einem Ein-Byte-Array gespeichert, mit einem Pointer pro Schlüssel. Die Gesamtgröße beträgt 40 Bytes (4*1 + 4*8). Beachten Sie, dass das Pointer-Array mit dem Schlüssel-Array ausgerichtet ist (z. B. liegt Schlüssel 0 an Position 0 des Schlüssel-Arrays, deshalb liegt sein Pointer an Position 0 des Pointer-Arrays)

Node 16: Node 16 hält bis zu 16 verschiedene Schlüssel. Wie bei Node 4 wird jeder Schlüssel in einem Ein-Byte-Array gespeichert, mit einem Pointer pro Schlüssel. Die Gesamtgröße beträgt 144 Bytes (16*1 + 16*8). Wie bei Node 4 ist das Pointer-Array mit dem Schlüssel-Array ausgerichtet.

Node 48: Node 48 hält bis zu 48 verschiedene Schlüssel. Ist ein Schlüssel in diesem Knoten vorhanden, hält die Ein-Byte-Array-Position, die diesen Schlüssel repräsentiert, einen Index in das Pointer-Array, der auf das Kind dieses Schlüssels zeigt. Die Gesamtgröße beträgt 640 Bytes (256*1 + 48*8). Beachten Sie, dass Pointer-Array und Schlüssel-Array nicht mehr ausgerichtet sind. Das Schlüssel-Array zeigt auf die Position im Pointer-Array, an der der Pointer dieses Schlüssels gespeichert ist (z. B. ist der Schlüssel 255 im Schlüssel-Array auf 2 gesetzt, weil Position 2 des Pointer-Arrays auf das zu diesem Schlüssel gehörende Kind zeigt).

Node 256: Node 256 hält bis zu 256 verschiedene Schlüssel, also alle möglichen Werte in der Verteilung. Er hat nur einen Pointer-Vektor; ist der Pointer gesetzt, existiert der Schlüssel und zeigt auf sein Kind. Die Gesamtgröße beträgt 2048 Bytes (256 Pointer * 8 Bytes).

Für das Beispiel im vorherigen Abschnitt könnten wir statt eines Node 256 einen Node 4 nutzen, um die Schlüssel zu speichern, weil wir nur 3 vorhandene Schlüssel haben. Es sähe also so aus:

ART in DuckDB

Bei der Überlegung, welche Indexstruktur wir in DuckDB implementieren, wollten wir eine Struktur, die sowohl für PK/FK/Unique-Constraints genutzt werden kann als auch Range-Queries und Joins beschleunigen kann. Datenbanksysteme implementieren üblicherweise Hash-Tabellen für Constraint-Prüfungen und B+-Bäume für Range-Queries. In ART-Indexes sahen wir aber eine Gelegenheit, die Codekomplexität zu senken, indem wir eine Datenstruktur für zwei Einsatzfälle haben. Die wichtigsten Eigenschaften, die ART-Indexes uns bieten und die wir nutzen, sind:

1. Kompakte Struktur. Da die internen ART-Knoten eher klein sind, passen sie in CPU-Caches und sind eine cache-bewusstere Struktur als B+-Bäume.
2. Schnelle Point-Queries. Der Worst Case für eine ART-Point-Query ist O(k), was für Constraint-Prüfungen ausreichend schnell ist.
3. Keine dramatische Regression bei Inserts. Viele Hash-Tabellen-Varianten müssen neu gebaut werden, wenn sie eine bestimmte Größe erreichen. In der Praxis kann ein Insert eine deutliche Zeitregression verursachen, eine Abfrage dauert plötzlich Größenordnungen länger, ohne dass der Nutzer einen offensichtlichen Grund sieht. Im ART können Inserts Knotenwachstum verursachen (z. B. kann ein Node 4 zu einem Node 16 wachsen), aber das ist günstig.
4. Fähigkeit, Range-Queries auszuführen. Der ART führt Range-Queries nicht so schnell wie B+-Bäume aus, weil er Baumtraversierungen durchführen muss, während der B+-Baum Blattknoten sequenziell scannen kann. Er hat aber immer noch einen Vorteil gegenüber Hash-Tabellen, weil diese Art von Abfragen möglich ist (Manche argumentieren, man könne Hash-Tabellen für Range-Queries nutzen, aber meh). Das erlaubt uns, ART effizient für hochselektive Range-Queries und Index Joins zu nutzen.
5. Wartbarkeit. Eine Struktur für Constraint-Prüfungen und Range-Queries statt zwei ist codeeffizienter und wartbarer.

Wofür wird er genutzt?

Wie zuvor gesagt werden ART-Indexes in DuckDB vor allem auf drei Fronten genutzt.

1. Daten-Constraints. Primary Keys, Foreign Keys und Unique-Constraints werden alle von einem ART-Index gehalten. Beim Einfügen von Daten in ein Tuple mit einem Constraint wird das effektiv versuchen, eine Einfügung in den ART-Index durchzuführen, und fehlschlagen, wenn das Tuple schon existiert.

   CREATE TABLE integers (i INTEGER PRIMARY KEY);
   -- Insert unique values into ART
   INSERT INTO integers VALUES (3), (2);
   -- Insert conflicting value in ART will fail
   INSERT INTO integers VALUES (3);
   
   CREATE TABLE fk_integers (
       j INTEGER,
       FOREIGN KEY (j) REFERENCES integers(i)
    );
   -- This insert works normally
   INSERT INTO fk_integers VALUES (2), (3);
   -- This fails after checking the ART in integers
   INSERT INTO fk_integers VALUES (4);

2. Range-Queries. Hochselektive Range-Queries auf indexierten Spalten nutzen ebenfalls den ART-Index darunter.

   CREATE TABLE integers (i INTEGER PRIMARY KEY);
   -- Insert unique values into ART
   INSERT INTO integers VALUES (3), (2), (1), (8) , (10);
   -- Range queries (if highly selective) will also use the ART index
   SELECT * FROM integers WHERE i >= 8;

3. Joins. Joins mit einer kleinen Zahl von Matches nutzen ebenfalls bestehende ART-Indexes.

   -- Optionally you can always force index joins with the following pragma
   PRAGMA force_index_join;
   
   CREATE TABLE t1 (i INTEGER PRIMARY KEY);
   CREATE TABLE t2 (i INTEGER PRIMARY KEY);
   -- Insert unique values into ART
   INSERT INTO t1 VALUES (3), (2), (1), (8), (10);
   INSERT INTO t2 VALUES (3), (2), (1), (8), (10);
   -- Joins will also use the ART index
   SELECT * FROM t1 INNER JOIN t2 ON (t1.i = t2.i);

4. Indexes über Ausdrücke. ART-Indexes können auch genutzt werden, um Ausdrücke schnell nachzuschlagen.

   CREATE TABLE integers (i INTEGER, j INTEGER);
   
   INSERT INTO integers VALUES (1, 1), (2, 2), (3, 3);
   
   -- Creates index over the i + j expression
   CREATE INDEX i_index ON integers USING ART((i + j));
   
   -- Uses ART index point query
   SELECT i FROM integers WHERE i + j = 2;

ART-Speicherung

Es gibt zwei Hauptconstraints beim Speichern von ART-Indexes:

1. Der Index muss in einer Reihenfolge gespeichert werden, die Lazy-Loading erlaubt. Sonst müssten wir den Index vollständig laden, einschließlich Knoten, die für Abfragen, die in dieser Session ausgeführt würden, möglicherweise unnötig sind.
2. Er darf die Knotengröße nicht erhöhen. Sonst mindern wir die cache-bewusste Wirksamkeit des ART-Index.

Post-Order-Traversierung

Um Lazy-Loading zu erlauben, müssen wir alle Kinder eines Knotens speichern, die Informationen sammeln, wo jedes Kind gespeichert ist, und dann, wenn wir den eigentlichen Knoten speichern, die Platteninformationen jedes seiner Kinder speichern. Um diese Art von Operation durchzuführen, machen wir eine Post-Order-Traversierung.

Die Post-Order-Traversierung ist in der Abbildung unten gezeigt. Die Kreise in Rot repräsentieren die numerische Reihenfolge, in der die Knoten gespeichert werden. Starten wir vom Wurzelknoten (d. h. Node 4 mit Speicherreihenfolge 10), müssen wir zuerst beide Kinder speichern (d. h. Node 16 mit Speicherreihenfolge 8 und das Leaf mit Speicherreihenfolge 9). Das geht rekursiv für jedes seiner Kinder weiter.

Die Abbildung unten zeigt eine tatsächliche Darstellung, wie das in DuckDBs Blockformat aussehen würde. In DuckDB werden Daten in 256-kB-zusammenhängenden Blöcken gespeichert, wobei einige Blöcke für Metadaten und einige für eigentliche Daten reserviert sind. Jeder Block wird durch eine id repräsentiert. Um Navigation innerhalb eines Blocks zu erlauben, sind sie nach Byte-Offsets partitioniert, jeder Block enthält also 256.000 verschiedene Offsets.

In diesem Beispiel haben wir Block 0, der einige unserer Datenbank-Metadaten speichert. Insbesondere zwischen den Offsets 100.000 und 100.200 speichern wir Informationen, die zu einem ART-Index gehören. Das speichert Informationen über den Index (z. B. Name, Constraints, Ausdruck) und die <Block,Offset>-Position seines Wurzelknotens.

Nehmen wir zum Beispiel an, wir machen einen Lookup des Schlüssels mit row_ids, die im Leaf mit Speicherreihenfolge 1 gespeichert sind. Wir würden damit beginnen, den ART-Wurzelknoten auf <Block:2, Offset:220> zu laden; durch Prüfen der in diesem Knoten gespeicherten Schlüssel würden wir dann sehen, dass wir den Node 16 bei <Block:2, Offset:140> laden müssen und dann schließlich unser Leaf bei <Block:0, Offset:0>. Das bedeutet, dass für diesen Lookup nur diese 3 Knoten in den Speicher geladen wurden. Nachfolgende Zugriffe auf diese Knoten würden nur Speicherzugriff brauchen, während Zugriffe auf andere Knoten (z. B. Leaf Speicherreihenfolge 2) immer noch zu Plattenzugriff führen würden.

Ein großes Problem bei der Umsetzung dieses (De-)Serialisierungsprozesses ist, dass wir jetzt nicht nur Informationen über die Speicheradresse von Pointern halten müssen, sondern auch, ob sie schon im Speicher sind und wenn nicht, was die <Block,Offset>-Position ist, an der sie gespeichert sind.

Würden wir die Block-ID und den Offset in neuen Variablen speichern, würde das die ART-Knotengrößen dramatisch erhöhen und ihre Wirksamkeit als cache-bewusste Datenstruktur mindern.

Nehmen Sie Node 256 als Beispiel. Die Kosten, 256 Pointer zu halten, betragen 2048 Bytes (256 Pointer * 8 Bytes). Sagen wir, wir entscheiden uns, die Blockinformationen in einem neuen Array zu speichern, etwa so:

struct BlockPointer {
    uint32_t block_id;
    uint32_t offset;
}

class Node256 : public Node  {
    // Pointers to the child nodes
    Node* children[256];
    BlockPointer block_info[256];
}

Node 256 würde um 2048 Bytes (256 * (4+4)) wachsen und damit seine aktuelle Größe auf 4096 Bytes verdoppeln.

Pointer Swizzling

Um die Vergrößerung der ART-Knoten zu vermeiden, haben wir uns entschieden, Swizzlable Pointers zu implementieren und sie statt regulärer Pointer zu nutzen.

Die Idee ist, dass wir nicht alle 64 Bits (d. h. 48 Bits geben Ihnen einen Adressraum von 256 Terabyte und unterstützen jede der aktuellen Architekturen, siehe die verwandte Diskussion auf Stack Overflow und die Wikipedia-Seite „64-bit computing“) in einem Pointer brauchen, um auf eine Speicheradresse zu zeigen. Deshalb können wir das höchstwertige Bit als Flag nutzen (d. h. das Swizzle Flag). Ist das Swizzle Flag gesetzt, ist der Wert in unserem Swizzlable Pointer eine Speicheradresse für den Knoten. Andernfalls speichert die Variable die Blockinformationen, wo der Knoten gespeichert ist. Im letzteren Fall nutzen wir die folgenden 31 Bits, um die Block-ID zu speichern, und die restlichen 32 Bits, um den Offset zu speichern.

In der folgenden Abbildung sehen Sie eine visuelle Darstellung von DuckDBs Swizzlable Pointer.

Benchmarks

Um die Vorteile und Nachteile unserer aktuellen Speicherimplementierung zu bewerten, führen wir einen Benchmark aus (verfügbar unter diesem Colab-Link), bei dem wir eine Tabelle mit 50.000.000 integralen Elementen mit einem Primary-Key-Constraint darauf anlegen.

con = duckdb.connect("vault.db")
con.execute("CREATE TABLE integers (x INTEGER PRIMARY KEY)")
con.execute("INSERT INTO integers SELECT * FROM range(50000000)")

Wir führen diesen Benchmark auf zwei verschiedenen DuckDB-Versionen aus, einer, in der der Index nicht gespeichert wird (d. h. v0.4.0), was bedeutet, dass er immer im Speicher ist und bei einem Datenbankneustart vollständig rekonstruiert wird, und einer, in der der Index gespeichert wird (d. h. Bleeding-Edge-Version), mit der zuvor beschriebenen Lazy-Loading-Technik.

Speicherzeit

Wir messen zuerst die zusätzlichen Kosten, unseren Index zu serialisieren.

cur_time = time.time()
con.close()
print("Storage time: " + str(time.time() - cur_time))

Speicherzeit

Wir sehen, dass das Speichern des Index 2× teurer ist als das Nicht-Speichern des Index. Der Grund ist, dass unsere Tabelle aus einer Spalte mit 50.000.000 int32_t-Werten besteht. Beim Speichern des ART speichern wir aber auch 50.000.000 int64_t-Werte für ihre jeweiligen row_ids in den Blättern. Diese Zunahme der Elemente ist der Hauptgrund für die zusätzlichen Speicherkosten.

Ladezeit

Wir messen jetzt die Ladezeit beim Neustart unserer Datenbank.

cur_time = time.time()
con = duckdb.connect("vault.db")
print("Load time: " + str(time.time() - cur_time))

Hier sehen wir einen Unterschied von zwei Größenordnungen bei den Ladezeiten der Datenbank. Dieser Unterschied geht im Wesentlichen auf die vollständige Rekonstruktion des ART-Index während des Ladens zurück. In der Storage-Version werden an diesem Punkt nur die Metadateninformationen über den ART-Index geladen.

Query-Zeit (kalt)

Wir messen jetzt die kalte Query-Zeit (d. h. die Datenbank wurde gerade neu gestartet, das heißt in der Storage-Version existiert der Index noch nicht im Speicher) beim Ausführen von Point-Queries auf unserem Index. Wir führen 5000 Point-Queries aus, gleichmäßig verteilt auf 10000 Elemente in unserer Verteilung. Wir nutzen diesen Wert, um die Point-Queries immer dazu zu zwingen, eine große Zahl ungenutzter Knoten zu laden.

times = []
for i in range (0, 50000000, 10000):
  cur_time = time.time()
  con.execute("SELECT x FROM integers WHERE x = " + str(i))
  times.append(time.time() - cur_time)

Im Allgemeinen ist jede Abfrage im persistierten Speicherformat 3× teurer. Das hat zwei Hauptgründe:

• Das Anlegen der Knoten. In der Storage-Version legen wir die Knoten lazy an, das heißt für jeden Knoten müssen alle Parameter alloziert werden, und Werte wie Schlüssel und Präfixe werden geladen.
• Block-Pinning. Bei jedem Knoten müssen wir die Blöcke, in denen sie gespeichert sind, pinnen und unpinnen.

Query-Zeit (heiß)

In diesem Experiment führen wir dieselben Abfragen wie im vorherigen Abschnitt aus.

Die Zeiten in beiden Versionen sind vergleichbar, weil alle Knoten in der Storage-Version bereits im Speicher gesetzt sind. Fazit: Wenn gespeicherte Indexes aktiv genutzt werden, zeigen sie ähnliche Performance wie vollständig In-Memory-Indexes.

Zukünftige Arbeit

ART-Index-Speicherung war ein lange bestehendes Issue in DuckDB, und mehrere Nutzer haben gesagt, es sei ein fehlendes Feature, das ein Hindernis für sie war, DuckDB zu nutzen. Obwohl das Speichern und Lazy-Laden von ART-Indexes jetzt möglich ist, gibt es viele zukünftige Wege, die wir noch verfolgen können, um den ART-Index performanter zu machen. Hier liste ich, was ich für die wichtigsten nächsten Schritte halte:

1. Caching gepinnter Blöcke. In unserer aktuellen Implementierung werden Blöcke ständig gepinnt und ungepinnt, obwohl Blöcke mehrere Knoten speichern können und bei Lookups höchstwahrscheinlich durchgehend wiederverwendet werden. Sie klug zu cachen führt zu drastischen Einsparungen bei Abfragen, die Knotenladen auslösen.
2. Bulk Loading. Unser ART-Index unterstützt derzeit kein Bulk Loading. Das bedeutet, dass Knoten beim Anlegen eines Index über eine Spalte ständig resized werden, weil Elemente eins nach dem anderen eingefügt werden. Laden wir die Daten im Bulk, können wir genau wissen, welche Knoten wir für diesen Datensatz anlegen müssen, und diese häufigen Resizes vermeiden.
3. Bulk Insertion. Beim Bulk Insertion würde ein ähnliches Problem wie beim Bulk Loading auftreten. Eine mögliche Lösung wäre, einen neuen ART-Index mit Bulk Loading anzulegen und ihn dann mit dem bestehenden ART-Index zu mergen.
4. Vektorisierte Lookups/Inserts. DuckDB nutzt eine vektorisierte Ausführungsengine. Sowohl unsere ART-Lookups als auch Inserts folgen aber noch einem Tuple-at-a-Time-Modell.
5. Aktualisierbare Indexspeicherung. In unserer aktuellen Implementierung werden ART-Indexes vollständig von der Platte invalidiert und erneut gespeichert. Das verursacht einen unnötigen Anstieg der Speicherzeit bei nachfolgenden Speicherungen. Knoten direkt auf die Platte zu aktualisieren statt den Index vollständig neu zu schreiben, könnte zukünftige Speicherkosten drastisch senken. Anders gesagt: Indexes werden bei jedem Checkpoint ständig vollständig gespeichert.
6. Kombinierte Pointer/Row-ID-Blätter. Unser aktuelles Leaf-Knoten-Format erlaubt das Speichern von Werten, die über mehrere Tuples wiederholt vorkommen. Da ART-Indexes aber üblicherweise genutzt werden, um Unique-Key-Constraints zu halten (z. B. Primary Keys), und eine eindeutige row_id in denselben Pointer-Größenraum passt, kann viel Platz gespart werden, indem die Kind-Pointer auf die eigentliche row_id zeigen, statt einen echten Blattknoten anzulegen, der nur eine row_id speichert.

Roadmap

It’s tough to make predictions, especially about the future
– Yogi Berra

ART-Indexes sind ein Kernteil sowohl der Constraint-Durchsetzung als auch der Zugriffsgeschwindigkeit in DuckDB. Und wie im vorherigen Abschnitt dargestellt, gibt es viele verschiedene Wege, die wir in unserer Tüte voller ART-Goodies einschlagen können, mit Vorteilen für völlig unterschiedliche Einsatzfälle.