Database Paper Browser

Back to papers

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)

Paper ID
9928
Venue
VLDB
Year
2009
Pagerank
0.00019538003
Overall Rank
387 | 97.32%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 78 citing papers.

Rank Citing Paper Year Venue Pagerank
20 How Good Are Query Optimizers, Really? 2016 VLDB 0.00058294381
86 Learned Cardinalities: Estimating Correlated Joins with Deep Learning 2019 CIDR 0.0003577267
157 Neo: A Learned Query Optimizer 2019 VLDB 0.00028782395
560 Plan-Structured Deep Neural Network Models for Query Performance Prediction 2019 VLDB 0.00016570735
715 Selectivity Estimation for Range Predicates using Lightweight Models 2019 VLDB 0.0001480646
1,053 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00012504851
1,081 Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions 2011 VLDB 0.00012387181
1,164 Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022 VLDB 0.00011978719
1,489 Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation 2015 SIGMOD 0.00010670879
1,526 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 0.00010560232
1,542 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 0.00010485163
1,931 Flow-Loss: Learning Cardinality Estimates That Matter 2021 VLDB 9.5483519e-05
2,039 Plan Bouquets: Query Processing without Selectivity Estimation 2014 SIGMOD 9.3438044e-05
2,134 DSB: A Decision Support Benchmark for Workload-Driven and Traditional Database Systems 2021 VLDB 9.1799543e-05
2,185 Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models 2017 VLDB 9.0583954e-05
2,329 QueryFormer: A Tree Transformer Model for Query Plan Representation 2022 VLDB 8.8228164e-05
2,506 Lero: A Learning-to-Rank Query Optimizer 2023 VLDB 8.5603022e-05
2,571 Why TPC Is Not Enough: An Analysis of the Amazon Redshift Fleet 2024 VLDB 8.4677877e-05
2,688 Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation 2022 VLDB 8.3172831e-05
2,689 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 8.317052e-05
2,879 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 8.0744978e-05
3,041 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 7.8821124e-05
3,150 Efficiently Approximating Selectivity Functions using Low Overhead Regression Models 2020 VLDB 7.7621739e-05
3,164 Estimating Cardinalities with Deep Sketches 2019 SIGMOD 7.7464612e-05
3,475 Robust Query Driven Cardinality Estimation under Changing Workloads 2023 VLDB 7.4606119e-05
3,877 Simplicity Done Right for Join Ordering 2021 CIDR 7.1096512e-05
3,900 Accelerating Approximate Aggregation Queries with Expensive Predicates 2021 VLDB 7.0930701e-05
4,218 Adaptive Statistics in Oracle 12c 2017 VLDB 6.8883873e-05
4,507 LEON: A New Framework for ML-Aided Query Optimization 2023 VLDB 6.723287e-05
4,555 ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads 2024 VLDB 6.6989559e-05
4,745 Learned Cardinality Estimation for Similarity Queries 2021 SIGMOD 6.5993019e-05
4,795 Scalable Reservoir Sampling on Many-Core CPUs 2019 SIGMOD 6.5716653e-05
4,986 Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server 2023 VLDB 6.4810456e-05
5,082 Exact Cardinality Query Optimization with Bounded Execution Cost 2019 SIGMOD 6.4386697e-05
5,206 Stage: Query Execution Time Prediction in Amazon Redshift 2024 SIGMOD 6.3868465e-05
5,600 SAM: Database Generation from Query Workloads with Supervised Autoregressive Models 2022 SIGMOD 6.2199759e-05
5,640 Sample-Efficient Cardinality Estimation Using Geometric Deep Learning 2024 VLDB 6.2029974e-05
5,647 Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA 2014 SIGMOD 6.2011141e-05
5,845 Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach 2024 VLDB 6.1294746e-05
5,935 Optimization of Conjunctive Predicates for Main Memory Column Stores 2016 VLDB 6.0980013e-05
6,227 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 6.0093252e-05
6,267 Robustness Metrics for Relational Query Execution Plans 2018 VLDB 5.9973569e-05
6,648 LPLM: A Neural Language Model for Cardinality Estimation of LIKE-Queries 2024 SIGMOD 5.8722385e-05
7,092 Selectivity Functions of Range Queries are Learnable* 2022 SIGMOD 5.7588694e-05
7,579 SQLStorm: Taking Database Benchmarking into the LLM Era 2025 VLDB 5.6492649e-05
7,724 Robust Query Processing: Mission Possible 2020 VLDB 5.6179697e-05
8,054 alpha to omega: The Greek Alphabet of Sampling 2020 CIDR 5.5562082e-05
8,490 Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries 2024 SIGMOD 5.4868152e-05
8,526 A Practical Approach to Groupjoin and Nested Aggregates 2021 VLDB 5.4787362e-05
8,842 T3: Accurate and Fast Performance Prediction for Relational Database Systems With Compiled Decision Trees 2025 SIGMOD 5.4241294e-05
Previous Page 1 / 2 Next

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
35 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00048862242
98 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00034732081
132 Optimization of Nonrecursive Queries 1986 VLDB 0.00030449256
167 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.000277743
255 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00023376534
256 The History of Histograms (abridged) 2003 VLDB 0.00023353808
266 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00023039606
281 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00022539374
975 Analyzing Plan Diagrams of Database Query Optimizers 2005 VLDB 0.0001295619
1,619 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 0.00010273734
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
6,267 Robustness Metrics for Relational Query Execution Plans 2018 VLDB 5.9973569e-05
10,945 Sub-optimal Join Order Identification with L1-error 2024 SIGMOD 5.1725247e-05
20 How Good Are Query Optimizers, Really? 2016 VLDB 0.00058294381
3,451 Exact Cardinality Query Optimization for Optimizer Testing 2009 VLDB 7.4749615e-05
567 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD 0.00016486291
1,250 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00011563119
4,986 Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server 2023 VLDB 6.4810456e-05
5,082 Exact Cardinality Query Optimization with Bounded Execution Cost 2019 SIGMOD 6.4386697e-05
1,164 Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022 VLDB 0.00011978719
7,871 On the Calculation of Optimality Ranges for Relational Query Execution Plans 2018 SIGMOD 5.5951573e-05