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: 3630
Venue: SIGMOD
Year: 2005
Pagerank: 0.00018193263
Overall Rank: 680 | 95.28%
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.00059446482
329	Neo: A Learned Query Optimizer	2019	VLDB	0.00027301488
876	Plan-Structured Deep Neural Network Models for Query Performance Prediction	2019	VLDB	0.00015660534
1,268	Proactive Re-Optimization	2005	SIGMOD	0.00012914584
1,756	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00010659753
2,143	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	9.4437798e-05
2,154	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2018	VLDB	9.4176683e-05
2,222	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2019	SIGMOD	9.2598438e-05
2,632	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	8.4153283e-05
2,652	Multi-Objective Parametric Query Optimization	2015	VLDB	8.3662031e-05
3,402	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD	7.134261e-05
3,570	Large-Scale Collective Entity Matching	2011	VLDB	6.9563715e-05
3,658	Towards a Hands-Free Query Optimizer through Deep Learning	2019	CIDR	6.8700949e-05
3,729	Cost-based or Learning-based? A Hybrid Query Optimizer for Query Plan Selection	2022	VLDB	6.8078013e-05
4,196	Warding off the Dangers of Data Corruption with Amulet	2011	SIGMOD	6.3630395e-05
4,272	Looking Ahead Makes Query Plans Robust: Making the Initial Case with In-Memory Star Schema Data Warehouse Workloads	2017	VLDB	6.2933353e-05
4,342	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB	6.2680535e-05
4,434	Xplus: A SQL-Tuning-Aware Query Optimizer	2010	VLDB	6.1851729e-05
4,480	Variance Aware Optimization of Parameterized Queries	2010	SIGMOD	6.1433292e-05
4,876	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	5.8544467e-05
5,578	CliffGuard: A Principled Framework for Finding Robust Database Designs	2015	SIGMOD	5.4231783e-05
5,676	A Pay-As-You-Go Framework for Query Execution Feedback	2008	VLDB	5.3768269e-05
5,696	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	5.367449e-05
5,824	StatAdvisor: Recommending Statistical Views	2009	VLDB	5.311975e-05
6,277	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	5.1260947e-05
6,471	Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees	2017	SIGMOD	5.0438582e-05
6,561	On the Stability of Plan Costs and the Costs of Plan Stability	2010	VLDB	5.0055336e-05
6,763	Robustness Metrics for Relational Query Execution Plans	2018	VLDB	4.9291549e-05
6,879	ROX: Run-time Optimization of XQueries	2009	SIGMOD	4.8934866e-05
7,122	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	4.8199209e-05
7,776	Plan Stitch: Harnessing the Best of Many Plans	2018	VLDB	4.6493147e-05
7,854	dbET: Execution Time Distribution-based Plan Selection	2023	SIGMOD	4.6306186e-05
8,149	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	4.5715614e-05
8,162	MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates	2020	SIGMOD	4.5686903e-05
8,440	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	4.505741e-05
9,387	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	4.341968e-05
9,692	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD	4.2986161e-05
10,205	RIB: Robust Learning-based Index Benefit Estimation	2026	SIGMOD	4.1905499e-05
10,635	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	4.1905499e-05
10,638	Conformal Prediction for Verifiable Learned Query Optimization	2025	VLDB	4.1905499e-05
10,757	PAR2QO: Parametric Penalty-Aware Robust Query Optimization	2025	VLDB	4.1905499e-05
11,703	Tighter Upper Bounds for Join Cardinality Estimates	2018	SIGMOD	4.1905499e-05
12,319	Large-Scale Uncertainty Management Systems: Learning and Exploiting Your Data (Tutorial Summary)	2009	SIGMOD	4.1905499e-05
12,497	Asking the Right Questions: Model-driven Optimization using Probes	2006	PODS	4.1905499e-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.0040465394
60	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00064450997
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051431888
100	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050033475
114	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046317654
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041819767
212	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033997204
223	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032829841
250	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00030640525
325	The History of Histograms (abridged)	2003	VLDB	0.00027398081
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002737538
369	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025502381
373	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00025354685
838	Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data	2001	SIGMOD	0.00016024923
1,234	Least Expected Cost Query Optimization: An Exercise in Utility	1999	PODS	0.00013115865
1,240	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00013090678
2,187	Least Expected Cost Query Optimization: What Can We Expect?	2002	PODS	9.3429142e-05
2,552	Probabilistic Optimization of Top N Queries	1999	VLDB	8.5540341e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059446482
650	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.0001865144
1,638	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00011050093
1,699	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010848882
6,277	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	5.1260947e-05
8,193	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	4.5575291e-05
1,756	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00010659753
1,017	Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques	2012	VLDB	0.00014627121
10,635	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	4.1905499e-05
6,763	Robustness Metrics for Relational Query Execution Plans	2018	VLDB	4.9291549e-05