2025-05-14

Sortieren beim Einfügen für schnelle selektive Abfragen

Alex Monahan

Der schnellste Weg, Daten zu lesen, ist, Daten nicht zu lesen. So einfach ist das! Dieser Beitrag dreht sich darum, so wenig Daten wie möglich zu lesen, um selektive Leseabfragen zu beantworten.

Springen Sie gern direkt zu den Best Practices!

Use Cases

Diese Techniken sind am nützlichsten, wenn Leseperformance kritischer ist als Schreibperformance. Dann können wir bewusst Ordnungsschritte einbauen, die das Schreiben verlangsamen, das Lesen aber stark beschleunigen. Das ist oft der Fall, wenn Daten im Hintergrund vorverarbeitet werden, Leseabfragen aber kundenseitig in einem Dashboard oder einer App laufen.

Sortieren hilft in jeder dieser Situationen:

• Ihr Datensatz ist groß und passt nicht vollständig in den Speicher
• Sie wollen pro Abfrage nur einen Teil Ihres Datensatzes lesen
• Sie greifen über HTTP(S) auf Ihre Daten zu
• Ihre Daten liegen in der Cloud auf Object Storage wie AWS S3

Dieser Überblick beschreibt das DuckDB-Dateiformat, aber dank DuckDBs Partial-Reading-Unterstützung lassen sich diese Techniken allgemein auf fast jedes spaltenorientierte Dateiformat oder jede Datenbank anwenden. Das ist ein großartiger Weg, das Abfragen von Apache-Parquet-Dateien auf entfernten Endpunkten zu beschleunigen – einschließlich Data Lakes!

Bleiben Sie dran für einen Folgebeitrag zu fortgeschrittenem Mehrspalten-Sortieren!

Wie hilft das DuckDB-Format?

Bauen wir etwas Intuition zur Struktur des DuckDB-Dateiformats auf! DuckDB speichert Daten in einer einzelnen Datei. Jede Datei heißt Datenbank (die DuckDB-Bibliothek ist die Datenbank-Engine).

Jede Datenbankdatei kann mehrere Tabellen, Sichten, Funktionen, Indizes und Primär-/Fremdschlüssel-Beziehungen in derselben Datei speichern. Das hat Vorteile für die Portabilität, erlaubt man aber auch, mehr als nur Daten zu speichern – auch Metadaten. Diese Metadaten erlauben der DuckDB-Engine, selektiv nur Teile der DuckDB-Datei zu lesen, wenn sie angefordert werden – entscheidend für Larger-than-Memory-Datensätze und für die Performance-Optimierungen in diesem Beitrag!

DuckDB speichert Daten spaltenorientiert (das heißt, Werte einer Spalte liegen zusammen in derselben Menge von Blöcken). Spaltenorientiert heißt aber nicht, die gesamte Spalte zusammenhängend zu speichern! Vor dem Speichern zerlegt DuckDB Tabellen in Zeilen-Chunks, sogenannte Row Groups. Jede Row Group hat standardmäßig 122 880 Zeilen.

Als Nächstes zoomen wir in Row Group 1 aus Table 1 im ersten Diagramm:

Innerhalb jeder Row Group liegen die Daten einer einzelnen Spalte zusammenhängend auf der Platte in einem oder mehreren Blöcken. DuckDB komprimiert diese Daten, um die Dateigröße zu reduzieren.

Zone Maps nutzen, um das Lesen von Daten zu überspringen

Wie hilft das Speichern in Spalten bei selektiven Leseabfragen? Allein tut es das nicht! Am Anfang der Spaltendaten in jeder Row Group speichert DuckDB aber auch Metadaten über die gespeicherten Spaltendaten. Dazu gehören die Minimal- und Maximalwerte dieser Spalte in dieser Row Group. Wir nennen das Zone Maps oder Min-Max-Indizes.

Wenn DuckDB eine SQL-Abfrage mit Filter erhält, prüft es vor dem Lesen der Spaltensegmente von der Platte zuerst die Metadaten. Könnte dieser Filterwert im Min-/Max-Bereich dieses Spaltensegments liegen? Wenn nicht, kann DuckDB das Lesen der Daten in dieser gesamten Row Group überspringen.

Zum Beispiel speichert Column N in diesem Beispiel die Abkürzungen US-amerikanischer Bundesstaaten. Wenn wir Daten für den Staat VA (Virginia) abfragen, könnte diese Row Group Daten für VA enthalten? Unsere Abfrage könnte so aussehen:

FROM "Table 1"
WHERE "Column N" = 'VA';

DuckDBs freundliches SQL macht das traditionelle SQL-SELECT * optional!

DuckDB prüft zuerst die Zone Map (im Diagramm als Column N Metadata beschriftet). Fällt VA (alphabetisch) in den Bereich von AZ bis PA? Nein! Wir können diese gesamte Row Group überspringen.

Wenn wir stattdessen nach dem Staat NM (New Mexico) filtern, zeigt die Zone Map, dass NM-Daten in dieser Row Group möglich sind. DuckDB holt daher die gesamte Spalte (möglicherweise von einem entfernten Ort) und prüft jede Zeile, ob NM-Daten existieren. Laut Diagramm gibt es in dieser Row Group keine NM-Daten, das Holen und Prüfen jeder Zeile wäre also unnötiger Aufwand. Alle 122 880 Zeilen müssten geprüft werden! Wenn die Zone-Map nur einen kleineren Bereich von Staatsabkürzungen abdecken würde…

Strategisch Daten überspringen

Unser Ziel ist, Daten so zu sortieren, dass die Zone Maps für die Spalten, nach denen wir filtern wollen, so selektiv wie möglich sind. Wenn der Min-Max-Index dieser Row Group nur von AZ bis CA reichte, wären die Daten viel eher überspringbar. Anders gesagt: Jede Teilmenge der Daten, die wir holen wollen, sollte nur in wenigen Row Groups liegen. Wir wollen nicht jede Row Group holen und jede Zeile prüfen! Staaten, die früh im Alphabet stehen, sollten zum Beispiel in derselben Row Group zusammenliegen.

Bei selektiven Abfragen können Sie darauf zielen, nur eine einzelne Row Group zu holen! Da DuckDBs Multithreading-Modell aber auf Row Groups basiert, sollten Sie hohe Performance sehen, solange die Zahl der Row Groups kleiner ist als die Zahl der Threads (≈CPU-Kerne), die DuckDB nutzt.

Sortier-Best-Practices

Es gibt viele Faustregeln, wie man Min-Max-Indizes am besten nutzt, weil ihre Wirksamkeit stark von Daten und Workload abhängt. Sie gelten sowohl in DuckDB als auch in anderen spaltenorientierten Formaten wie Apache Parquet oder anderen spaltenorientierten Datenbanken. Hier einige Ansätze!

Bei der Entscheidung, welche Spalten sortiert werden, ist es entscheidend, die WHERE-Klauseln aller Lese-Workloads zu prüfen. Oft ist der wichtigste Faktor, welche Spalten am häufigsten zum Filtern genutzt werden. Ein grundlegender Ansatz wäre, nach allen Filterspalten zu sortieren, beginnend mit den am häufigsten genutzten.

Eine andere Option, wenn die Workload nach mehreren unterschiedlichen Spalten filtert, ist, zuerst nach Spalten mit der niedrigsten Kardinalität (den wenigsten eindeutigen Werten) zu sortieren. Es kann zum Beispiel helfen, zuerst nach einem groben customer_type und dann nach einer eindeutigen customer_id zu sortieren.

Oft ist es nützlich, nur aktuelle Daten zu lesen, daher kann es die Performance verbessern, wenn aktuelle Daten nicht über die ganze Tabelle verteilt sind. Beim Sortieren nach Zeitstempeln sollten Sie aber bedenken, dass Zeitstempel oft sehr hohe Kardinalität haben. Deshalb kann es helfen, zuerst nach Spalten mit niedrigerer Kardinalität zu sortieren. Sie könnten versucht sein, zuerst nach dem Zeitstempel zu sortieren – widerstehen Sie dieser Versuchung! (oder testen Sie zumindest Alternativen). Es kann sinnvoller sein, nach einem auf Woche, Monat oder Jahr gerundeten Zeitstempel und dann nach anderen Spalten zu sortieren.

Um von Min-Max-Indizes zu profitieren, muss eine WHERE-Klausel direkt auf einer konkreten Spalte filtern, nicht auf einem berechneten Ausdruck. Wird ein Ausdruck genutzt, muss er für jede Zeile ausgewertet werden, und keine Row Group kann übersprungen werden!

Weitere Techniken

Es gibt weitere Wege, Min-Max-Indizes in DuckDB voll auszunutzen!

Kleine Inserts vermeiden

Wenn eine Workload Daten in kleinen Batches oder zeilenweise einfügt, gibt es keine Gelegenheit, die Daten beim Einfügen effektiv zu sortieren. Stattdessen werden die Daten weitgehend nach Einfügezeit sortiert, was nur für zeitbasierte Filter effektives Pruning liefert. Wenn möglich, erlauben Bulk-Inserts oder Batching, dass das Sortieren für andere Spalten besser wirkt. Als Alternative kann es einen periodischen Neu-Sortier-Job geben, analog zu einem Re-Indexing in transaktionalen Systemen.

In Chunks sortieren

Sortieren kann für große Tabellen rechnerisch teuer sein. Ein Weg, den benötigten Speicher (oder Disk Spill) beim Sortieren zu reduzieren, ist, die Tabelle stückweise zu verarbeiten: mehrere SQL-Anweisungen in einer Schleife, jeweils auf einen bestimmten Chunk gefiltert. Da SQL kein Schleifenkonstrukt hat, übernimmt das eine Host-Sprache (Python, Jinja-Templating usw.). Der Pseudocode wäre:

CREATE OR REPLACE TABLE sorted_table AS
    FROM unsorted_table
    WITH NO DATA;

for chunk in chunks:
    INSERT INTO sorted_table
        FROM unsorted_table
        WHERE chunking_column = chunk
        ORDER BY other_columns...;

Das hat den Effekt, zuerst nach der Chunking-Spalte und dann nach den other_columns zu sortieren. Es kann auch länger dauern (weil die Daten einmal pro Chunk gescannt werden müssen), der Speicherverbrauch ist aber wahrscheinlich deutlich niedriger.

Die ersten Zeichen von Strings sortieren

Ungefähres Sortieren reicht oft, um die Leseperformance zu verbessern. In den Zone Maps von VARCHAR-Spalten speichert DuckDB nur die ersten 8 Bytes der Min- und Max-Stringwerte. Es ist also nicht nötig, mehr als die ersten 8 Bytes (8 ASCII-Zeichen) zu sortieren!

Das hat den zusätzlichen Vorteil schnelleren Sortierens, weil die Laufzeit von DuckDBs Radix-Sort-Algorithmus empfindlich auf die Länge der Strings reagiert (absichtlich!). Die Zeitkomplexität des Algorithmus ist O(nk), wobei n die Zahl der Zeilen und k die Breite des Sortierschlüssels ist. Nur nach den ersten paar Zeichen eines VARCHAR zu sortieren kann schneller und weniger rechenintensiv sein und ähnliche Leseperformance erreichen. DuckDBs VARCHAR-Datentyp inlined Strings außerdem, wenn sie unter 12 Bytes liegen, sodass die Arbeit mit kurzen Strings auch deshalb schneller ist. Zum Beispiel:

CREATE OR REPLACE TABLE sorted_table AS
    FROM unsorted_table
    ORDER BY varchar_column_to_sort[:8];

DuckDBs freundliches SQL erlaubt Klammer-Notation für String-Slicing!

Nach mehr Spalten filtern

Filter in einer WHERE-Klausel hinzuzufügen kann helfen, wenn diese Spalten irgendeine ungefähre Ordnung haben. Statt nur nach customer_id zu filtern, nehmen Sie customer_type mit in die Abfrage, wenn die Tabelle danach sortiert ist. Oft kennt man zur Query-Zeit neben der customer_id auch andere Metadaten.

Die Row-Group-Größe anpassen

Ein Parameter, der für konkrete Workloads getunt werden kann, ist die Zahl der Zeilen in einer Row Group (ROW_GROUP_SIZE). Wenn es viele eindeutige Werte in einer Filterspalte gibt, kann eine kleinere Zeilenzahl pro Row Group die Gesamtzahl der zu scannenden Zeilen reduzieren. Es gibt aber Overhead durch häufigeres Prüfen von Metadaten bei kleineren Row Groups, es gibt also einen Trade-off.

Eine größere Row-Group-Größe kann vorzuziehen sein, wenn eine Tabelle besonders groß ist und Abfragen sehr selektiv sind. Zum Beispiel, wenn Sie eine große Fact-Tabelle mit Jahren Historie abfragen, aber nur auf die letzte Woche filtern. Größere Row Groups reduzieren die Zahl der Metadatenprüfungen, die nötig sind, um die aktuellen Daten zu erreichen. Jede Row Group ist aber größer, also gibt es auch dort einen Trade-off.

Um die Row-Group-Größe anzupassen, übergeben Sie einen Parameter beim Anhängen einer Datenbank. Hinweis: Eine Row-Group-Größe sollte eine Zweierpotenz sein. Die minimale Row-Group-Größe ist 2 048, die Vektorgröße von DuckDB.

ATTACH './smaller_row_groups.duckdb' (ROW_GROUP_SIZE 8_192);

Ausblick auf den nächsten Beitrag der Serie

Ein Folgebeitrag dieser Serie wird fortgeschrittene Sortiertechniken behandeln. Die können die Performance steigern, wenn mehrere Leser-Workloads mit unterschiedlichen Filtern denselben Datensatz abfragen. Was zum Beispiel, wenn ich für manche Abfragen nach US-Staat filtern muss, für andere nach Nachnamen der Kundschaft? Außerdem kann das Sortieren nach gerundeten Zeit-Buckets (Tag, Monat oder Jahr) und dann nach anderen Spalten helfen, wenn nur aktuelle Daten gebraucht werden.

Mikrobenchmarks werden die 10×-Performance-Vorteile zeigen, die am Anfang dieses Beitrags erwähnt wurden! Der Beitrag wird auch Wege zeigen, zu messen, wie effektiv eine Tabelle entlang verschiedener Spalten sortiert ist.

Fazit

Daten beim Einfügen zu ordnen kann Leseabfragen mit Filtern deutlich beschleunigen. Sobald Ihr Datensatz groß wird oder Sie ihn remote speichern, sollten Sie diese Techniken in Betracht ziehen. Und diese Ansätze funktionieren in fast jedem spaltenorientierten Dateiformat oder jeder Datenbank!

Viel Spaß beim Analysieren!