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 28 of 78 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,961	T3: Accurate and Fast Performance Prediction for Relational Database Systems With Compiled Decision Trees	2025	SIGMOD	4.4171776e-05
9,138	Phoebe: A Learning-based Checkpoint Optimizer	2021	VLDB	4.3842765e-05
9,191	POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance	2024	VLDB	4.3738237e-05
9,215	PACE: Poisoning Attacks on Learned Cardinality Estimation	2024	SIGMOD	4.3679174e-05
9,303	Engineering High-Performance Database Engines	2014	VLDB	4.3550373e-05
9,387	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	4.341968e-05
9,628	Approximate Sketches	2024	SIGMOD	4.3102157e-05
9,690	Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes	2023	SIGMOD	4.2994116e-05
9,727	SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning	2025	SIGMOD	4.2901665e-05
9,811	A Practical Theory of Generalization in Selectivity Learning	2025	VLDB	4.2742278e-05
9,845	Path-centric Cardinality Estimation for Subgraph Matching	2025	VLDB	4.2680295e-05
9,877	PRICE: A Pretrained Model for Cross-Database Cardinality Estimation	2025	VLDB	4.2615675e-05
9,959	An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL	2025	SIGMOD	4.2254157e-05
10,203	Reqo: A Comprehensive Learning-Based Cost Model for Robust and Explainable Query Optimization	2026	SIGMOD	4.1905499e-05
10,507	PLM4NDV: Minimizing Data Access for Number of Distinct Values Estimation with Pre-trained Language Models	2025	SIGMOD	4.1905499e-05
10,543	AdaNDV: Adaptive Number of Distinct Value Estimation via Learning to Select and Fuse Estimators	2025	VLDB	4.1905499e-05
10,598	ACE: A Cardinality Estimator for Set-Valued Queries	2025	VLDB	4.1905499e-05
10,627	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB	4.1905499e-05
10,635	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	4.1905499e-05
10,641	AQETuner: Reliable Query-level Configuration Tuning for Analytical Query Engines	2025	VLDB	4.1905499e-05
10,647	Cardinality Estimation for Having-Clauses	2025	VLDB	4.1905499e-05
10,707	The Accuracy of Cardinality Estimators: Unraveling the Evaluation Result Conundrum	2025	VLDB	4.1905499e-05
10,731	Privacy-Enhanced Database Synthesis for Benchmark Publishing	2025	VLDB	4.1905499e-05
10,844	Learned Cost Models for Query Optimization: From Batch to Streaming Systems	2025	VLDB	4.1905499e-05
10,863	Graph Transformers for Query Plan Representation: Potentials and Challenges	2025	VLDB	4.1905499e-05
10,945	Sub-optimal Join Order Identification with L1-error	2024	SIGMOD	4.1905499e-05
10,951	gSWORD: GPU-accelerated Sampling for Subgraph Counting	2024	SIGMOD	4.1905499e-05
11,760	Lusail: A System for Querying Linked Data at Scale	2018	VLDB	4.1905499e-05

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

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