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
9,630	PBench: Workload Synthesizer with Real Statistics for Cloud Analytics Benchmarking	2025	VLDB	5.3018378e-05
9,649	Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes	2023	SIGMOD	5.3001368e-05
9,652	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD	5.2993023e-05
9,693	Cardinality Estimation of LIKE Predicate Queries using Deep Learning	2025	SIGMOD	5.2901428e-05
9,715	SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning	2025	SIGMOD	5.2849709e-05
9,730	Databases in the Era of Memory-Centric Computing	2025	CIDR	5.2802856e-05
9,734	Still Asking: How Good Are Query Optimizers, Really?	2025	VLDB	5.2802856e-05
9,756	The UDFBench Benchmark for General-purpose UDF Queries	2025	VLDB	5.2759752e-05
9,808	A Practical Theory of Generalization in Selectivity Learning	2025	VLDB	5.2683122e-05
9,819	Athena: An Effective Learning-based Framework for Query Optimizer Performance Improvement	2025	SIGMOD	5.2648912e-05
9,841	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS	5.2617062e-05
9,843	Path-centric Cardinality Estimation for Subgraph Matching	2025	VLDB	5.2617062e-05
9,846	Saving Money for Analytical Workloads in the Cloud	2024	VLDB	5.2617062e-05
9,862	Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections	2022	VLDB	5.256625e-05
9,872	Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation	2025	VLDB	5.2547389e-05
9,873	PRICE: A Pretrained Model for Cross-Database Cardinality Estimation	2025	VLDB	5.2547389e-05
9,890	DBMS Fitting: Why should we learn what we already know?	2020	CIDR	5.2500123e-05
9,913	Check Out the Big Brain on BRAD: Simplifying Cloud Data Processing with Learned Automated Data Meshes	2023	VLDB	5.2443653e-05
9,931	Wii: Dynamic Budget Reallocation In Index Tuning	2024	SIGMOD	5.2386374e-05
9,947	SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index	2026	SIGMOD	5.2299972e-05
9,956	How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches	2025	VLDB	5.2232357e-05
9,959	An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL	2025	SIGMOD	5.2142386e-05
9,987	I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server	2026	CIDR	5.1725247e-05
9,992	Leveraging Query Optimizers to Verify the Soundness of LLM-based Query Rewrites for Real-World Workloads, and More!	2026	CIDR	5.1725247e-05
10,018	GenJoin: Conditional Generative Plan-to-Plan Query Optimizer that Learns from Subplan Hints	2026	SIGMOD	5.1725247e-05
10,032	Rainbow: Risk-aware Index Benefit Estimation Facing Out Of Distribution Workloads	2026	SIGMOD	5.1725247e-05
10,034	SieveSketch: A Fine-grained and Adaptive Sketch Framework for Accurate Frequency Estimation	2026	SIGMOD	5.1725247e-05
10,047	AgentTune: An Agent-Based Large Language Model Framework for Database Knob Tuning	2026	SIGMOD	5.1725247e-05
10,049	Approximate Query Processing under Updates	2026	SIGMOD	5.1725247e-05
10,050	APQO: An Adaptive Framework for Parametric Query Optimization	2026	SIGMOD	5.1725247e-05
10,093	MCTuner: Spatial Decomposition-Enhanced Database Tuning via LLM-Guided Exploration	2026	SIGMOD	5.1725247e-05
10,096	NeuSO: Neural Optimizer for Subgraph Queries	2026	SIGMOD	5.1725247e-05
10,104	Query Optimization for Database-Returning Queries	2026	SIGMOD	5.1725247e-05
10,112	SEFRQO: A Self-Evolving Fine-Tuned RAG-Based Query Optimizer	2026	SIGMOD	5.1725247e-05
10,125	Understanding and Detecting Query Performance Regression in Practical Index Tuning: [Experiments & Analysis]	2026	SIGMOD	5.1725247e-05
10,156	Divo: Learning a Stable and Effective Query Optimizer with a Diverse Workload	2026	SIGMOD	5.1725247e-05
10,177	InferF: Declarative Factorization of AI/ML Inferences over Joins	2026	SIGMOD	5.1725247e-05
10,203	Reqo: A Comprehensive Learning-Based Cost Model for Robust and Explainable Query Optimization	2026	SIGMOD	5.1725247e-05
10,212	SQLBarber: A System Leveraging Large Language Models to Generate Customized and Realistic SQL Workloads	2026	SIGMOD	5.1725247e-05
10,217	This is Going to Sound Crazy, But What If We Used Large Language Models to Boost Automatic Database Tuning Algorithms By Leveraging Prior History? We Will Find Better Configurations More Quickly Than Retraining From Scratch!	2026	SIGMOD	5.1725247e-05
10,219	Practical Parameterized Query Optimization via Efficient Plan Reuse and List-wise Ranking	2026	SIGMOD	5.1725247e-05
10,225	LIO: A lightweight and interpretable query optimizer based on an evolutionary forest	2026	VLDB	5.1725247e-05
10,227	Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries	2026	VLDB	5.1725247e-05
10,241	Robust Predicate Transfer with Dynamic Execution	2026	VLDB	5.1725247e-05
10,271	OBELISK: Efficient Offline Query Planning with Bayesian Optimization-Informed Language Model Reasoning	2026	VLDB	5.1725247e-05
10,277	SemBench: A Benchmark for Semantic Query Processing Engines	2026	VLDB	5.1725247e-05
10,278	LakeHelm: Zero-Shot Lakehouse Advisor for Joint Engine-Format Selection and Configuration	2026	VLDB	5.1725247e-05
10,282	Toward Drift-Aware Database Benchmarking	2026	VLDB	5.1725247e-05
10,295	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB	5.1725247e-05
10,296	FlowLog: Efficient and Extensible Datalog via Incrementality	2026	VLDB	5.1725247e-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