Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors
Summary: Defines q-error for cardinality estimates and bounds that yield an optimal plan when q-error is small. Shows plan cost within q^4 of optimal under bounded q-error and gives methods to compute best q-error approximations and size-estimate synopses, with experiments. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Guido Moerkotte (University of Mannheim)
- 2. Thomas Neumann (Max Planck Institute)
- 3. Gabriele Steidl (University of Mannheim)
BibTeX Citation
@article{moerkotte_vldb09,
title = {{Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors}},
author = {Moerkotte, Guido and Neumann, Thomas and Steidl, Gabriele},
journal = {PVLDB},
series = {{VLDB} '09},
doi = {10.14778/1687627.1687738},
url = {https://doi.org/10.14778/1687627.1687738},
year = {2009}
}Incoming Citations (Sorted by Pagerank)
Showing 29 of 79 citing papers.
Outgoing Citations (Sorted by Pagerank)
Showing 10 of 10 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 37 | Improved Histograms for Selectivity Estimation of Range Predicates | 1996 | SIGMOD | 0.00047731453 |
| 91 | On the Propagation of Errors in the Size of Join Results | 1991 | SIGMOD | 0.0003475226 |
| 143 | Optimization of Nonrecursive Queries | 1986 | VLDB | 0.00029179719 |
| 169 | Wavelet-Based Histograms for Selectivity Estimation | 1998 | SIGMOD | 0.00027134723 |
| 255 | The History of Histograms (abridged) | 2003 | VLDB | 0.00022981861 |
| 267 | Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports | 2001 | VLDB | 0.00022722971 |
| 275 | Optimal Histograms with Quality Guarantees | 1998 | VLDB | 0.00022413521 |
| 295 | Towards Estimation Error Guarantees for Distinct Values | 2000 | PODS | 0.00021914399 |
| 996 | Analyzing Plan Diagrams of Database Query Optimizers | 2005 | VLDB | 0.00012634603 |
| 1,741 | Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation | 1999 | VLDB | 9.7382372e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 10,368 | Coresets for Robust Query Optimization | 2026 | PODS |
| 2 | 11,507 | Sub-optimal Join Order Identification with L1-error | 2024 | SIGMOD |
| 3 | 15 | How Good Are Query Optimizers, Really? | 2016 | VLDB |
| 4 | 3,367 | Exact Cardinality Query Optimization for Optimizer Testing | 2009 | VLDB |
| 5 | 569 | Towards a Robust Query Optimizer: A Principled and Practical Approach | 2005 | SIGMOD |
| 6 | 1,257 | Sampling-Based Query Re-Optimization | 2016 | SIGMOD |
| 7 | 5,022 | Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server | 2023 | VLDB |
| 8 | 5,199 | Exact Cardinality Query Optimization with Bounded Execution Cost | 2019 | SIGMOD |
| 9 | 982 | Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation | 2022 | VLDB |
| 10 | 7,597 | On the Calculation of Optimality Ranges for Relational Query Execution Plans | 2018 | SIGMOD |