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.00058294381
Overall Rank: 20 | 99.87%
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
7,520	Plan Stitch: Harnessing the Best of Many Plans	2018	VLDB	5.6603314e-05
7,579	SQLStorm: Taking Database Benchmarking into the LLM Era	2025	VLDB	5.6492649e-05
7,632	Blueprinting the Cloud: Unifying and Automatically Optimizing Cloud Data Infrastructures with BRAD	2024	VLDB	5.6369542e-05
7,634	NOCAP: Near-Optimal Correlation-Aware Partitioning Joins	2023	SIGMOD	5.6365306e-05
7,656	Building Advanced SQL Analytics From Low-Level Plan Operators	2021	SIGMOD	5.6306218e-05
7,681	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB	5.6252996e-05
7,698	RCRank: Multimodal Ranking of Root Causes of Slow Queries in Cloud Database Systems	2025	VLDB	5.6225406e-05
7,722	The Holon Approach for Simultaneously Tuning Multiple Components in a Self-Driving Database Management System with Machine Learning via Synthesized Proto-Actions	2024	VLDB	5.6186987e-05
7,736	ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning	2023	VLDB	5.6146208e-05
7,770	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	5.6064744e-05
7,844	Thrifty Query Execution via Incrementability	2020	SIGMOD	5.6022439e-05
7,871	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	5.5951573e-05
7,917	Grep: A Graph Learning Based Database Partitioning System	2023	SIGMOD	5.5867954e-05
7,956	Leveraging Dynamic and Heterogeneous Workload Knowledge to Boost the Performance of Index Advisors	2024	VLDB	5.5736751e-05
8,054	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	5.5562082e-05
8,087	MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates	2020	SIGMOD	5.5486991e-05
8,100	The Case for Learned In-Memory Joins	2023	VLDB	5.5455315e-05
8,182	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	5.5385661e-05
8,245	Excalibur: A Virtual Machine for Adaptive Fine-grained JIT-Compiled Query Execution based on VOILA	2023	VLDB	5.5249762e-05
8,281	Can Large Language Models Be Query Optimizer for Relational Databases?	2026	SIGMOD	5.5167963e-05
8,290	Conditional Cuckoo Filters	2021	SIGMOD	5.514631e-05
8,291	Making RDBMSs Efficient on Graph Workloads Through Predefined Joins	2022	VLDB	5.5145966e-05
8,358	A Concave Path to Low-overhead Robust Query Processing	2018	VLDB	5.5011787e-05
8,451	PostCENN: PostgreSQL with Machine Learning Models for Cardinality Estimation	2021	VLDB	5.4924612e-05
8,463	Learned Offline Query Planning via Bayesian Optimization	2025	SIGMOD	5.4900503e-05
8,490	Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries	2024	SIGMOD	5.4868152e-05
8,521	The Case for NLP-Enhanced Database Tuning: Towards Tuning Tools that "Read the Manual"	2021	VLDB	5.4801129e-05
8,526	A Practical Approach to Groupjoin and Nested Aggregates	2021	VLDB	5.4787362e-05
8,531	Parachute: Single-Pass Bi-Directional Information Passing	2025	VLDB	5.4771584e-05
8,581	Workload-driven, Lazy Discovery of Data Dependencies for Query Optimization	2022	CIDR	5.4683949e-05
8,592	SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms	2023	VLDB	5.4654569e-05
8,698	Resource-Adaptive Query Execution with Paged Memory Management	2025	CIDR	5.4467894e-05
8,723	ByteCard: Enhancing ByteDance’s Data Warehouse with Learned Cardinality Estimation	2024	SIGMOD	5.4407297e-05
8,856	One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting	2024	SIGMOD	5.4214637e-05
8,914	JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation	2023	SIGMOD	5.4089358e-05
8,988	BASE: Bridging the Gap between Cost and Latency for Query Optimization	2023	VLDB	5.4017106e-05
9,048	Extending SQL to Return a Subdatabase	2025	SIGMOD	5.3880466e-05
9,054	TreeSensing: Linearly Compressing Sketches with Flexibility	2023	SIGMOD	5.3880466e-05
9,089	POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance	2024	VLDB	5.3857237e-05
9,113	PACE: Poisoning Attacks on Learned Cardinality Estimation	2024	SIGMOD	5.3795816e-05
9,211	DBG-PT: A Large Language Model Assisted Query Performance Regression Debugger	2024	VLDB	5.3657916e-05
9,254	Optimizing Disjunctive Queries with Tagged Execution	2024	SIGMOD	5.3572577e-05
9,290	LIMAO: A Framework for Lifelong Modular Learned Query Optimization	2025	VLDB	5.3525489e-05
9,297	FEBench: A Benchmark for Real-Time Relational Data Feature Extraction	2023	VLDB	5.3510467e-05
9,306	Db2une: Tuning Under Pressure via Deep Learning	2024	VLDB	5.3494296e-05
9,319	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	5.3468418e-05
9,327	Are Joins over LSM-trees Ready? Take RocksDB as an Example	2025	VLDB	5.3449422e-05
9,353	CEDA: Learned Cardinality Estimation with Domain Adaptation	2023	VLDB	5.344078e-05
9,526	Low Rank Learning for Offline Query Optimization	2025	SIGMOD	5.3206369e-05
9,608	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD	5.3067619e-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.0024179717
98	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00034732081
99	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034651834
100	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00034549997
159	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00028420571
256	The History of Histograms (abridged)	2003	VLDB	0.00023353808
387	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019538003
395	R* Optimizer Validation and Performance Evaluation for Local Queries	1986	SIGMOD	0.00019377004
567	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016486291
1,074	Dynamic Programming Strikes Back	2008	SIGMOD	0.00012416314
1,081	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00012387181
1,646	The Picasso Database Query Optimizer Visualizer	2010	VLDB	0.00010197566
1,909	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.5931227e-05
1,942	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.5209948e-05
2,039	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	9.3438044e-05
2,245	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD	8.9438948e-05
2,298	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.8701679e-05
2,654	Adaptive and Big Data Scale Parallel Execution in Oracle	2013	VLDB	8.3637522e-05
2,937	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD	8.0072565e-05
3,451	Exact Cardinality Query Optimization for Optimizer Testing	2009	VLDB	7.4749615e-05
4,029	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	7.0167316e-05
4,093	Of Snowstorms and Bushy Trees	2014	VLDB	6.9705366e-05
6,616	ROX: Run-time Optimization of XQueries	2009	SIGMOD	5.8812707e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
367	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00020067056
4,029	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	7.0167316e-05
304	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00021980949
772	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014187327
1,333	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011225357
5,082	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	6.4386697e-05
7,871	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	5.5951573e-05
1,542	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	0.00010485163
9,734	Still Asking: How Good Are Query Optimizers, Really?	2025	VLDB	5.2802856e-05
4,324	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD	6.8348121e-05