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.00061067652
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 330 citing papers.

Rank Citing Paper Year Venue Pagerank
85 Learned Cardinalities: Estimating Correlated Joins with Deep Learning 2019 CIDR 0.00035876108
144 Neo: A Learned Query Optimizer 2019 VLDB 0.00029090793
318 DeepDB: Learn from Data, not from Queries! 2020 VLDB 0.00021166957
361 Bao: Making Learned Query Optimization Practical 2021 SIGMOD 0.00020000855
373 Umbra: A Disk-Based System with In-Memory Performance 2020 CIDR 0.00019705706
406 Deep Unsupervised Cardinality Estimation 2020 VLDB 0.00019050182
462 An End-to-End Learning-based Cost Estimator 2020 VLDB 0.00017836105
510 NeuroCard: One Cardinality Estimator for All Tables 2021 VLDB 0.00017059914
688 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00014749318
713 Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins 2019 VLDB 0.00014571507
772 VerdictDB: Universalizing Approximate Query Processing 2018 SIGMOD 0.0001409096
981 Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022 VLDB 0.00012713454
1,065 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00012202293
1,185 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD 0.00011607329
1,195 Balsa: Learning a Query Optimizer Without Expert Demonstrations 2022 SIGMOD 0.00011574218
1,280 AI Meets AI: Leveraging Query Executions to Improve Index Recommendations 2019 SIGMOD 0.00011224914
1,396 Magic mirror in my hand, which is the best in the land? An Experimental Evaluation of Index Selection Algorithms 2020 VLDB 0.00010788714
1,432 Towards a Learning Optimizer for Shared Clouds 2019 VLDB 0.00010676754
1,465 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 0.00010572023
1,488 Efficient Discovery of Approximate Dependencies 2018 VLDB 0.00010513265
1,515 DSB: A Decision Support Benchmark for Workload-Driven and Traditional Database Systems 2021 VLDB 0.00010418766
1,516 Automatically Indexing Millions of Databases in Microsoft Azure SQL Database 2019 SIGMOD 0.00010398346
1,543 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 0.00010305662
1,580 Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries 2020 SIGMOD 0.00010177136
1,596 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 0.00010122962
1,605 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2019 SIGMOD 0.00010095581
1,735 Flow-Loss: Learning Cardinality Estimates That Matter 2021 VLDB 9.7566604e-05
1,786 Procedural Extensions of SQL: Understanding their usage in the wild 2021 VLDB 9.6281276e-05
1,800 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2018 VLDB 9.6082185e-05
1,849 Diagnosing Root Causes of Intermittent Slow Queries in Cloud Databases 2020 VLDB 9.5032324e-05
1,949 Quantifying TPC-H Choke Points and Their Optimizations 2020 VLDB 9.3172855e-05
1,975 CodexDB: Synthesizing Code for Query Processing from Natural Language Instructions using GPT-3 Codex 2022 VLDB 9.2801545e-05
2,002 FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation 2021 VLDB 9.2076835e-05
2,037 LLM-R^2: A Large Language Model Enhanced Rule-based Rewrite System for Boosting Query Efficiency 2025 VLDB 9.1494269e-05
2,209 Lero: A Learning-to-Rank Query Optimizer 2023 VLDB 8.8360101e-05
2,217 Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models 2017 VLDB 8.8151982e-05
2,218 Computing the Shapley Value of Facts in Query Answering 2022 SIGMOD 8.8130445e-05
2,248 QueryFormer: A Tree Transformer Model for Query Plan Representation 2022 VLDB 8.7567205e-05
2,317 BtrBlocks: Efficient Columnar Compression for Data Lakes 2023 SIGMOD 8.6492924e-05
2,342 Learned Cardinality Estimation: An In-depth Study 2022 SIGMOD 8.6074783e-05
2,393 A Learned Query Rewrite System using Monte Carlo Tree Search 2022 VLDB 8.5298464e-05
2,476 Learning a Partitioning Advisor for Cloud Databases 2020 SIGMOD 8.407183e-05
2,518 Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation 2022 VLDB 8.3532841e-05
2,583 Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation 2021 VLDB 8.2589842e-05
2,635 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 8.1954989e-05
2,686 Cost-based or Learning-based? A Hybrid Query Optimizer for Query Plan Selection 2022 VLDB 8.1300913e-05
2,770 Facilitating Database Tuning with Hyper-Parameter Optimization: A Comprehensive Experimental Evaluation 2022 VLDB 8.0343719e-05
2,818 To Partition, or Not to Partition, That is the Join Question in a Real System 2021 SIGMOD 7.9703078e-05
2,824 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 7.9662478e-05
2,833 Cost Models for Big Data Query Processing: Learning, Retrofitting, and Our Findings 2020 SIGMOD 7.9539771e-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.0023943337
91 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00034748721
98 LEO - DB2's LEarning Optimizer 2001 VLDB 0.00034099838
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033884854
160 CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies 2004 SIGMOD 0.00027827605
255 The History of Histograms (abridged) 2003 VLDB 0.00022974524
386 Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors 2009 VLDB 0.00019446558
397 R* Optimizer Validation and Performance Evaluation for Local Queries 1986 SIGMOD 0.00019151375
569 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD 0.00016244162
883 Dynamic Programming Strikes Back 2008 SIGMOD 0.00013263866
1,058 Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions 2011 VLDB 0.00012224038
1,607 The Picasso Database Query Optimizer Visualizer 2010 VLDB 0.00010085995
1,892 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.4150583e-05
1,931 Consistently Estimating the Selectivity of Conjuncts of Predicates 2005 VLDB 9.3511556e-05
1,989 Plan Bouquets: Query Processing without Selectivity Estimation 2014 SIGMOD 9.2469024e-05
2,245 Cache-Efficient Aggregation: Hashing Is Sorting 2015 SIGMOD 8.7615858e-05
2,252 Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs 2013 VLDB 8.7480805e-05
2,529 Adaptive and Big Data Scale Parallel Execution in Oracle 2013 VLDB 8.3361013e-05
2,890 Query Optimizers: Time to Rethink the Contract? 2009 SIGMOD 7.9010819e-05
3,362 Exact Cardinality Query Optimization for Optimizer Testing 2009 VLDB 7.3719912e-05
3,800 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD 7.0130412e-05
4,052 Of Snowstorms and Bushy Trees 2014 VLDB 6.8257821e-05
6,802 ROX: Run-time Optimization of XQueries 2009 SIGMOD 5.6773357e-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,800 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,185 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD
6 5,200 Exact Cardinality Query Optimization with Bounded Execution Cost 2019 SIGMOD
7 7,603 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,107 Still Asking: How Good Are Query Optimizers, Really? 2025 VLDB
10 4,417 Estimating Compilation Time of a Query Optimizer 2003 SIGMOD