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
11501
Venue
VLDB
Year
2016
Pagerank
0.00059284255
Overall Rank
18 | 99.88%
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 313 citing papers.

Rank Citing Paper Year Venue Pagerank
84 Learned Cardinalities: Estimating Correlated Joins with Deep Learning 2019 CIDR 0.00035838391
154 Neo: A Learned Query Optimizer 2019 VLDB 0.00028726181
323 DeepDB: Learn from Data, not from Queries! 2020 VLDB 0.00021264788
378 Bao: Making Learned Query Optimization Practical 2021 SIGMOD 0.00019638121
401 Deep Unsupervised Cardinality Estimation 2020 VLDB 0.00019092557
422 Umbra: A Disk-Based System with In-Memory Performance 2020 CIDR 0.00018732744
465 An End-to-End Learning-based Cost Estimator 2020 VLDB 0.0001803934
513 NeuroCard: One Cardinality Estimator for All Tables 2021 VLDB 0.00017190574
694 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00014911698
772 VerdictDB: Universalizing Approximate Query Processing 2018 SIGMOD 0.00014147905
809 Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins 2019 VLDB 0.00013874588
1,061 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00012369764
1,122 Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022 VLDB 0.0001209124
1,241 Balsa: Learning a Query Optimizer Without Expert Demonstrations 2022 SIGMOD 0.00011521639
1,279 AI Meets AI: Leveraging Query Executions to Improve Index Recommendations 2019 SIGMOD 0.00011361878
1,286 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD 0.00011320736
1,468 Towards a Learning Optimizer for Shared Clouds 2019 VLDB 0.00010686496
1,481 Magic mirror in my hand, which is the best in the land? An Experimental Evaluation of Index Selection Algorithms 2020 VLDB 0.00010644613
1,499 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 0.00010564536
1,500 Efficient Discovery of Approximate Dependencies 2018 VLDB 0.00010561098
1,536 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 0.00010460864
1,548 Automatically Indexing Millions of Databases in Microsoft Azure SQL Database 2019 SIGMOD 0.00010392475
1,573 Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries 2020 SIGMOD 0.00010328171
1,712 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2019 SIGMOD 9.9492299e-05
1,740 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 9.875587e-05
1,815 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2018 VLDB 9.6894541e-05
1,832 DSB: A Decision Support Benchmark for Workload-Driven and Traditional Database Systems 2021 VLDB 9.6607418e-05
1,876 Flow-Loss: Learning Cardinality Estimates That Matter 2021 VLDB 9.5717543e-05
1,892 Procedural Extensions of SQL: Understanding their usage in the wild 2021 VLDB 9.5277793e-05
1,949 Diagnosing Root Causes of Intermittent Slow Queries in Cloud Databases 2020 VLDB 9.430385e-05
1,988 FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation 2021 VLDB 9.3501502e-05
2,202 Quantifying TPC-H Choke Points and Their Optimizations 2020 VLDB 8.9639459e-05
2,203 Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models 2017 VLDB 8.9610447e-05
2,355 QueryFormer: A Tree Transformer Model for Query Plan Representation 2022 VLDB 8.7022189e-05
2,420 Lero: A Learning-to-Rank Query Optimizer 2023 VLDB 8.605257e-05
2,424 Computing the Shapley Value of Facts in Query Answering 2022 SIGMOD 8.6009068e-05
2,452 A Learned Query Rewrite System using Monte Carlo Tree Search 2022 VLDB 8.5584e-05
2,499 Learning a Partitioning Advisor for Cloud Databases 2020 SIGMOD 8.4993549e-05
2,521 CodexDB: Synthesizing Code for Query Processing from Natural Language Instructions using GPT-3 Codex 2022 VLDB 8.4729505e-05
2,543 Learned Cardinality Estimation: An In-depth Study 2022 SIGMOD 8.4445934e-05
2,553 LLM-R^2: A Large Language Model Enhanced Rule-based Rewrite System for Boosting Query Efficiency 2025 VLDB 8.4283807e-05
2,620 Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation 2021 VLDB 8.3363963e-05
2,723 Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation 2022 VLDB 8.2049453e-05
2,731 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 8.1959181e-05
2,740 Facilitating Database Tuning with Hyper-Parameter Optimization: A Comprehensive Experimental Evaluation 2022 VLDB 8.1855759e-05
2,762 Cost-based or Learning-based? A Hybrid Query Optimizer for Query Plan Selection 2022 VLDB 8.1539867e-05
2,788 BtrBlocks: Efficient Columnar Compression for Data Lakes 2023 SIGMOD 8.1205155e-05
2,812 Query Performance Prediction for Concurrent Queries using Graph Embedding 2020 VLDB 8.0979597e-05
2,822 Cost Models for Big Data Query Processing: Learning, Retrofitting, and Our Findings 2020 SIGMOD 8.0898536e-05
2,940 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 7.9381573e-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.0024089429
89 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00035031529
100 LEO - DB2's LEarning Optimizer 2001 VLDB 0.00034385207
101 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00034376651
159 CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies 2004 SIGMOD 0.00028129426
257 The History of Histograms (abridged) 2003 VLDB 0.00023154793
388 Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors 2009 VLDB 0.00019410042
396 R* Optimizer Validation and Performance Evaluation for Local Queries 1986 SIGMOD 0.00019287574
566 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD 0.00016436005
1,013 Dynamic Programming Strikes Back 2008 SIGMOD 0.00012652549
1,071 Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions 2011 VLDB 0.00012322342
1,604 The Picasso Database Query Optimizer Visualizer 2010 VLDB 0.00010230973
1,893 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.5269935e-05
1,936 Consistently Estimating the Selectivity of Conjuncts of Predicates 2005 VLDB 9.4557372e-05
1,987 Plan Bouquets: Query Processing without Selectivity Estimation 2014 SIGMOD 9.3517129e-05
2,250 Cache-Efficient Aggregation: Hashing Is Sorting 2015 SIGMOD 8.8694486e-05
2,275 Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs 2013 VLDB 8.8196821e-05
2,664 Adaptive and Big Data Scale Parallel Execution in Oracle 2013 VLDB 8.2816537e-05
2,944 Query Optimizers: Time to Rethink the Contract? 2009 SIGMOD 7.9335187e-05
3,426 Exact Cardinality Query Optimization for Optimizer Testing 2009 VLDB 7.4218997e-05
3,813 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD 7.1051056e-05
4,091 Of Snowstorms and Bushy Trees 2014 VLDB 6.9090244e-05
6,688 ROX: Run-time Optimization of XQueries 2009 SIGMOD 5.8015211e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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