Adaptive Factorization Using Linear-Chained Hash Tables

Zusammenfassung

Wir führen faktorisierte Aggregationen und worst-case-optimale Joins in DuckDB ein – mit einem adaptiven Mechanismus, der sie nur dann einsetzt, wenn sie die Anfrageleistung verbessern. Grundlage ist die Einführung eines neuen Hash-Table-Designs („Linear-Chained“) für Equi-Joins. Unsere erste Erkenntnis: Die kollisionsfreien Ketten dieses Designs ermöglichen effiziente faktorisierte und worst-case-optimale Verarbeitung. Die Entscheidung für Faktorisierung und worst-case-optimale Joins verschieben wir zudem von der Optimierung in die Laufzeit. Unsere zweite Erkenntnis: Auch wenn den Join-Eingaben Statistiken fehlen (etwa weil es sich um Unterabfragen oder Parquet-Dateien handelt), lassen sich genaue Statistiken gewinnen, indem wir Laufzeit-Heuristiken nutzen und während des Hash-Join-Builds effiziente On-the-fly-Sketches erzeugen. Schließlich zeigen wir, dass Machine-Learning-Modelle mit diesen Metriken bei hoher Genauigkeit eine nahezu optimale Leistung erreichen. Außerdem schlagen wir heuristikbasierte Ansätze vor, die eine vergleichbare Leistung bieten, dabei aber auf günstiger zu erhebende Laufzeitstatistiken setzen und besser erklärbar sind.