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
9927
Venue
VLDB
Year
2009
Pagerank
0.00018942366
Overall Rank
629 | 95.63%
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
71 How Good Are Query Optimizers, Really? 2016 VLDB 0.00059038975
204 Learned Cardinalities: Estimating Correlated Joins with Deep Learning 2019 CIDR 0.00034784455
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,254 Selectivity Estimation for Range Predicates using Lightweight Models 2019 VLDB 0.00013027411
1,547 Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions 2011 VLDB 0.00011442359
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
1,981 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 9.8687545e-05
2,142 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 9.4507296e-05
2,165 Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation 2015 SIGMOD 9.389622e-05
2,631 Plan Bouquets: Query Processing without Selectivity Estimation 2014 SIGMOD 8.4101843e-05
2,783 Flow-Loss: Learning Cardinality Estimates That Matter 2021 VLDB 8.1293383e-05
2,969 Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models 2017 VLDB 7.7974762e-05
2,985 DSB: A Decision Support Benchmark for Workload-Driven and Traditional Database Systems 2021 VLDB 7.7795847e-05
3,001 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 7.7404487e-05
3,169 QueryFormer: A Tree Transformer Model for Query Plan Representation 2022 VLDB 7.4498425e-05
3,178 Why TPC Is Not Enough: An Analysis of the Amazon Redshift Fleet 2024 VLDB 7.4325992e-05
3,348 Lero: A Learning-to-Rank Query Optimizer 2023 VLDB 7.1904529e-05
3,449 Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation 2022 VLDB 7.0824319e-05
3,646 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 6.8853079e-05
3,725 Estimating Cardinalities with Deep Sketches 2019 SIGMOD 6.8170734e-05
3,924 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 6.6271553e-05
3,954 Efficiently Approximating Selectivity Functions using Low Overhead Regression Models 2020 VLDB 6.5926838e-05
4,417 Robust Query Driven Cardinality Estimation under Changing Workloads 2023 VLDB 6.2037371e-05
4,523 Simplicity Done Right for Join Ordering 2021 CIDR 6.1135504e-05
4,571 Adaptive Statistics in Oracle 12c 2017 VLDB 6.0773174e-05
4,694 Scalable Reservoir Sampling on Many-Core CPUs 2019 SIGMOD 5.9944898e-05
4,712 Accelerating Approximate Aggregation Queries with Expensive Predicates 2021 VLDB 5.9787986e-05
5,334 LEON: A New Framework for ML-Aided Query Optimization 2023 VLDB 5.5649836e-05
5,401 ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads 2024 VLDB 5.5285035e-05
5,469 Learned Cardinality Estimation for Similarity Queries 2021 SIGMOD 5.4898192e-05
5,633 Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server 2023 VLDB 5.4011156e-05
5,685 Exact Cardinality Query Optimization with Bounded Execution Cost 2019 SIGMOD 5.3717535e-05
5,832 Stage: Query Execution Time Prediction in Amazon Redshift 2024 SIGMOD 5.3111109e-05
5,905 Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA 2014 SIGMOD 5.2788785e-05
5,942 SAM: Database Generation from Query Workloads with Supervised Autoregressive Models 2022 SIGMOD 5.2634242e-05
6,289 Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach 2024 VLDB 5.1275309e-05
6,374 Optimization of Conjunctive Predicates for Main Memory Column Stores 2016 VLDB 5.0927058e-05
6,383 Sample-Efficient Cardinality Estimation Using Geometric Deep Learning 2024 VLDB 5.0884322e-05
6,704 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 4.9554912e-05
6,763 Robustness Metrics for Relational Query Execution Plans 2018 VLDB 4.9338479e-05
7,186 LPLM: A Neural Language Model for Cardinality Estimation of LIKE-Queries 2024 SIGMOD 4.8063731e-05
7,457 Selectivity Functions of Range Queries are Learnable* 2022 SIGMOD 4.7247191e-05
8,127 Robust Query Processing: Mission Possible 2020 VLDB 4.579056e-05
8,207 SQLStorm: Taking Database Benchmarking into the LLM Era 2025 VLDB 4.5583637e-05
8,350 alpha to omega: The Greek Alphabet of Sampling 2020 CIDR 4.5404832e-05
8,680 A Practical Approach to Groupjoin and Nested Aggregates 2021 VLDB 4.4694927e-05
8,697 Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries 2024 SIGMOD 4.4657888e-05
8,893 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 4.4275272e-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
64 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063612837
99 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00050022914
143 Optimization of Nonrecursive Queries 1986 VLDB 0.00041510555
222 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00032828302
308 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00028142852
325 The History of Histograms (abridged) 2003 VLDB 0.00027378328
326 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00027358981
378 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.0002497492
1,070 Analyzing Plan Diagrams of Database Query Optimizers 2005 VLDB 0.00014316791
1,695 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 0.00010882793
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
6,763 Robustness Metrics for Relational Query Execution Plans 2018 VLDB 4.9338479e-05
10,942 Sub-optimal Join Order Identification with L1-error 2024 SIGMOD 4.1945683e-05
71 How Good Are Query Optimizers, Really? 2016 VLDB 0.00059038975
3,952 Exact Cardinality Query Optimization for Optimizer Testing 2009 VLDB 6.5939652e-05
684 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD 0.00018179769
1,758 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00010655546
5,633 Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server 2023 VLDB 5.4011156e-05
5,685 Exact Cardinality Query Optimization with Bounded Execution Cost 2019 SIGMOD 5.3717535e-05
1,638 Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022 VLDB 0.00011049779
8,213 On the Calculation of Optimality Ranges for Relational Query Execution Plans 2018 SIGMOD 4.557937e-05