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

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 299 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
204	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00034784455
333	Neo: A Learned Query Optimizer	2019	VLDB	0.00027206884
608	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00019235898
640	Bao: Making Learned Query Optimization Practical	2021	SIGMOD	0.00018759152
735	Umbra: A Disk-Based System with In-Memory Performance	2020	CIDR	0.00017452467
758	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.0001706608
806	An End-to-End Learning-based Cost Estimator	2020	VLDB	0.00016434274
910	NeuroCard: One Cardinality Estimator for All Tables	2021	VLDB	0.00015423056
1,105	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00013990395
1,204	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00013319541
1,333	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00012523806
1,619	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011111678
1,638	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00011049779
1,643	CodexDB: Synthesizing Code for Query Processing from Natural Language Instructions using GPT-3 Codex	2022	VLDB	0.0001104256
1,703	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010836769
1,855	AI Meets AI: Leveraging Query Executions to Improve Index Recommendations	2019	SIGMOD	0.00010315245
1,981	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	9.8687545e-05
2,020	Magic mirror in my hand, which is the best in the land? An Experimental Evaluation of Index Selection Algorithms	2020	VLDB	9.762624e-05
2,047	Automatically Indexing Millions of Databases in Microsoft Azure SQL Database	2019	SIGMOD	9.6920209e-05
2,077	Efficient Discovery of Approximate Dependencies	2018	VLDB	9.6001836e-05
2,083	Towards a Learning Optimizer for Shared Clouds	2019	VLDB	9.5834572e-05
2,121	Balsa: Learning a Query Optimizer Without Expert Demonstrations	2022	SIGMOD	9.5017232e-05
2,139	Diagnosing Root Causes of Intermittent Slow Queries in Cloud Databases	2020	VLDB	9.4640037e-05
2,142	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	9.4507296e-05
2,156	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2018	VLDB	9.4170209e-05
2,219	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2019	SIGMOD	9.2623533e-05
2,237	Procedural Extensions of SQL: Understanding their usage in the wild	2021	VLDB	9.2212748e-05
2,275	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.1262202e-05
2,364	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD	8.9554751e-05
2,762	FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation	2021	VLDB	8.1585394e-05
2,783	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	8.1293383e-05
2,868	Computing the Shapley Value of Facts in Query Answering	2022	SIGMOD	7.9816425e-05
2,916	Quantifying TPC-H Choke Points and Their Optimizations	2020	VLDB	7.9068048e-05
2,969	Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models	2017	VLDB	7.7974762e-05
2,985	DSB: A Decision Support Benchmark for Workload-Driven and Traditional Database Systems	2021	VLDB	7.7795847e-05
3,001	Neural Subgraph Counting with Wasserstein Estimator	2022	SIGMOD	7.7404487e-05
3,076	Learning a Partitioning Advisor for Cloud Databases	2020	SIGMOD	7.6107677e-05
3,169	QueryFormer: A Tree Transformer Model for Query Plan Representation	2022	VLDB	7.4498425e-05
3,248	A Learned Query Rewrite System using Monte Carlo Tree Search	2022	VLDB	7.3258782e-05
3,265	RHEEM: Enabling Cross-Platform Data Processing - May The Big Data Be With You! -	2018	VLDB	7.3083672e-05
3,266	Learned Cardinality Estimation: An In-depth Study	2022	SIGMOD	7.3074684e-05
3,348	Lero: A Learning-to-Rank Query Optimizer	2023	VLDB	7.1904529e-05
3,449	Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation	2022	VLDB	7.0824319e-05
3,472	LLM-R2: A Large Language Model Enhanced Rule-based Rewrite System for Boosting Query Efficiency	2025	VLDB	7.0639229e-05
3,499	Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation	2021	VLDB	7.0376445e-05
3,511	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.0254052e-05
3,580	Query Performance Prediction for Concurrent Queries using Graph Embedding	2020	VLDB	6.9500996e-05
3,625	Cost Models for Big Data Query Processing: Learning, Retrofitting, and Our Findings	2020	SIGMOD	6.9055212e-05
3,644	BtrBlocks: Efficient Columnar Compression for Data Lakes	2023	SIGMOD	6.8854928e-05
3,646	G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching	2020	SIGMOD	6.8853079e-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.0040449103
99	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050022914
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041786333
182	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00036962631
224	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00032746205
268	R* Optimizer Validation and Performance Evaluation for Local Queries	1986	SIGMOD	0.00029662304
325	The History of Histograms (abridged)	2003	VLDB	0.00027378328
629	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00018942366
684	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018179769
1,300	The Picasso Database Query Optimizer Visualizer	2010	VLDB	0.00012733214
1,341	Dynamic Programming Strikes Back	2008	SIGMOD	0.00012486285
1,547	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00011442359
2,356	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	8.9620762e-05
2,377	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	8.9402115e-05
2,631	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	8.4101843e-05
2,742	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD	8.1906104e-05
2,785	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.1286814e-05
3,021	Adaptive and Big Data Scale Parallel Execution in Oracle	2013	VLDB	7.6991391e-05
3,408	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD	7.1288167e-05
3,952	Exact Cardinality Query Optimization for Optimizer Testing	2009	VLDB	6.5939652e-05
4,511	Of Snowstorms and Bushy Trees	2014	VLDB	6.1247645e-05
4,738	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9600502e-05
6,874	ROX: Run-time Optimization of XQueries	2009	SIGMOD	4.8978984e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
423	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023669348
4,738	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9600502e-05
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022734812
978	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014881073
1,619	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011111678
5,685	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	5.3717535e-05
8,213	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	4.557937e-05
2,142	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	9.4507296e-05
9,747	Still Asking: How Good Are Query Optimizers, Really?	2025	VLDB	4.2897489e-05
4,397	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD	6.2230918e-05