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.00018959896
Overall Rank
627 | 95.65%
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.00059446482
203 Learned Cardinalities: Estimating Correlated Joins with Deep Learning 2019 CIDR 0.00034868567
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,239 Selectivity Estimation for Range Predicates using Lightweight Models 2019 VLDB 0.00013091459
1,536 Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions 2011 VLDB 0.00011458359
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
1,978 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 9.8764627e-05
2,143 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 9.4437798e-05
2,167 Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation 2015 SIGMOD 9.3879598e-05
2,632 Plan Bouquets: Query Processing without Selectivity Estimation 2014 SIGMOD 8.4153283e-05
2,781 Flow-Loss: Learning Cardinality Estimates That Matter 2021 VLDB 8.1282042e-05
2,937 DSB: A Decision Support Benchmark for Workload-Driven and Traditional Database Systems 2021 VLDB 7.8552033e-05
2,971 Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models 2017 VLDB 7.7935535e-05
2,988 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 7.7752463e-05
3,131 Why TPC Is Not Enough: An Analysis of the Amazon Redshift Fleet 2024 VLDB 7.5054309e-05
3,167 QueryFormer: A Tree Transformer Model for Query Plan Representation 2022 VLDB 7.4561078e-05
3,345 Lero: A Learning-to-Rank Query Optimizer 2023 VLDB 7.1908499e-05
3,455 Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation 2022 VLDB 7.0760196e-05
3,644 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 6.8842065e-05
3,725 Estimating Cardinalities with Deep Sketches 2019 SIGMOD 6.8117015e-05
3,924 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 6.6227223e-05
3,955 Efficiently Approximating Selectivity Functions using Low Overhead Regression Models 2020 VLDB 6.5895015e-05
4,413 Robust Query Driven Cardinality Estimation under Changing Workloads 2023 VLDB 6.1989918e-05
4,526 Simplicity Done Right for Join Ordering 2021 CIDR 6.1079584e-05
4,566 Adaptive Statistics in Oracle 12c 2017 VLDB 6.073045e-05
4,689 Scalable Reservoir Sampling on Many-Core CPUs 2019 SIGMOD 5.9899401e-05
4,703 Accelerating Approximate Aggregation Queries with Expensive Predicates 2021 VLDB 5.9793615e-05
5,339 LEON: A New Framework for ML-Aided Query Optimization 2023 VLDB 5.5596755e-05
5,405 ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads 2024 VLDB 5.5243727e-05
5,477 Learned Cardinality Estimation for Similarity Queries 2021 SIGMOD 5.4856699e-05
5,639 Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server 2023 VLDB 5.3972261e-05
5,696 Exact Cardinality Query Optimization with Bounded Execution Cost 2019 SIGMOD 5.367449e-05
5,844 Stage: Query Execution Time Prediction in Amazon Redshift 2024 SIGMOD 5.3060581e-05
5,907 Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA 2014 SIGMOD 5.2741214e-05
5,944 SAM: Database Generation from Query Workloads with Supervised Autoregressive Models 2022 SIGMOD 5.2583712e-05
6,288 Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach 2024 VLDB 5.1226099e-05
6,372 Optimization of Conjunctive Predicates for Main Memory Column Stores 2016 VLDB 5.0878306e-05
6,382 Sample-Efficient Cardinality Estimation Using Geometric Deep Learning 2024 VLDB 5.0835686e-05
6,705 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 4.9507418e-05
6,763 Robustness Metrics for Relational Query Execution Plans 2018 VLDB 4.9291549e-05
7,188 LPLM: A Neural Language Model for Cardinality Estimation of LIKE-Queries 2024 SIGMOD 4.8017628e-05
7,442 Selectivity Functions of Range Queries are Learnable* 2022 SIGMOD 4.7248554e-05
7,887 SQLStorm: Taking Database Benchmarking into the LLM Era 2025 VLDB 4.6218382e-05
8,130 Robust Query Processing: Mission Possible 2020 VLDB 4.5746794e-05
8,345 alpha to omega: The Greek Alphabet of Sampling 2020 CIDR 4.5361313e-05
8,676 A Practical Approach to Groupjoin and Nested Aggregates 2021 VLDB 4.4652082e-05
8,695 Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries 2024 SIGMOD 4.461508e-05
8,893 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 4.4232868e-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
63 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063595699
100 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00050033475
144 Optimization of Nonrecursive Queries 1986 VLDB 0.00041430126
223 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00032829841
316 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00027981848
325 The History of Histograms (abridged) 2003 VLDB 0.00027398081
326 Optimal Histograms with Quality Guarantees 1998 VLDB 0.0002737538
380 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00024943236
1,064 Analyzing Plan Diagrams of Database Query Optimizers 2005 VLDB 0.00014348262
1,691 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 0.00010890775
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.9291549e-05
10,945 Sub-optimal Join Order Identification with L1-error 2024 SIGMOD 4.1905499e-05
71 How Good Are Query Optimizers, Really? 2016 VLDB 0.00059446482
3,943 Exact Cardinality Query Optimization for Optimizer Testing 2009 VLDB 6.6067351e-05
680 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD 0.00018193263
1,756 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00010659753
5,639 Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server 2023 VLDB 5.3972261e-05
5,696 Exact Cardinality Query Optimization with Bounded Execution Cost 2019 SIGMOD 5.367449e-05
1,638 Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022 VLDB 0.00011050093
8,193 On the Calculation of Optimality Ranges for Relational Query Execution Plans 2018 SIGMOD 4.5575291e-05