Towards a Robust Query Optimizer: A Principled and Practical Approach

Summary: Proposes robust query optimization by treating cardinality estimation probabilistically rather than exact. A Bayesian, sample-based estimator from precomputed samples captures correlations and enables performance/predictability tradeoffs, integrating with optimizers. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3629
Venue: SIGMOD
Year: 2005
Pagerank: 0.00018179769
Overall Rank: 684 | 95.25%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Brian Babcock
2. Surajit Chaudhuri

Incoming Citations (Sorted by Pagerank)

Showing 44 of 44 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059038975
333	Neo: A Learned Query Optimizer	2019	VLDB	0.00027206884
884	Plan-Structured Deep Neural Network Models for Query Performance Prediction	2019	VLDB	0.00015654004
1,272	Proactive Re-Optimization	2005	SIGMOD	0.00012920076
1,758	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00010655546
2,142	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	9.4507296e-05
2,156	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2018	VLDB	9.4170209e-05
2,219	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2019	SIGMOD	9.2623533e-05
2,631	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	8.4101843e-05
2,659	Multi-Objective Parametric Query Optimization	2015	VLDB	8.3604734e-05
3,408	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD	7.1288167e-05
3,645	Large-Scale Collective Entity Matching	2011	VLDB	6.8853274e-05
3,658	Towards a Hands-Free Query Optimizer through Deep Learning	2019	CIDR	6.8704209e-05
3,727	Cost-based or Learning-based? A Hybrid Query Optimizer for Query Plan Selection	2022	VLDB	6.8141709e-05
4,195	Warding off the Dangers of Data Corruption with Amulet	2011	SIGMOD	6.368976e-05
4,276	Looking Ahead Makes Query Plans Robust: Making the Initial Case with In-Memory Star Schema Data Warehouse Workloads	2017	VLDB	6.2976602e-05
4,348	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB	6.2660237e-05
4,436	Xplus: A SQL-Tuning-Aware Query Optimizer	2010	VLDB	6.1909336e-05
4,482	Variance Aware Optimization of Parameterized Queries	2010	SIGMOD	6.1482936e-05
4,874	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	5.8594632e-05
5,581	CliffGuard: A Principled Framework for Finding Robust Database Designs	2015	SIGMOD	5.424205e-05
5,668	A Pay-As-You-Go Framework for Query Execution Feedback	2008	VLDB	5.3806337e-05
5,685	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	5.3717535e-05
5,815	StatAdvisor: Recommending Statistical Views	2009	VLDB	5.3165295e-05
6,278	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	5.1309442e-05
6,479	Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees	2017	SIGMOD	5.0483805e-05
6,561	On the Stability of Plan Costs and the Costs of Plan Stability	2010	VLDB	5.0099895e-05
6,763	Robustness Metrics for Relational Query Execution Plans	2018	VLDB	4.9338479e-05
6,874	ROX: Run-time Optimization of XQueries	2009	SIGMOD	4.8978984e-05
7,126	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	4.8232367e-05
7,776	Plan Stitch: Harnessing the Best of Many Plans	2018	VLDB	4.6537231e-05
7,854	dbET: Execution Time Distribution-based Plan Selection	2023	SIGMOD	4.6350172e-05
8,158	MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates	2020	SIGMOD	4.5730772e-05
8,164	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	4.5718104e-05
8,448	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	4.5100508e-05
9,380	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	4.3461329e-05
9,693	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD	4.3027391e-05
10,205	RIB: Robust Learning-based Index Benefit Estimation	2026	SIGMOD	4.1945683e-05
10,627	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	4.1945683e-05
10,630	Conformal Prediction for Verifiable Learned Query Optimization	2025	VLDB	4.1945683e-05
10,751	PAR2QO: Parametric Penalty-Aware Robust Query Optimization	2025	VLDB	4.1945683e-05
11,698	Tighter Upper Bounds for Join Cardinality Estimates	2018	SIGMOD	4.1945683e-05
12,311	Large-Scale Uncertainty Management Systems: Learning and Exploiting Your Data (Tutorial Summary)	2009	SIGMOD	4.1945683e-05
12,488	Asking the Right Questions: Model-driven Optimization using Probes	2006	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 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.0040449103
59	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00064501896
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051315959
99	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050022914
116	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046148737
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041786333
211	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033981214
222	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032828302
252	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00030632263
325	The History of Histograms (abridged)	2003	VLDB	0.00027378328
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00027358981
367	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025509745
372	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00025354779
842	Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data	2001	SIGMOD	0.00016031973
1,236	Least Expected Cost Query Optimization: An Exercise in Utility	1999	PODS	0.00013117798
1,241	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00013097578
2,180	Least Expected Cost Query Optimization: What Can We Expect?	2002	PODS	9.3481968e-05
2,556	Probabilistic Optimization of Top N Queries	1999	VLDB	8.5465733e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,685	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	5.3717535e-05
650	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.00018659177
1,638	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00011049779
1,703	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010836769
6,278	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	5.1309442e-05
1,758	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00010655546
8,213	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	4.557937e-05
1,019	Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques	2012	VLDB	0.00014625603
10,627	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	4.1945683e-05
6,763	Robustness Metrics for Relational Query Execution Plans	2018	VLDB	4.9338479e-05