Data Chunk Compaction in Vectorized Execution

Zusammenfassung

Moderne analytische Datenbanksysteme setzen oft auf vektorisierte Anfrage-Engines, die spaltenorientierte Daten in Batches (also Data Chunks) verarbeiten, um den Interpretationsaufwand zu senken und den CPU-Parallelismus zu verbessern. Bestimmte Operatoren, insbesondere Hash-Joins, können die Zahl gültiger Einträge in einem Data Chunk jedoch drastisch reduzieren, sodass in einer Ausführungspipeline viele kleine Chunks entstehen. Diese kleinen Chunks können die Vorteile vektorisierter Anfrageverarbeitung nicht voll nutzen und verursachen deutliche Leistungseinbußen. Die zentrale Forschungsfrage lautet, wann und wie diese kleinen Data Chunks während der Anfrageausführung verdichtet werden sollten. In diesem Beitrag modellieren wir zunächst das Chunk-Compaction-Problem und analysieren die Abwägungen zwischen verschiedenen Verdichtungsstrategien. Anschließend schlagen wir einen lernbasierten Algorithmus vor, der die Verdichtungsschwelle zur Laufzeit dynamisch anpassen kann. Zur Frage des „Wie“ schlagen wir für den Hash-Join-Operator eine Methode vor, die wir logische Verdichtung nennen und die Datenbewegungen beim Verdichten von Data Chunks minimiert. Wir haben die vorgeschlagenen Techniken in DuckDB umgesetzt und im Join Order Benchmark, TPC-H und TPC-DS Beschleunigungen von bis zu 63 % beobachtet.