Zero-Cost NDV Estimation from Columnar File Metadata

Each language version is independently generated for its own context, not a direct translation.

Stell dir vor, du bist ein Bibliothekar, der eine riesige, digitale Bibliothek verwaltet. Diese Bibliothek besteht aus vielen Regalen (den sogenannten "Row Groups"), und in jedem Regal stehen Bücher (die Datenzeilen). Deine Aufgabe ist es, einem Gast zu sagen: "Wie viele verschiedene Buchtitel gibt es insgesamt in dieser Bibliothek?" (Das nennt man im Fachjargon NDV – Number of Distinct Values).

Das Problem: Du darfst kein einziges Buch öffnen. Du darfst keine Seiten lesen. Du darfst auch keine neuen Zettel schreiben, um die Titel zu zählen. Du darfst nur auf die Etiketten auf den Regalen schauen.

Normalerweise wäre das unmöglich. Aber dieser Papier beschreibt einen genialen Trick, wie man das nur mit den vorhandenen Etiketten herausfinden kann – und das kostenlos, ohne Zeit oder Speicherplatz zu verschwenden.

Hier ist die Erklärung der zwei Haupt-Tricks, die der Autor verwendet:

Trick 1: Das Gewicht der Regale (Die Wörterbuch-Methode)

In vielen modernen Bibliotheken werden Bücher nicht einfach so hingedrückt. Wenn es viele Bücher mit demselben Titel gibt, schreibt man den Titel nur einmal auf eine Liste (ein "Wörterbuch") und klebt dann kleine Nummern an die Bücher, die auf diese Liste verweisen.

Die Idee: Der Autor schaut sich das Gewicht (die Größe) des Regals an.
Die Logik: Wenn das Regal schwer ist, aber die Bücher selbst eigentlich dünn sind, muss das "Wörterbuch" (die Liste der Titel) sehr lang gewesen sein.
Der Rechen-Trick: Er nimmt die bekannte Formel, wie viel Platz ein Wörterbuch braucht, und dreht sie um.
- Beispiel: "Wenn das Regal 10 kg wiegt und jedes Buch 100g wiegt, aber wir wissen, dass 5 kg nur für die Nummern-Liste draufgehen sind... dann müssen wir etwa 50 verschiedene Titel haben."
Wann es funktioniert: Wenn die Bücher in den Regalen gut gemischt sind (in jedem Regal sind viele verschiedene Titel).
Wann es scheitert: Wenn die Regale sortiert sind (Regal 1 hat nur "A", Regal 2 hat nur "B"). Dann denkt das System, es gäbe nur wenige Titel, weil die Liste kurz ist, obwohl es in Wahrheit viele verschiedene Titel im ganzen Gebäude gibt.

Trick 2: Die Extrem-Spitzen (Die Min/Max-Methode)

Jedes Regal hat ein kleines Schildchen mit zwei Zahlen: dem kleinsten und dem größten Wert, der in diesem Regal vorkommt.

Die Idee: Stell dir vor, du hast 50 Regale. Du schaust dir nur die kleinsten Werte jedes Regals an.
Der Rechen-Trick (Das "Gummibärchen-Spiel"): Stell dir vor, du hast einen Topf mit 100 verschiedenen Gummibärchenfarben (die verschiedenen Titel). Du greifst 50 Mal blind in den Topf (einmal pro Regal) und schaust, wie viele verschiedene Farben du dabei siehst.
- Wenn du in jedem Regal nur "A" und "B" siehst, hast du wahrscheinlich nur 2 Farben im Topf.
- Wenn du in Regal 1 "A", in Regal 2 "B", in Regal 3 "C" siehst, weißt du, dass der Topf viel mehr Farben hat.
Der Mathematische Zauber: Der Autor nutzt ein bekanntes mathematisches Modell (den "Coupon Collector"), um zu raten: "Wenn ich bei 50 Regalen schon 40 verschiedene Minima gesehen habe, wie viele Farben müssen dann insgesamt im Topf sein?"
Wann es funktioniert: Wenn die Bücher sortiert sind (Regal 1 hat "A-M", Regal 2 hat "N-Z"). Dann sind die Minima sehr unterschiedlich, und man kann die Gesamtzahl gut schätzen.
Wann es scheitert: Wenn alles wild durcheinander ist, sehen die Minima oft gleich aus, und man unterschätzt die Anzahl.

Der Schiedsrichter: Der "Verteilungs-Detektor"

Da beide Tricks unterschiedliche Stärken haben, braucht man einen Schiedsrichter. Das System schaut sich die Regale an:

Sind die Regale sortiert? (Die Minima ändern sich ständig?) -> Nimm Trick 2.
Sind die Regale wild gemischt? (Die Minima sind überall ähnlich?) -> Nimm Trick 1.
Ist es eine Mischung? -> Nimm das Ergebnis, das höher ist. (Besser, man schätzt etwas zu hoch als zu niedrig).

Warum ist das so toll?

Kostenlos: Man muss kein einziges Buch öffnen. Man liest nur die Etiketten auf den Regalen (die Metadaten), die ohnehin schon da sind.
Schnell: Es dauert nur einen kurzen Blick.
Nützlich für KI und Datenbanken: Wenn ein Computer wissen will, wie viel Arbeit eine Abfrage macht (z. B. "Wie viele verschiedene Kunden gibt es?"), kann er sofort planen, ohne erst alles durchsuchen zu müssen. Das spart Energie und Zeit, besonders auf schnellen Grafikprozessoren (GPUs).

Zusammenfassung in einem Satz

Der Autor hat einen Weg gefunden, die Anzahl der verschiedenen Dinge in einer riesigen Datenbank zu erraten, indem er einfach die Größe der Listen und die Extremwerte auf den Regaletiketten analysiert, ohne jemals den Inhalt der Regale zu öffnen – wie ein Detektiv, der nur anhand des Gewichts eines Koffers und der Temperatur am Rand schließt, was sich darin befindet.

Each language version is independently generated for its own context, not a direct translation.

Titel: Zero-Cost NDV-Schätzung aus Metadaten spaltenorientierter Dateien

Autor: Claude Brisson (VoltronData)

1. Problemstellung

Bei der Entwicklung von Theseus, einem GPU-beschleunigten, verteilten Abfrage-Engine, bestand ein dringender Bedarf an genauen Schätzungen der Anzahl der unterschiedlichen Werte (NDV – Number of Distinct Values) für Spalten. Diese Schätzungen sind essenziell für:

Kostenbasierte Abfrageoptimierung (z. B. Pushdown von Aggregationen, Join-Reihenfolge).
Zuweisung von GPU-Speicher für Kernel.

Das Hauptproblem ist, dass das distinct_count-Feld in Apache Parquet-Dateien fast nie gefüllt ist, da die exakte Berechnung zu teuer ist und die meisten Writer diese Information nicht speichern. Herkömmliche Alternativen wie Sampling oder die Wartung von HyperLogLog-Sketches erfordern entweder den Zugriff auf die Daten selbst oder zusätzliche Infrastruktur auf der Writer-Seite, was den Ansatz der reinen Metadaten-basierten Planung zunichtemacht.

Die zentrale Frage lautete: Welche Kardinalitätsinformationen sind bereits in den vorhandenen Metadaten (Dictionary-Encoding-Größe und Min/Max-Statistiken) implizit kodiert, ohne auf die eigentlichen Daten zuzugreifen?

2. Methodik

Der vorgestellte Ansatz nutzt zwei komplementäre Signale aus den Metadaten, um NDV zu schätzen, und leitet zwischen diesen basierend auf der Datenverteilung um.

A. Inversion der Dictionary-Encoding-Speichergleichung

Spaltenorientierte Formate (wie Parquet) speichern für Spalten mit niedriger bis mittlerer Kardinalität eine Dictionary-Seite und Daten-Seiten mit Bit-Packed-Indizes.

Grundgleichung: Die unkomprimierte Größe $S$ setzt sich zusammen aus der Dictionary-Größe und der Index-Größe:
$S = ndv \times len + (N - nulls) \times \lceil \log_2(ndv) \rceil / 8$
Dabei ist $ndv$ die gesuchte Anzahl der unterschiedlichen Werte, $len$ die durchschnittliche Byte-Länge eines Wertes, $N$ die Zeilenanzahl und $nulls$ die Anzahl der Null-Werte.
Lösung: Da $S$ , $N$ und $nulls$ bekannt sind und $len$ aus den Min/Max-Werten geschätzt werden kann, wird die Gleichung nach $ndv$ aufgelöst. Dies geschieht mittels der Newton-Raphson-Methode, wobei die Diskontinuität der Ceiling-Funktion durch eine kontinuierliche Approximation der Ableitung behandelt wird.
Gültigkeitsbereich: Diese Methode ist genau, wenn die unterschiedlichen Werte gut über die Row Groups (Zeilenblöcke) verteilt sind ("well-spread").

B. Min/Max-Diversitätsschätzung (Coupon Collector-Modell)

Parquet speichert pro Row Group Min- und Max-Werte.

Ansatz: Die Anzahl der verschiedenen Min-Werte ( $m_{min}$ ) und Max-Werte ( $m_{max}$ ) über alle $n$ Row Groups hinweg wird gezählt.
Modell: Dies wird als Coupon-Collector-Problem modelliert. Wenn man $n$ Row Groups betrachtet, entspricht dies dem Ziehen von $n$ Proben aus einer Population von $NDV$ Werten. Die erwartete Anzahl beobachteter Distinkter Werte ist:
$E[m] = NDV \times (1 - e^{-n/NDV})$
Inversion: Durch Umstellen dieser Gleichung (ebenfalls via Newton-Raphson) kann $NDV$ aus der beobachteten Anzahl der verschiedenen Min/Max-Werte rekonstruiert werden.
Gültigkeitsbereich: Diese Methode ist robust für sortierte oder partitionierte Daten, bei denen sich die Bereiche der Row Groups kaum überschneiden. Hier würde die Dictionary-Inversion die NDV unterschätzen.

C. Verteilungsdetektor und Hybrid-Ansatz

Ein leichter Detektor analysiert die Row-Group-Statistiken, um den Datenlayout-Typ zu klassifizieren:

Overlap-Ratio: Wie stark überschneiden sich die Bereiche aufeinanderfolgender Row Groups?
Monotonie: Gibt es einen klaren Trend in den Mittelpunkten der Bereiche?

Basierend darauf wird entschieden:

Bei gut verteilten Daten (hoher Overlap): Dictionary-Inversion ist bevorzugt.
Bei sortierten Daten (geringer Overlap): Min/Max-Diversität ist bevorzugt.
Hybrid-Ergebnis: Da beide Methoden in unterschiedlichen Szenarien unterschätzen, wird das Maximum beider Schätzwerte genommen, begrenzt durch die Anzahl der nicht-null Zeilen und typspezifische Obergrenzen (z. B. Bereich von Integer-Typen).

3. Wichtige Beiträge

Geschlossene Gleichung: Herleitung einer geschlossenen Formel, die NDV mit der Dictionary-Speichergröße verknüpft, und deren Lösung mittels Newton-Raphson.
Implizite Kardinalitäts-Skizzen: Die Erkenntnis, dass Min/Max-Statistiken von Row Groups als implizite Skizzen fungieren können, deren NDV durch Inversion des Coupon-Collector-Modells wiederhergestellt werden kann.
Dynamisches Routing: Entwicklung eines leichten Verteilungsdetektors, der automatisch zwischen den beiden Schätzern wählt.
Batch-Speichervorhersage: Anwendung des Coupon-Collector-Modells, um den benötigten Dictionary-Speicher für GPU-Batches vorherzusagen, ohne die Daten zu lesen.

4. Ergebnisse und Evaluation

Implementierung: Die Methode wurde in Theseus (VoltronData) implementiert und in Produktionsumgebungen getestet.
Genauigkeit:
- Für gut verteilte Spalten lagen die Fehler in der Regel unter 10 %.
- Bei sortierten Spalten konnte die systematische Unterschätzung der Dictionary-Inversion durch die Min/Max-Methode effektiv korrigiert werden.
Ressourcen: Die Schätzung erfolgt in O(n) Zeit (wobei $n$ die Anzahl der Row Groups ist) und benötigt O(1) zusätzlichen Speicherplatz. Es wird kein Zugriff auf die Datenseiten benötigt.
Verlust von Daten: Die ursprüngliche Implementierung und detaillierte experimentellen Daten gingen durch die Liquidierung von VoltronData verloren. Das Paper rekonstruiert den Ansatz aus dem Gedächtnis; eine Reproduktion auf öffentlichen Benchmarks ist geplant.

5. Bedeutung und Anwendungsbereiche

Zero-Cost-Optimierung: Ermöglicht präzise Kostenmodelle für Abfrageoptimierer, ohne zusätzliche I/O-Operationen oder Speicherplatz für Statistiken zu benötigen.
GPU- und Speicher-Management: Kritisch für die Vorhersage des Speicherverbrauchs von GPU-Kernels (Dictionary-Größe) vor der Ausführung.
Format-Unabhängigkeit: Obwohl an Parquet demonstriert, ist die Technik auf jedes spaltenorientierte Format anwendbar, das Dictionary-Encoding und Partition-Level-Statistiken unterstützt (z. B. ORC, F3).
Datenprofilierung: Bietet schnelle Einblicke in die Datenverteilung für Data-Engineering-Workflows.

Zusammenfassend demonstriert das Paper, dass Metadaten spaltenorientierter Dateien ausreichend Informationen enthalten, um die Kardinalität von Spalten präzise zu schätzen, was eine effiziente, datenunabhängige Abfrageoptimierung ermöglicht.