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 50 of 302 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,300	TATA: An Efficient Framework for Task Transfer in Query Plan Representation	2026	VLDB	5.1725167e-05
10,384	Data Chunk Compaction in Vectorized Execution	2025	SIGMOD	5.1725167e-05
10,445	Demo of LearnedWMP: Workload Memory Prediction Using Deep Query Template Representations	2025	SIGMOD	5.1725167e-05
10,455	LpBound in Action: Cardinality Estimation with One-Sided Guarantees	2025	SIGMOD	5.1725167e-05
10,469	UDFBench: A Tool for Benchmarking UDF Queries on SQL Engines	2025	SIGMOD	5.1725167e-05
10,471	Virtualizing Cloud Data Infrastructures with BRAD	2025	SIGMOD	5.1725167e-05
10,478	AJOSC: Adaptive Join Order Selection for Continuous Queries	2025	SIGMOD	5.1725167e-05
10,537	Two Birds with One Stone: Efficient Deep Learning over Mislabeled Data through Subset Selection	2025	SIGMOD	5.1725167e-05
10,560	Avoiding Materialisation for Guarded Aggregate Queries	2025	VLDB	5.1725167e-05
10,574	Holistic query Approximation via RL Modeling	2025	VLDB	5.1725167e-05
10,577	QOVIS: Understanding and Diagnosing Query Optimizer via a Visualization-assisted Approach	2025	VLDB	5.1725167e-05
10,598	ACE: A Cardinality Estimator for Set-Valued Queries	2025	VLDB	5.1725167e-05
10,599	Accio: Bolt-on Query Federation	2025	VLDB	5.1725167e-05
10,624	Unraveling the Impact of Window Semantics: Optimizing Join Order for Efficient Stream Processing	2025	VLDB	5.1725167e-05
10,627	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB	5.1725167e-05
10,635	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	5.1725167e-05
10,638	Conformal Prediction for Verifiable Learned Query Optimization	2025	VLDB	5.1725167e-05
10,641	AQETuner: Reliable Query-level Configuration Tuning for Analytical Query Engines	2025	VLDB	5.1725167e-05
10,643	Saving Private Hash Join	2025	VLDB	5.1725167e-05
10,707	The Accuracy of Cardinality Estimators: Unraveling the Evaluation Result Conundrum	2025	VLDB	5.1725167e-05
10,731	Privacy-Enhanced Database Synthesis for Benchmark Publishing	2025	VLDB	5.1725167e-05
10,733	Improving DBMS Scheduling Decisions with Accurate Performance Prediction on Concurrent Queries	2025	VLDB	5.1725167e-05
10,757	PAR2QO: Parametric Penalty-Aware Robust Query Optimization	2025	VLDB	5.1725167e-05
10,762	Selective Late Materialization in Modern Analytical Databases	2025	VLDB	5.1725167e-05
10,780	Automatic Indexing in Oracle	2025	VLDB	5.1725167e-05
10,796	SQL:Trek Automated Index Design at Airbnb	2025	VLDB	5.1725167e-05
10,813	Hint-QPT: Hints for Robust Query Performance Tuning	2025	VLDB	5.1725167e-05
10,836	A Demonstration of Q2O: Quantum-augmented Query Optimizer	2025	VLDB	5.1725167e-05
10,837	Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects	2025	VLDB	5.1725167e-05
10,844	Learned Cost Models for Query Optimization: From Batch to Streaming Systems	2025	VLDB	5.1725167e-05
10,845	Filtered Vector Search: State-of-the-art and Research Opportunities	2025	VLDB	5.1725167e-05
10,856	CloudGlide: Deconstructing the Landscape of Cloud-Based Analytics	2025	VLDB	5.1725167e-05
10,863	Graph Transformers for Query Plan Representation: Potentials and Challenges	2025	VLDB	5.1725167e-05
10,864	Exploring Exploratory Querying	2025	VLDB	5.1725167e-05
10,872	LEAP: A Low-cost Spark SQL Query Optimizer using Pairwise Comparison	2025	VLDB	5.1725167e-05
10,876	LASER: Buffer-Aware Learned Query Scheduling in Master-Standby Databases	2025	VLDB	5.1725167e-05
10,884	RankPQO: Learning-to-Rank for Parametric Query Optimization	2025	VLDB	5.1725167e-05
10,945	Sub-optimal Join Order Identification with L1-error	2024	SIGMOD	5.1725167e-05
10,986	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	5.1725167e-05
10,990	DPconv: Super-Polynomially Faster Join Ordering	2024	SIGMOD	5.1725167e-05
10,992	High-Performance Query Processing with NVMe Arrays: Spilling without Killing Performance	2024	SIGMOD	5.1725167e-05
10,996	SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs	2024	SIGMOD	5.1725167e-05
10,997	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	5.1725167e-05
11,087	Presto’s History-based Query Optimizer	2024	VLDB	5.1725167e-05
11,192	Efficient and Effective Cardinality Estimation for Skyline Family	2023	SIGMOD	5.1725167e-05
11,214	SH2O: Efficient Data Access for Work-Sharing Databases	2023	SIGMOD	5.1725167e-05
11,256	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB	5.1725167e-05
11,352	DeepO: A Learned Query Optimizer	2022	SIGMOD	5.1725167e-05
11,401	AutoDI: Towards an Automatic Plan Regression Analysis	2022	VLDB	5.1725167e-05
11,535	Fangorn: Adaptive Execution Framework for Heterogeneous Workloads on Shared Clusters	2021	VLDB	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