Debunking the Myth of Join Ordering: Toward Robust SQL Analytics

|—––|—––| | Paper | Debunking the Myth of Join Ordering: Toward Robust SQL Analytics (PDF) | | Konferenz | SIGMOD 2025 |

Zusammenfassung

Die Optimierung der Join-Reihenfolge ist entscheidend für gute Anfrageleistung. Trotz jahrzehntelanger Forschung und Praxis erzeugen moderne Query-Optimierer noch immer minderwertige Join-Pläne, die um Größenordnungen langsamer sind als optimal. Bestehende Arbeiten zu robuster Anfrageverarbeitung bieten oft keine theoretischen Garantien zur Robustheit der Join-Reihenfolge und opfern dabei Anfrageleistung. In diesem Beitrag betrachten wir die jüngere Technik Predicate Transfer unter dem Blickwinkel der Robustheit neu. Wir führen zwei neue Algorithmen ein, LargestRoot und SafeSubjoin, und schlagen anschließend Robust Predicate Transfer (RPT) vor, das gegen beliebige Join-Reihenfolgen einer azyklischen Anfrage beweisbar robust ist. Wir haben Robust Predicate Transfer in DuckDB integriert, einer modernen analytischen Datenbank, und gegen alle Anfragen der Benchmarks TPC-H, JOB, TPC-DS und DSB ausgewertet. Unsere Experimente zeigen, dass RPT die Robustheit der Join-Reihenfolge gegenüber der Baseline um Größenordnungen verbessert. Mit RPT beträgt das größte Verhältnis zwischen maximaler und minimaler Ausführungszeit zufälliger Join-Reihenfolgen für eine einzelne azyklische Anfrage nur 1,6× (bei den meisten ausgewerteten Anfragen liegt das Verhältnis nahe 1). Zugleich verbessert RPT die End-to-End-Anfrageleistung um ≈1,5× (geometrisches Mittel pro Anfrage). Wir hoffen, dass diese Arbeit den praktischen Join-Ordering-Problemen neue Wege aufzeigt.