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: 11314
Venue: VLDB
Year: 2016
Pagerank: 0.00059446482
Overall Rank: 71 | 99.51%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 302 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
203	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00034868567
329	Neo: A Learned Query Optimizer	2019	VLDB	0.00027301488
606	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00019251186
634	Bao: Making Learned Query Optimization Practical	2021	SIGMOD	0.00018844568
729	Umbra: A Disk-Based System with In-Memory Performance	2020	CIDR	0.00017448059
752	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00017138049
804	An End-to-End Learning-based Cost Estimator	2020	VLDB	0.0001643674
905	NeuroCard: One Cardinality Estimator for All Tables	2021	VLDB	0.00015423174
1,104	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.0001398479
1,161	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00013579831
1,334	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00012543633
1,621	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011105663
1,631	CodexDB: Synthesizing Code for Query Processing from Natural Language Instructions using GPT-3 Codex	2022	VLDB	0.00011071662
1,638	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00011050093
1,699	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010848882
1,856	AI Meets AI: Leveraging Query Executions to Improve Index Recommendations	2019	SIGMOD	0.00010319105
1,978	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	9.8764627e-05
2,022	Magic mirror in my hand, which is the best in the land? An Experimental Evaluation of Index Selection Algorithms	2020	VLDB	9.7623022e-05
2,050	Automatically Indexing Millions of Databases in Microsoft Azure SQL Database	2019	SIGMOD	9.6883066e-05
2,080	Towards a Learning Optimizer for Shared Clouds	2019	VLDB	9.5954034e-05
2,082	Efficient Discovery of Approximate Dependencies	2018	VLDB	9.5875364e-05
2,090	Balsa: Learning a Query Optimizer Without Expert Demonstrations	2022	SIGMOD	9.5668285e-05
2,140	Diagnosing Root Causes of Intermittent Slow Queries in Cloud Databases	2020	VLDB	9.4565836e-05
2,143	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	9.4437798e-05
2,154	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2018	VLDB	9.4176683e-05
2,222	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2019	SIGMOD	9.2598438e-05
2,242	Procedural Extensions of SQL: Understanding their usage in the wild	2021	VLDB	9.2124242e-05
2,281	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.122455e-05
2,364	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD	8.955077e-05
2,769	FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation	2021	VLDB	8.1512848e-05
2,781	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	8.1282042e-05
2,876	Computing the Shapley Value of Facts in Query Answering	2022	SIGMOD	7.9739469e-05
2,914	Quantifying TPC-H Choke Points and Their Optimizations	2020	VLDB	7.9197583e-05
2,937	DSB: A Decision Support Benchmark for Workload-Driven and Traditional Database Systems	2021	VLDB	7.8552033e-05
2,971	Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models	2017	VLDB	7.7935535e-05
2,988	Neural Subgraph Counting with Wasserstein Estimator	2022	SIGMOD	7.7752463e-05
3,066	Learning a Partitioning Advisor for Cloud Databases	2020	SIGMOD	7.6255556e-05
3,167	QueryFormer: A Tree Transformer Model for Query Plan Representation	2022	VLDB	7.4561078e-05
3,241	A Learned Query Rewrite System using Monte Carlo Tree Search	2022	VLDB	7.32744e-05
3,269	Learned Cardinality Estimation: An In-depth Study	2022	SIGMOD	7.3026051e-05
3,270	RHEEM: Enabling Cross-Platform Data Processing - May The Big Data Be With You! -	2018	VLDB	7.3013196e-05
3,345	Lero: A Learning-to-Rank Query Optimizer	2023	VLDB	7.1908499e-05
3,455	Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation	2022	VLDB	7.0760196e-05
3,465	LLM-R2: A Large Language Model Enhanced Rule-based Rewrite System for Boosting Query Efficiency	2025	VLDB	7.0668293e-05
3,492	Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation	2021	VLDB	7.0435484e-05
3,516	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.018912e-05
3,580	Query Performance Prediction for Concurrent Queries using Graph Embedding	2020	VLDB	6.9460425e-05
3,623	Cost Models for Big Data Query Processing: Learning, Retrofitting, and Our Findings	2020	SIGMOD	6.9017341e-05
3,642	BtrBlocks: Efficient Columnar Compression for Data Lakes	2023	SIGMOD	6.8876984e-05
3,644	G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching	2020	SIGMOD	6.8842065e-05

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.0040465394
100	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050033475
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041819767
181	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00036970794
224	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00032743209
269	R* Optimizer Validation and Performance Evaluation for Local Queries	1986	SIGMOD	0.00029665158
325	The History of Histograms (abridged)	2003	VLDB	0.00027398081
627	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00018959896
680	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018193263
1,297	The Picasso Database Query Optimizer Visualizer	2010	VLDB	0.00012732768
1,344	Dynamic Programming Strikes Back	2008	SIGMOD	0.00012477274
1,536	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00011458359
2,359	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	8.967267e-05
2,369	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	8.9462051e-05
2,632	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	8.4153283e-05
2,741	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD	8.1977375e-05
2,778	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.1345892e-05
3,016	Adaptive and Big Data Scale Parallel Execution in Oracle	2013	VLDB	7.7060968e-05
3,402	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD	7.134261e-05
3,943	Exact Cardinality Query Optimization for Optimizer Testing	2009	VLDB	6.6067351e-05
4,503	Of Snowstorms and Bushy Trees	2014	VLDB	6.131076e-05
4,734	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9553181e-05
6,879	ROX: Run-time Optimization of XQueries	2009	SIGMOD	4.8934866e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
422	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023654556
4,734	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9553181e-05
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022796106
979	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014871114
1,621	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011105663
5,696	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	5.367449e-05
8,193	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	4.5575291e-05
2,143	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	9.4437798e-05
9,746	Still Asking: How Good Are Query Optimizers, Really?	2025	VLDB	4.2856385e-05
4,390	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD	6.2193128e-05