2025-03-07

Parquet-Bloom-Filter in DuckDB

Hannes Mühleisen

Ein zentrales Feature des Parquet-Dateiformats ist, dass Reader selektiv nur die Daten lesen können, die für eine bestimmte Query relevant sind. Dazu enthalten Parquet-Dateien Spalten-Statistiken, vor allem Minimum und Maximum jeder Spalte in jeder Row Group. Filtert eine Query nach einem bestimmten Wert und sind die Daten – wie oft – einigermaßen sortiert, kann ein Reader „beweisen“, dass eine bestimmte Row Group keine relevanten Werte enthalten kann. DuckDB nutzt das intensiv und kann – auch bei Remote-Endpunkten – gezielt nur die für die Query relevanten Teile einer Parquet-Datei lesen. Details dazu im inzwischen betagten Blogbeitrag „Querying Parquet with precision using DuckDB“.

Dieser Ansatz hat aber Grenzen. Was, wenn die Spaltendaten zufällig gemischt sind? Dann kommen alle Werte in allen Row Groups vor, und Min-/Max-Statistiken nützen weniger, weil wir nur Werte außerhalb des Minimums und Maximums der gesamten Spalte ausschließen können. Parquet nutzt Dictionary Encoding, wenn es nicht zu viele unterschiedliche Werte in der Spalte gibt. Theoretisch könnte man das Dictionary nutzen, um Row Groups auszuschließen – aber es gibt zwei Probleme: Parquet erlaubt (unerklärlicherweise) den Wechsel von Dictionary- zu Plain-Encoding mitten in einer Row Group. Würde man nur das Dictionary zum Ausschluss nutzen, die Plain-Daten aber den gesuchten Wert enthalten, wären die Ergebnisse falsch. Außerdem ist das Dictionary Teil der eigentlichen Spaltendaten. Liest man die Spaltendaten nur wegen des Dictionarys, hat man die Kosten des Spaltenlesens schon weitgehend getragen.

Obskure Randnotiz: Theoretisch enthält die Spalten-Metadatenliste die Encodings, die in der Spalte vorkommen. Wenn diese Liste korrekt ist und kein Plain-Encoding enthält, könnte das Dictionary – wieder theoretisch – für etwas früheren Row-Group-Ausschluss genutzt werden. Der Nutzen ist aber mehr als zweifelhaft.

Parquet-Bloom-Filter

Die guten Leute beim Parquet PMC haben erkannt, dass es hier Verbesserungspotenzial gibt, und 2018 Bloom-Filter für Parquet ergänzt. Kurz gesagt sind Bloom-Filter kompakte, aber näherungsweise Indexstrukturen für eine Wertemenge. Für einen gegebenen Wert können sie entweder mit Sicherheit sagen, dass ein Wert nicht in der Menge ist, oder dass er möglicherweise in der Menge ist – mit einer False-Positive-Rate, die von der Größe des Bloom-Filters und der Zahl der eingefügten unterschiedlichen Werte abhängt. Vorerst behandeln wir einen Bloom-Filter einfach als undurchsichtige Bytefolge mit magischen Eigenschaften.

Wenn genutzt, können Parquet-Dateien einen Bloom-Filter für jede Spalte in jeder Row Group enthalten. Jeder Bloom-Filter kann an einer beliebigen Stelle in der Datei liegen (bloom_filter_offset). Am Offset finden wir eine weitere Thrift-kodierte Struktur, den BloomFilterHeader. Diese Struktur hat ein Feld für die Filterlänge und einige algorithmische Einstellungen, die derzeit redundant sind, weil es für alle nur eine gültige Einstellung gibt. Den Header muss man aber dekodieren, um zu wissen, wo der Header endet und die Filterbytes beginnen. Dann haben wir die kostbaren magischen Bytes des Bloom-Filters. Jetzt können wir den Filter gegen Query-Prädikate testen und sehen, ob wir die Row Group ganz überspringen können.

Weitere obskure Randnotizen: Die Spalten-Metadaten haben ein Feld für die Filtergröße (bloom_filter_length), es ist aber optional, und manche Writer (hallo, Spark) setzen ärgerlicherweise nur den Offset, nicht die Länge. Die Spezifikation beschreibt außerdem zwei mögliche Filterpositionen. Ohne erforderliche Länge in den Metadaten ist es schwierig bis unmöglich, alle Bloom-Filter einer Parquet-Datei in einer einzigen Range-Anfrage zu lesen. Auch unklar: Warum musste jeder Filter mit einem Thrift-Metadaten-Blob beginnen, wenn diese Information auch in den ColumnMetaData stehen könnte. Oder, Gott bewahre, die Filter hätten Teil der Haupt-Parquet-Metadaten werden können. Am Ende entstehen viele zusätzliche Reads, um die Bloom-Filter-Bytes zu finden und zu lesen – im Prinzip ein vorsichtiger Trade-off zwischen dem Lesen der Filter und dem „einfachen“ brute-force-Lesen der Spalte.

DuckDB-Bloom-Filter

Seit dem letzten Feature-Release (1.2.0) unterstützt DuckDB sowohl das Lesen als auch das Schreiben von Parquet-Bloom-Filtern. Das geschieht völlig transparent für die Nutzer, es ist keine zusätzliche Aktion oder Konfiguration nötig.

Schreiben

Derzeit werden Bloom-Filter für folgende Typen unterstützt:

• Integer-Typen (TINYINT, UTINYINT, SMALLINT, USMALLINT, INTEGER, UINTEGER, BIGINT, UBIGINT)
• Gleitkommatypen (FLOAT, DOUBLE)
• String-Typen (VARCHAR und BLOB)

Verschachtelte Typen (Listen, Structs, Arrays) werden derzeit nicht unterstützt, könnten aber in einem künftigen Release kommen. Allgemein werden Bloom-Filter geschrieben, wenn DuckDB für eine bestimmte Spalte (Chunk) in der Row Group Dictionary Encoding wählt. Es gibt einen COPY-Parameter für die maximale Dictionary-Größe (DICTIONARY_SIZE_LIMIT); standardmäßig sind das 10 % der Row-Group-Größe (ROW_GROUP_SIZE), die standardmäßig 122.880 Zeilen beträgt. Diese Werte haben sich als vernünftige erste Näherung für die meisten Fälle erwiesen; bei Performance-Problemen sollten Nutzer mit beiden Parametern experimentieren. Wächst die Zahl unterschiedlicher Werte in einem Bloom-Filter, muss seine Größe steigen, um eine bestimmte False-Positive-Rate zu halten. Standardmäßig wird die Filtergröße für eine „akzeptable“ False-Positive-Rate von 1 % bzw. 0,01 gewählt. Der neue COPY-Parameter BLOOM_FILTER_FALSE_POSITIVE_RATIO steuert die akzeptable Rate. Allgemein schaden False Positives umso mehr, je langsamer der Lesepfad ist.

Lesen

Beim Lesen nutzt DuckDB automatisch Konstanten-Vergleichs-Filterprädikate in der Query (z. B. WHERE a = 42), um den Bloom-Filter (falls vorhanden) zu prüfen und Row Groups zu überspringen, in denen der Bloom-Filter garantieren kann, dass es keine passenden Zeilen gibt. Auch das geschieht transparent, es gibt keine zu setzende Konfiguration.

Nutzer können feststellen, ob eine Parquet-Datei Bloom-Filter enthält: Die Funktion parquet_metadata wurde um zwei Spalten erweitert, bloom_filter_offset und bloom_filter_length. Um herauszufinden, welche Row Groups Bloom-Filter für eine Datei und Spalte ausschließen würden, gibt es die Funktion parquet_bloom_probe. Zum Beispiel liefert parquet_bloom_probe('file.parquet', 'col1', 42) eine Tabelle für jede Row Group in file.parquet, die angibt, ob der Wert 42 in dieser Row Group für Spalte col1 garantiert nicht vorkommt. Die meisten Nutzer brauchen diese Funktionen nicht; sie helfen beim Debuggen (und Testen).

Beispielanwendung

Schauen wir uns Parquet-Bloom-Filter in DuckDB an einem Beispiel an. Zuerst erzeugen wir eine Beispieldatei filter.parquet, die Bloom-Filter enthalten wird:

COPY (
    FROM range(10) r1, range(10_000_000) r2
    SELECT r1.range * 100 AS r
    ORDER BY random()
)
TO 'filter.parquet'
(FORMAT parquet, ROW_GROUP_SIZE 10_000_000);

SELECT r, count(*)
FROM 'filter.parquet'
GROUP BY r
ORDER BY r;

Die Datei enthält 10 unterschiedliche Werte (0, 100, 200 ... 900), jeweils zehn Millionen Mal. Insgesamt 100 Millionen Zeilen. Die entstehende Parquet-Datei wiegt 88 MB.

Wir erzeugen außerdem eine gleichwertige Datei ohne Bloom-Filter, indem wir DICTIONARY_SIZE_LIMIT auf 1 setzen:

COPY 'filter.parquet' to 'nofilter.parquet'
(FORMAT parquet, DICTIONARY_SIZE_LIMIT 1, ROW_GROUP_SIZE 10_000_000);

Der Inhalt beider Dateien ist gleichwertig, aber nofilter.parquet nutzt kein Dictionary Encoding und damit keine Bloom-Filter. Die Datei ist deshalb größer: 181 MB. Der Unterschied beim Abfragen nicht vorhandener Werte, in unserem Beispiel 501, ist aber viel größer:

.timer on
SELECT sum(r) FROM 'filter.parquet'   WHERE r = 501;
SELECT sum(r) FROM 'nofilter.parquet' WHERE r = 501;

Die erste Query ist in ca. 0,002 s fertig, die zweite braucht 0,1 s. Dieser große Unterschied erklärt sich durch Bloom-Filter! Da 501 in der Query nicht vorkommt, kann DuckDB automatisch alle Row Groups ausschließen und außer den Bloom-Filtern keine Daten lesen. Das können wir mit parquet_metadata genauer ansehen:

FROM parquet_metadata('filter.parquet')
SELECT row_group_id, stats_min, stats_max,
    bloom_filter_offset, bloom_filter_length
ORDER BY row_group_id;

Es gibt zehn Row Groups, und für jede einen recht kompakten Bloom-Filter mit 47 Bytes. Das sind ca. 500 Bytes extra in einer ziemlich großen Datei – für die Dateigröße eher irrelevant.

Führen wir die Query auf der anderen Datei aus, sehen wir das Fehlen der Bloom-Filter:

FROM parquet_metadata('nofilter.parquet')
SELECT row_group_id, stats_min, stats_max,
       bloom_filter_offset, bloom_filter_length
ORDER BY row_group_id;

Die Bloom-Filter in der Datei können wir mit parquet_bloom_probe weiter erkunden. Für den Wert 500 (der in den Daten vorkommt) zeigt die Funktion:

FROM parquet_bloom_probe('filter.parquet', 'r', 500);

Der Bloom-Filter kann keine Row Group ausschließen, weil der Wert 500 in allen Row Groups vorkommt. Bei einem nicht vorhandenen Wert schlägt der Bloom-Filter zu:

FROM parquet_bloom_probe('filter.parquet', 'r', 501);

Hier können wir alle Row Groups sicher überspringen, weil der Bloom-Filter garantiert, dass es keine passenden Werte gibt. Alles das mit 47 Bytes pro Row Group.

Fazit

DuckDBs neue Bloom-Filter-Unterstützung für Parquet-Dateien kann in bestimmten Szenarien die zu lesende Datenmenge stark reduzieren und die Query-Performance deutlich verbessern. Besonders nützlich ist das, wenn Dateien über eine langsame Netzwerkverbindung gelesen werden oder Row Groups besonders groß sind, mit wenigen unterschiedlichen, aber nicht geclusterten Werten.