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: 11501
Venue: VLDB
Year: 2016
Pagerank: 0.00059284255
Overall Rank: 18 | 99.88%
DOI: 10.14778/2850583.2850594

Incoming Non-self Citations Over Time

Authors

1. Viktor Leis (Technical University of Munich)
2. Andrey Gubichev (Technical University of Munich)
3. Atanas Mirchev (Technical University of Munich)
4. Peter Boncz (Centrum Wiskunde & Informatica)
5. Alfons Kemper (Technical University of Munich)
6. Thomas Neumann (Technical University of Munich)

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 13 of 313 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,160	Sub-optimal Join Order Identification with L1-error	2024	SIGMOD	5.093636e-05
11,196	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	5.093636e-05
11,200	High-Performance Query Processing with NVMe Arrays: Spilling without Killing Performance	2024	SIGMOD	5.093636e-05
11,204	SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs	2024	SIGMOD	5.093636e-05
11,205	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	5.093636e-05
11,290	Presto’s History-based Query Optimizer	2024	VLDB	5.093636e-05
11,413	SH2O: Efficient Data Access for Work-Sharing Databases	2023	SIGMOD	5.093636e-05
11,453	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB	5.093636e-05
11,548	DeepO: A Learned Query Optimizer	2022	SIGMOD	5.093636e-05
11,596	AutoDI: Towards an Automatic Plan Regression Analysis	2022	VLDB	5.093636e-05
11,728	Fangorn: Adaptive Execution Framework for Heterogeneous Workloads on Shared Clusters	2021	VLDB	5.093636e-05
11,847	Recommending Deployment Strategies in Crowdsourcing Platforms	2019	SIGMOD	5.093636e-05
11,902	Tighter Upper Bounds for Join Cardinality Estimates	2018	SIGMOD	5.093636e-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.0024089429
89	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00035031529
100	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034385207
101	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00034376651
159	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00028129426
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
388	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019410042
396	R* Optimizer Validation and Performance Evaluation for Local Queries	1986	SIGMOD	0.00019287574
566	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016436005
1,013	Dynamic Programming Strikes Back	2008	SIGMOD	0.00012652549
1,071	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00012322342
1,604	The Picasso Database Query Optimizer Visualizer	2010	VLDB	0.00010230973
1,893	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.5269935e-05
1,936	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.4557372e-05
1,987	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	9.3517129e-05
2,250	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD	8.8694486e-05
2,275	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.8196821e-05
2,664	Adaptive and Big Data Scale Parallel Execution in Oracle	2013	VLDB	8.2816537e-05
2,944	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD	7.9335187e-05
3,426	Exact Cardinality Query Optimization for Optimizer Testing	2009	VLDB	7.4218997e-05
3,813	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	7.1051056e-05
4,091	Of Snowstorms and Bushy Trees	2014	VLDB	6.9090244e-05
6,688	ROX: Run-time Optimization of XQueries	2009	SIGMOD	5.8015211e-05

Semantically Similar Papers

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