Saving Private Hash Join

Zusammenfassung

Moderne analytische Datenbanksysteme bieten hochperformante In-Memory-Joins. Passt die Build-Seite eines Joins jedoch nicht in den RAM, bricht die Leistung scharf ein, weil auf klassische externe Join-Algorithmen wie Sort-Merge umgeschaltet wird. Bei Streaming-Anfrageausführung verschärft sich das Problem, wenn mehrere Joins gleichzeitig ausgewertet werden: Das Datenbanksystem muss entscheiden, wie Speicher auf jeden Join verteilt wird, und das kann die Leistung stark beeinflussen.

Wir betrachten Join-Verarbeitung größer als der Speicher auf moderner Hardware neu und streben robuste Leistung an, die eine „Leistungsklippe“ vermeidet, wenn der Speicher ausgeht – auch in Anfrageplänen mit vielen Joins. Dafür schlagen wir drei Techniken vor. Erstens einen adaptiven, externen Hash-Join-Algorithmus, der temporäre Daten in einem einheitlichen Buffer Pool speichert, der temporäre und persistente Daten überwacht. Zweitens einen Optimierer, der Ausdrücke erzeugt, um Spalten zur Laufzeit zu komprimieren und so die Größe materialisierter temporärer Daten zu senken. Drittens eine Strategie, den Speicher nebenläufiger Operatoren während der Anfrageausführung dynamisch zu verwalten, um Auslagern zu reduzieren.

Wir integrieren diese Techniken in DuckDB und zeigen experimentell, dass unsere Implementierung bei speicherintensiven Join-Anfrageplänen die Leistung elegant abbaut, wenn der Platzbedarf das Speicherlimit überschreitet. Das vergrößert erheblich die Datensätze, die sich auf wirtschaftlicher Hardware verarbeiten lassen.

Implementierung

Die in diesem Beitrag beschriebenen Techniken sind in DuckDB v1.2.0 integriert.