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.00058303435
Overall Rank: 20 | 99.87%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 302 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,657	Recommending Deployment Strategies in Crowdsourcing Platforms	2019	SIGMOD	5.1725167e-05
11,703	Tighter Upper Bounds for Join Cardinality Estimates	2018	SIGMOD	5.1725167e-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.0024181671
98	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00034736109
99	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034661365
100	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00034551408
159	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00028421381
256	The History of Histograms (abridged)	2003	VLDB	0.00023354662
387	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019539027
395	R* Optimizer Validation and Performance Evaluation for Local Queries	1986	SIGMOD	0.00019378058
567	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016487025
1,074	Dynamic Programming Strikes Back	2008	SIGMOD	0.00012417484
1,081	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00012387623
1,646	The Picasso Database Query Optimizer Visualizer	2010	VLDB	0.00010197768
1,909	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.5933803e-05
1,941	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.5213058e-05
2,039	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	9.3442163e-05
2,245	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD	8.9441537e-05
2,298	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.8704273e-05
2,654	Adaptive and Big Data Scale Parallel Execution in Oracle	2013	VLDB	8.3634406e-05
2,936	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD	8.0074627e-05
3,451	Exact Cardinality Query Optimization for Optimizer Testing	2009	VLDB	7.4751678e-05
4,029	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	7.0167208e-05
4,093	Of Snowstorms and Bushy Trees	2014	VLDB	6.9707435e-05
6,615	ROX: Run-time Optimization of XQueries	2009	SIGMOD	5.8812828e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
367	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00020067087
4,029	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	7.0167208e-05
304	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00021975148
772	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014187427
1,333	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011226124
5,083	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	6.4386662e-05
7,872	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	5.5951486e-05
1,542	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	0.00010485222
9,734	Still Asking: How Good Are Query Optimizers, Really?	2025	VLDB	5.2802775e-05
4,324	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD	6.8348069e-05