POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance

Zusammenfassung

Join-Ordnung und Query-Optimierung sind entscheidend für die Abfrageleistung, bleiben aber schwierig, weil Merkmale von Query-Zwischenständen unbekannt sind oder sich ändern – besonders bei komplexen Abfragen mit vielen Joins. In den vergangenen zwei Jahrzehnten wurde ein Spektrum von Techniken für Adaptive Query Processing (AQP) vorgeschlagen – darunter Inter-/Intra-Operator-Adaptivität und Tuple Routing –, um diese Herausforderungen zu adressieren. Kommerzielle Datenbanksysteme implementieren holistische AQP-Techniken in der Praxis jedoch nicht, weil sie die Systemkomplexität erhöhen (etwa durch verwobene Planung und Ausführung) und so Debugging und Tests erschweren. Zudem können bestehende Ansätze großen Overhead verursachen und zu problematischen Leistungsregressionen führen. In diesem Beitrag stellen wir POLAR vor, eine einfache, aber sehr wirksame Technik zur selbstregulierenden Auswahl alternativer Join-Ordnungen mit begrenztem Overhead. Wir erweitern left-deep Join-Pipelines um alternative Join-Ordnungen, führen regret-bounded Tuple Routing durch, um „plans of least resistance“ zu finden und zu validieren, und verarbeiten dann den Großteil der Tupel-Batches über diese Pläne. Wir untersuchen verschiedene Techniken zur Join-Ordnungsauswahl, unterschiedliche Routing-Strategien und eine Vielzahl von Workload-Merkmalen. Unsere Experimente mit einem POLAR-Prototyp in DuckDB zeigen Laufzeitverbesserungen von bis zu 9× und weniger als 7 % Overhead für alle Benchmark-Abfragen; zugleich übertreffen wir State-of-the-Art-AQP-Systeme um bis zu 15×.