DBScholar

Back to papers

How Good Are Query Optimizers, Really?

Summary: Introduces the Join Order Benchmark (JOB) to test optimizer components on real-world, multi-join workloads. Cardinality estimators are error-prone; cost models matter less than estimates; exhaustive dynamic programming improves plan quality over heuristics under poor cardinality. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h476371500a44338b
Venue
VLDB
Year
2016
Pagerank
0.00061066921
Overall Rank
15 | 99.91%
DOI
10.14778/2850583.2850594

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{leis_vldb16,
        title = {{How Good Are Query Optimizers, Really?}},
        author = {Leis, Viktor and Gubichev, Andrey and Mirchev, Atanas and Boncz, Peter and Kemper, Alfons and Neumann, Thomas},
        journal = {PVLDB},
        series = {{VLDB} '16},
        volume = {9},
        number = {3},
        pages = {204--215},
        doi = {10.14778/2850583.2850594},
        url = {https://doi.org/10.14778/2850583.2850594},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 330 citing papers.

Rank Citing Paper Year Venue Pagerank
85 Learned Cardinalities: Estimating Correlated Joins with Deep Learning 2019 CIDR 0.00035864347
145 Neo: A Learned Query Optimizer 2019 VLDB 0.0002908188
318 DeepDB: Learn from Data, not from Queries! 2020 VLDB 0.00021167555
362 Bao: Making Learned Query Optimization Practical 2021 SIGMOD 0.00019989474
373 Umbra: A Disk-Based System with In-Memory Performance 2020 CIDR 0.00019711632
406 Deep Unsupervised Cardinality Estimation 2020 VLDB 0.00019045544
461 An End-to-End Learning-based Cost Estimator 2020 VLDB 0.00017829982
512 NeuroCard: One Cardinality Estimator for All Tables 2021 VLDB 0.00017050173
688 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00014753664
712 Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins 2019 VLDB 0.00014578373
784 VerdictDB: Universalizing Approximate Query Processing 2018 SIGMOD 0.00014012614
982 Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022 VLDB 0.00012714044
1,064 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00012202282
1,186 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD 0.0001160797
1,199 Balsa: Learning a Query Optimizer Without Expert Demonstrations 2022 SIGMOD 0.00011563985
1,279 AI Meets AI: Leveraging Query Executions to Improve Index Recommendations 2019 SIGMOD 0.00011226878
1,397 Magic mirror in my hand, which is the best in the land? An Experimental Evaluation of Index Selection Algorithms 2020 VLDB 0.00010789242
1,433 Towards a Learning Optimizer for Shared Clouds 2019 VLDB 0.00010677711
1,465 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 0.00010576304
1,488 Efficient Discovery of Approximate Dependencies 2018 VLDB 0.00010517437
1,515 DSB: A Decision Support Benchmark for Workload-Driven and Traditional Database Systems 2021 VLDB 0.00010417728
1,516 Automatically Indexing Millions of Databases in Microsoft Azure SQL Database 2019 SIGMOD 0.00010402594
1,542 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 0.00010308631
1,580 Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries 2020 SIGMOD 0.00010180835
1,596 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 0.00010127607
1,603 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2019 SIGMOD 0.00010097649
1,734 Flow-Loss: Learning Cardinality Estimates That Matter 2021 VLDB 9.7545773e-05
1,786 Procedural Extensions of SQL: Understanding their usage in the wild 2021 VLDB 9.6326265e-05
1,800 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2018 VLDB 9.6093317e-05
1,857 Diagnosing Root Causes of Intermittent Slow Queries in Cloud Databases 2020 VLDB 9.4929201e-05
1,952 Quantifying TPC-H Choke Points and Their Optimizations 2020 VLDB 9.3189525e-05
1,975 CodexDB: Synthesizing Code for Query Processing from Natural Language Instructions using GPT-3 Codex 2022 VLDB 9.2807031e-05
2,004 FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation 2021 VLDB 9.2065719e-05
2,039 LLM-R^2: A Large Language Model Enhanced Rule-based Rewrite System for Boosting Query Efficiency 2025 VLDB 9.1493268e-05
2,210 Lero: A Learning-to-Rank Query Optimizer 2023 VLDB 8.8257742e-05
2,216 Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models 2017 VLDB 8.8177753e-05
2,217 Computing the Shapley Value of Facts in Query Answering 2022 SIGMOD 8.8172185e-05
2,250 QueryFormer: A Tree Transformer Model for Query Plan Representation 2022 VLDB 8.7533306e-05
2,314 BtrBlocks: Efficient Columnar Compression for Data Lakes 2023 SIGMOD 8.6533171e-05
2,342 Learned Cardinality Estimation: An In-depth Study 2022 SIGMOD 8.6060437e-05
2,395 A Learned Query Rewrite System using Monte Carlo Tree Search 2022 VLDB 8.5281914e-05
2,478 Learning a Partitioning Advisor for Cloud Databases 2020 SIGMOD 8.4079121e-05
2,522 Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation 2022 VLDB 8.3477168e-05
2,583 Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation 2021 VLDB 8.2589758e-05
2,634 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 8.1993804e-05
2,690 Cost-based or Learning-based? A Hybrid Query Optimizer for Query Plan Selection 2022 VLDB 8.1258173e-05
2,772 Facilitating Database Tuning with Hyper-Parameter Optimization: A Comprehensive Experimental Evaluation 2022 VLDB 8.035288e-05
2,818 To Partition, or Not to Partition, That is the Join Question in a Real System 2021 SIGMOD 7.9739791e-05
2,824 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 7.9698957e-05
2,834 Cost Models for Big Data Query Processing: Learning, Retrofitting, and Our Findings 2020 SIGMOD 7.9560627e-05
Previous Page 1 / 7 Next

Outgoing Citations (Sorted by Pagerank)

Showing 23 of 23 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
1 Access Path Selection in a Relational Database Management System 1979 SIGMOD 0.0023947656
91 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.0003475226
98 LEO - DB2's LEarning Optimizer 2001 VLDB 0.00034106982
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033894985
160 CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies 2004 SIGMOD 0.00027837289
255 The History of Histograms (abridged) 2003 VLDB 0.00022981861
386 Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors 2009 VLDB 0.00019444411
397 R* Optimizer Validation and Performance Evaluation for Local Queries 1986 SIGMOD 0.00019157058
569 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD 0.00016245271
884 Dynamic Programming Strikes Back 2008 SIGMOD 0.00013267935
1,060 Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions 2011 VLDB 0.00012224575
1,606 The Picasso Database Query Optimizer Visualizer 2010 VLDB 0.00010089789
1,891 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.4184294e-05
1,929 Consistently Estimating the Selectivity of Conjuncts of Predicates 2005 VLDB 9.3546057e-05
1,987 Plan Bouquets: Query Processing without Selectivity Estimation 2014 SIGMOD 9.250242e-05
2,245 Cache-Efficient Aggregation: Hashing Is Sorting 2015 SIGMOD 8.7649358e-05
2,251 Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs 2013 VLDB 8.7511987e-05
2,530 Adaptive and Big Data Scale Parallel Execution in Oracle 2013 VLDB 8.3391175e-05
2,891 Query Optimizers: Time to Rethink the Contract? 2009 SIGMOD 7.9021718e-05
3,367 Exact Cardinality Query Optimization for Optimizer Testing 2009 VLDB 7.3719456e-05
3,797 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD 7.0163619e-05
4,052 Of Snowstorms and Bushy Trees 2014 VLDB 6.8283077e-05
6,800 ROX: Run-time Optimization of XQueries 2009 SIGMOD 5.6792071e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 321 Measuring the Complexity of Join Enumeration in Query Optimization 1990 VLDB
2 3,797 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD
3 272 An Overview of Query Optimization in Relational Systems 1998 PODS
4 796 Rapid Bushy Join-order Optimization with Cartesian Products 1996 SIGMOD
5 1,186 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD
6 5,199 Exact Cardinality Query Optimization with Bounded Execution Cost 2019 SIGMOD
7 7,597 On the Calculation of Optimality Ranges for Relational Query Execution Plans 2018 SIGMOD
8 1,465 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD
9 10,103 Still Asking: How Good Are Query Optimizers, Really? 2025 VLDB
10 4,415 Estimating Compilation Time of a Query Optimizer 2003 SIGMOD