DBScholar

Back to papers

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
h7c5c5e38e12d9528
Venue
SIGMOD
Year
2005
Pagerank
0.00016244162
Overall Rank
569 | 96.18%
DOI
10.1145/1066157.1066172

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{babcock_sigmod05,
        title = {{Towards a Robust Query Optimizer: A Principled and Practical Approach}},
        author = {Babcock, Brian and Chaudhuri, Surajit},
        series = {{SIGMOD} '05},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1066157.1066172},
        url = {https://dl.acm.org/doi/10.1145/1066157.1066172},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 45 of 45 citing papers.

Rank Citing Paper Year Venue Pagerank
15 How Good Are Query Optimizers, Really? 2016 VLDB 0.00061067652
144 Neo: A Learned Query Optimizer 2019 VLDB 0.00029090793
560 Plan-Structured Deep Neural Network Models for Query Performance Prediction 2019 VLDB 0.00016408613
837 Proactive Re-Optimization 2005 SIGMOD 0.00013551072
1,258 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00011308863
1,465 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 0.00010572023
1,605 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2019 SIGMOD 0.00010095581
1,800 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2018 VLDB 9.6082185e-05
1,989 Plan Bouquets: Query Processing without Selectivity Estimation 2014 SIGMOD 9.2469024e-05
2,524 Multi-Objective Parametric Query Optimization 2015 VLDB 8.3400278e-05
2,686 Cost-based or Learning-based? A Hybrid Query Optimizer for Query Plan Selection 2022 VLDB 8.1300913e-05
2,890 Query Optimizers: Time to Rethink the Contract? 2009 SIGMOD 7.9010819e-05
3,057 Towards a Hands-Free Query Optimizer through Deep Learning 2019 CIDR 7.6960881e-05
3,274 Large-Scale Collective Entity Matching 2011 VLDB 7.4675244e-05
3,396 Variance Aware Optimization of Parameterized Queries 2010 SIGMOD 7.3386533e-05
3,527 Identifying Robust Plans through Plan Diagram Reduction 2008 VLDB 7.2283486e-05
3,593 Looking Ahead Makes Query Plans Robust: Making the Initial Case with In-Memory Star Schema Data Warehouse Workloads 2017 VLDB 7.1803217e-05
4,508 Xplus: A SQL-Tuning-Aware Query Optimizer 2010 VLDB 6.5696141e-05
4,945 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 6.3418058e-05
5,081 Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees 2017 SIGMOD 6.2830143e-05
5,200 Exact Cardinality Query Optimization with Bounded Execution Cost 2019 SIGMOD 6.2303304e-05
5,227 Approximation Schemes for Many-Objective Query Optimization 2014 SIGMOD 6.2183387e-05
5,310 CliffGuard: A Principled Framework for Finding Robust Database Designs 2015 SIGMOD 6.184026e-05
5,475 A Pay-As-You-Go Framework for Query Execution Feedback 2008 VLDB 6.115573e-05
5,598 StatAdvisor: Recommending Statistical Views 2009 VLDB 6.0690976e-05
5,658 Uncertainty Aware Query Execution Time Prediction 2014 VLDB 6.0460211e-05
5,988 On the Stability of Plan Costs and the Costs of Plan Stability 2010 VLDB 5.9229752e-05
6,114 Robustness Metrics for Relational Query Execution Plans 2018 VLDB 5.8796178e-05
6,246 Warding off the Dangers of Data Corruption with Amulet 2011 SIGMOD 5.8348656e-05
6,796 dbET: Execution Time Distribution-based Plan Selection 2023 SIGMOD 5.6784895e-05
6,802 ROX: Run-time Optimization of XQueries 2009 SIGMOD 5.6773357e-05
7,074 Plan Stitch: Harnessing the Best of Many Plans 2018 VLDB 5.604902e-05
8,046 Efficiently Computing Join Orders with Heuristic Search 2023 SIGMOD 5.3992239e-05
8,348 MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates 2020 SIGMOD 5.3486679e-05
8,393 PARQO: Penalty-Aware Robust Plan Selection in Query Optimization 2024 VLDB 5.3387995e-05
8,531 ROME: Robust Query Optimization via Parallel Multi-Plan Execution 2024 SIGMOD 5.3206021e-05
8,969 Conformal Prediction for Verifiable Learned Query Optimization 2025 VLDB 5.2477982e-05
9,640 Small Selectivities Matter: Lifting the Burden of Empty Samples 2021 SIGMOD 5.1448486e-05
9,735 PAR2QO: Parametric Penalty-Aware Robust Query Optimization 2025 VLDB 5.1325223e-05
10,380 Coresets for Robust Query Optimization 2026 PODS 4.9769913e-05
10,692 RIB: Robust Learning-based Index Benefit Estimation 2026 SIGMOD 4.9769913e-05
11,291 Robust Plan Evaluation based on Approximate Probabilistic Machine Learning 2025 VLDB 4.9769913e-05
12,208 Tighter Upper Bounds for Join Cardinality Estimates 2018 SIGMOD 4.9769913e-05
12,801 Large-Scale Uncertainty Management Systems: Learning and Exploiting Your Data (Tutorial Summary) 2009 SIGMOD 4.9769913e-05
12,977 Asking the Right Questions: Model-driven Optimization using Probes 2006 PODS 4.9769913e-05
Previous Page 1 / 1 Next

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.0023943337
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.0004772731
77 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00036817139
79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00036476265
91 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00034748721
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033884854
119 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.0003136296
138 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00029618887
169 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00027126333
232 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.0002378554
255 The History of Histograms (abridged) 2003 VLDB 0.00022974524
275 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00022404363
286 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.00022112534
346 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00020320726
700 Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data 2001 SIGMOD 0.00014675903
1,078 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012149796
1,122 Least Expected Cost Query Optimization: An Exercise in Utility 1999 PODS 0.00011933634
1,821 Least Expected Cost Query Optimization: What Can We Expect? 2002 PODS 9.5646318e-05
2,183 Probabilistic Optimization of Top N Queries 1999 VLDB 8.9044171e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 471 Robust Query Processing through Progressive Optimization 2004 SIGMOD
2 981 Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022 VLDB
3 5,658 Uncertainty Aware Query Execution Time Prediction 2014 VLDB
4 1,065 Are We Ready For Learned Cardinality Estimation? 2021 VLDB
5 7,603 On the Calculation of Optimality Ranges for Relational Query Execution Plans 2018 SIGMOD
6 1,258 Sampling-Based Query Re-Optimization 2016 SIGMOD
7 682 Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques 2012 VLDB
8 11,291 Robust Plan Evaluation based on Approximate Probabilistic Machine Learning 2025 VLDB
9 10,380 Coresets for Robust Query Optimization 2026 PODS
10 6,114 Robustness Metrics for Relational Query Execution Plans 2018 VLDB