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.00061463175
Overall Rank
15 | 99.91%
DOI
10.14778/2850583.2850594
PDF
Download (CC BY-NC-ND 4.0)

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 333 citing papers.

Rank Citing Paper Year Venue Pagerank
84 Learned Cardinalities: Estimating Correlated Joins with Deep Learning 2019 CIDR 0.00035920657
142 Neo: A Learned Query Optimizer 2019 VLDB 0.00029114937
320 DeepDB: Learn from Data, not from Queries! 2020 VLDB 0.00021128745
355 Bao: Making Learned Query Optimization Practical 2021 SIGMOD 0.00020146245
375 Umbra: A Disk-Based System with In-Memory Performance 2020 CIDR 0.00019660459
405 Deep Unsupervised Cardinality Estimation 2020 VLDB 0.00019020138
453 An End-to-End Learning-based Cost Estimator 2020 VLDB 0.0001801482
508 NeuroCard: One Cardinality Estimator for All Tables 2021 VLDB 0.00017108973
689 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00014725904
706 Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins 2019 VLDB 0.00014622696
770 VerdictDB: Universalizing Approximate Query Processing 2018 SIGMOD 0.00014086699
983 Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022 VLDB 0.00012677179
1,064 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00012181459
1,175 Balsa: Learning a Query Optimizer Without Expert Demonstrations 2022 SIGMOD 0.00011630532
1,185 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD 0.00011586181
1,282 AI Meets AI: Leveraging Query Executions to Improve Index Recommendations 2019 SIGMOD 0.00011197535
1,400 Magic mirror in my hand, which is the best in the land? An Experimental Evaluation of Index Selection Algorithms 2020 VLDB 0.00010759064
1,436 Towards a Learning Optimizer for Shared Clouds 2019 VLDB 0.00010658836
1,444 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 0.00010616242
1,490 Efficient Discovery of Approximate Dependencies 2018 VLDB 0.0001047928
1,513 DSB: A Decision Support Benchmark for Workload-Driven and Traditional Database Systems 2021 VLDB 0.00010394557
1,517 Automatically Indexing Millions of Databases in Microsoft Azure SQL Database 2019 SIGMOD 0.00010385462
1,541 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 0.00010288394
1,583 Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries 2020 SIGMOD 0.00010148362
1,603 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 0.00010090639
1,609 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2019 SIGMOD 0.0001007196
1,740 Flow-Loss: Learning Cardinality Estimates That Matter 2021 VLDB 9.7289523e-05
1,771 Diagnosing Root Causes of Intermittent Slow Queries in Cloud Databases 2020 VLDB 9.6775181e-05
1,800 Procedural Extensions of SQL: Understanding their usage in the wild 2021 VLDB 9.5999908e-05
1,803 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2018 VLDB 9.5987229e-05
1,931 CodexDB: Synthesizing Code for Query Processing from Natural Language Instructions using GPT-3 Codex 2022 VLDB 9.3449634e-05
1,956 LLM-R^2: A Large Language Model Enhanced Rule-based Rewrite System for Boosting Query Efficiency 2025 VLDB 9.2927535e-05
1,958 Quantifying TPC-H Choke Points and Their Optimizations 2020 VLDB 9.2894133e-05
2,009 FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation 2021 VLDB 9.1813272e-05
2,169 QueryFormer: A Tree Transformer Model for Query Plan Representation 2022 VLDB 8.9151935e-05
2,190 Lero: A Learning-to-Rank Query Optimizer 2023 VLDB 8.8848923e-05
2,228 Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models 2017 VLDB 8.7912743e-05
2,234 Computing the Shapley Value of Facts in Query Answering 2022 SIGMOD 8.7839031e-05
2,239 BtrBlocks: Efficient Columnar Compression for Data Lakes 2023 SIGMOD 8.7753778e-05
2,348 Learned Cardinality Estimation: An In-depth Study 2022 SIGMOD 8.5910072e-05
2,389 A Learned Query Rewrite System using Monte Carlo Tree Search 2022 VLDB 8.5228689e-05
2,481 Learning a Partitioning Advisor for Cloud Databases 2020 SIGMOD 8.3862675e-05
2,523 Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation 2022 VLDB 8.3316032e-05
2,584 Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation 2021 VLDB 8.2435322e-05
2,635 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 8.1795762e-05
2,696 Cost-based or Learning-based? A Hybrid Query Optimizer for Query Plan Selection 2022 VLDB 8.1068354e-05
2,768 Query Performance Prediction for Concurrent Queries using Graph Embedding 2020 VLDB 8.0199086e-05
2,779 Facilitating Database Tuning with Hyper-Parameter Optimization: A Comprehensive Experimental Evaluation 2022 VLDB 8.0085666e-05
2,827 To Partition, or Not to Partition, That is the Join Question in a Real System 2021 SIGMOD 7.9486247e-05
2,828 Cost Models for Big Data Query Processing: Learning, Retrofitting, and Our Findings 2020 SIGMOD 7.9476509e-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.0023948467
91 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00034691614
98 LEO - DB2's LEarning Optimizer 2001 VLDB 0.00034050614
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033847446
160 CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies 2004 SIGMOD 0.00027775994
254 The History of Histograms (abridged) 2003 VLDB 0.00022999992
381 Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors 2009 VLDB 0.00019497061
396 R* Optimizer Validation and Performance Evaluation for Local Queries 1986 SIGMOD 0.00019119719
568 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD 0.00016221103
881 Dynamic Programming Strikes Back 2008 SIGMOD 0.0001324243
1,061 Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions 2011 VLDB 0.00012207625
1,604 The Picasso Database Query Optimizer Visualizer 2010 VLDB 0.00010086711
1,896 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.4010932e-05
1,935 Consistently Estimating the Selectivity of Conjuncts of Predicates 2005 VLDB 9.3407959e-05
1,987 Plan Bouquets: Query Processing without Selectivity Estimation 2014 SIGMOD 9.2323722e-05
2,248 Cache-Efficient Aggregation: Hashing Is Sorting 2015 SIGMOD 8.7484225e-05
2,261 Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs 2013 VLDB 8.7351549e-05
2,527 Adaptive and Big Data Scale Parallel Execution in Oracle 2013 VLDB 8.3243069e-05
2,888 Query Optimizers: Time to Rethink the Contract? 2009 SIGMOD 7.8895201e-05
3,361 Exact Cardinality Query Optimization for Optimizer Testing 2009 VLDB 7.3621595e-05
3,807 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD 6.9902343e-05
4,048 Of Snowstorms and Bushy Trees 2014 VLDB 6.817438e-05
6,816 ROX: Run-time Optimization of XQueries 2009 SIGMOD 5.6593309e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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