Ausführungsformat

Vector ist das Containerformat, in dem Daten zur Laufzeit im Speicher gehalten werden. DataChunk ist eine Sammlung von Vectors, etwa um eine Spaltenliste in einem PhysicalProjection-Operator darzustellen.

Datenfluss

DuckDB verwendet ein vektorisiertes Query-Ausführungsmodell. Alle Operatoren in DuckDB sind darauf optimiert, mit Vectors fester Größe zu arbeiten.

Diese feste Größe wird im Code üblicherweise als STANDARD_VECTOR_SIZE bezeichnet. Die Standard-STANDARD_VECTOR_SIZE beträgt 2048 Tupel.

Vektorformat

Vectors stellen logisch Arrays dar, die Daten eines einzelnen Typs enthalten. DuckDB unterstützt verschiedene Vektorformate, mit denen dasselbe logische Datum in einer anderen physischen Darstellung gespeichert werden kann. Das ermöglicht eine kompaktere Darstellung und potenziell komprimierte Ausführung im gesamten System. Im Folgenden sind die unterstützten Vektorformate aufgeführt.

Flache Vektoren

Flache Vektoren sind physisch als zusammenhängendes Array gespeichert; das ist das Standardformat ohne Komprimierung. Bei flachen Vektoren sind logische und physische Darstellung identisch.

Konstantenvektoren

Konstantenvektoren sind physisch als einzelner konstanter Wert gespeichert.

Konstantenvektoren sind nützlich, wenn Datenelemente wiederholt werden – etwa beim Ergebnis eines konstanten Ausdrucks in einem Funktionsaufruf: Der Konstantenvektor speichert den Wert nur einmal.

SELECT lst || 'duckdb'
FROM range(1000) tbl(lst);

Da duckdb ein String-Literal ist, ist der Wert des Literals in jeder Zeile derselbe. In einem flachen Vektor müssten wir das Literal ‘duckdb’ für jede Zeile duplizieren. Der Konstantenvektor erlaubt es, das Literal nur einmal zu speichern.

Konstantenvektoren werden vom Speicher auch beim Dekomprimieren aus konstanter Komprimierung erzeugt.

Dictionary-Vektoren

Dictionary-Vektoren sind physisch als Kindvektor plus Selektionsvektor gespeichert, der Indizes in den Kindvektor enthält.

Dictionary-Vektoren werden vom Speicher beim Dekomprimieren aus Dictionary-Komprimierung erzeugt.

Wie Konstantenvektoren werden Dictionary-Vektoren ebenfalls vom Speicher erzeugt. Beim Deserialisieren eines dictionary-komprimierten Spaltensegments speichern wir es in einem Dictionary-Vektor, damit die Daten während der Query-Ausführung komprimiert bleiben.

Sequenzvektoren

Sequenzvektoren sind physisch als Offset und Inkrementwert gespeichert.

Sequenzvektoren eignen sich, um aufsteigende Folgen effizient zu speichern. Sie werden in der Regel für Zeilenkennungen erzeugt.

Unified-Vektorformat

Diese Eigenschaften der verschiedenen Vektorformate eignen sich gut zur Optimierung: Sind etwa alle Parameter einer Funktion konstant, können wir das Ergebnis einmal berechnen und einen Konstantenvektor ausgeben. Spezialisierten Code für jede Kombination von Vektortypen in jeder Funktion zu schreiben, ist wegen der kombinatorischen Explosion aber nicht praktikabel.

Stattdessen kann, wenn ein Vektor unabhängig vom Typ generisch genutzt werden soll, das UnifiedVectorFormat verwendet werden. Dieses Format wirkt im Wesentlichen als generische Sicht auf den Inhalt des Vectors. Jeder Vector-Typ kann in dieses Format konvertiert werden.

Komplexe Typen

String-Vektoren

Zum effizienten Speichern von Strings nutzen wir unsere Klasse string_t.

struct string_t {
    union {
        struct {
            uint32_t length;
            char prefix[4];
            char *ptr;
        } pointer;
        struct {
            uint32_t length;
            char inlined[12];
        } inlined;
    } value;
};

Kurze Strings (<= 12 bytes) werden in die Struktur eingebettet, größere Strings werden mit einem Zeiger auf die Daten im zusätzlichen String-Puffer gespeichert. Die Länge wird in den Funktionen durchgängig genutzt, um strlen zu vermeiden und nicht ständig auf Null-Zeiger prüfen zu müssen. Das Präfix dient bei Vergleichen als früher Abbruch (stimmt das Präfix nicht, wissen wir, dass die Strings ungleich sind, und müssen keinen Zeigern folgen).

List-Vektoren

List-Vektoren sind als Folge von Listeneinträgen zusammen mit einem Kind-Vector gespeichert. Der Kindvektor enthält die Werte, die in der Liste vorkommen, und die Listeneinträge legen fest, wie jede einzelne Liste aufgebaut ist.

struct list_entry_t {
    idx_t offset;
    idx_t length;
};

Der Offset verweist auf die Startzeile im Kind-Vector, die Länge hält die Größe der Liste dieser Zeile fest.

List-Vektoren können rekursiv gespeichert werden. Bei verschachtelten List-Vektoren ist das Kind eines List-Vektors wieder ein List-Vektor.

Betrachten Sie als Beispiel diese nachgestellte Darstellung eines Vectors vom Typ BIGINT[][]:

{
   "type": "list",
   "data": "list_entry_t",
   "child": {
      "type": "list",
      "data": "list_entry_t",
      "child": {
         "type": "bigint",
         "data": "int64_t"
      }
   }
}

Struct-Vektoren

Struct-Vektoren speichern eine Liste von Kindvektoren. Anzahl und Typen der Kindvektoren sind durch das Schema des Structs festgelegt.

Map-Vektoren

Intern sind Map-Vektoren als LIST[STRUCT(key KEY_TYPE, value VALUE_TYPE)] gespeichert.

Union-Vektoren

Intern nutzt UNION dieselbe Struktur wie ein STRUCT. Das erste „Kind“ ist immer der Tag-Vektor der UNION, der für jede Zeile festhält, welcher der UNION-Typen auf diese Zeile zutrifft.