Debunking the Myth of Join Ordering: Toward Robust SQL Analytics
Top Cited Papers
Open Access
- 17 June 2025
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (3) , 1-28
Abstract
Join order optimization is critical in achieving good query performance. Despite decades of research and practice, modern query optimizers could still generate inferior join plans that are orders of magnitude slower than optimal. Existing research on robust query processing often lacks theoretical guarantees on join-order robustness while sacrificing query performance. In this paper, we rediscover the recent Predicate Transfer technique from a robustness point of view. We introduce two new algorithms, LargestRoot and SafeSubjoin, and then propose Robust Predicate Transfer (RPT) that is provably robust against arbitrary join orders of an acyclic query. We integrated Robust Predicate Transfer with DuckDB, a state-of-the-art analytical database, and evaluated against all the queries in TPC-H, JOB, TPC-DS, and DSB benchmarks. Our experimental results show that RPT improves join-order robustness by orders of magnitude compared to the baseline. With RPT, the largest ratio between the maximum and minimum execution time out of random join orders for a single acyclic query is only 1.6x (the ratio is close to 1 for most evaluated queries). Meanwhile, applying RPT also improves the end-to-end query performance by ≈1.5x (per-query geometric mean). We hope that this work sheds light on solving the practical join ordering problem.Keywords
All Related Versions
This publication has 55 references indexed in Scilit:
- A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan EnumerationData Science and Engineering, 2021
- An Approach Based on Bayesian Networks for Query Selectivity Estimation2019
- How I Learned to Stop Worrying and Love Re-optimization2019
- Robust Query Processing: Mission Possible2019
- LevelHeaded: A Unified Engine for Business Intelligence and Linear Algebra Querying2018
- Evaluating multi-way joins over discounted hitting time2014
- Size Bounds and Query Plans for Relational JoinsSIAM Journal on Computing, 2013
- Cache-, Hash- and Space-Efficient Bloom Filters2007
- Hybrid Simultaneous Scheduling and Mapping in SQL Multi-query Parallelization1999
- Graph minors. II. Algorithmic aspects of tree-widthJournal of Algorithms, 1986