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

Rank	Citing Paper	Year	Venue	Pagerank
8,956	T3: Accurate and Fast Performance Prediction for Relational Database Systems With Compiled Decision Trees	2025	SIGMOD	4.4214154e-05
9,187	POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance	2024	VLDB	4.3780059e-05
9,194	Phoebe: A Learning-based Checkpoint Optimizer	2021	VLDB	4.3761777e-05
9,213	PACE: Poisoning Attacks on Learned Cardinality Estimation	2024	SIGMOD	4.3721075e-05
9,299	Engineering High-Performance Database Engines	2014	VLDB	4.3587894e-05
9,380	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	4.3461329e-05
9,628	Approximate Sketches	2024	SIGMOD	4.3143499e-05
9,691	Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes	2023	SIGMOD	4.3035354e-05
9,728	SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning	2025	SIGMOD	4.2942813e-05
9,812	A Practical Theory of Generalization in Selectivity Learning	2025	VLDB	4.2783272e-05
9,845	Path-centric Cardinality Estimation for Subgraph Matching	2025	VLDB	4.2721228e-05
9,878	PRICE: A Pretrained Model for Cross-Database Cardinality Estimation	2025	VLDB	4.2656547e-05
9,960	An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL	2025	SIGMOD	4.2294678e-05
10,203	Reqo: A Comprehensive Learning-Based Cost Model for Robust and Explainable Query Optimization	2026	SIGMOD	4.1945683e-05
10,498	PLM4NDV: Minimizing Data Access for Number of Distinct Values Estimation with Pre-trained Language Models	2025	SIGMOD	4.1945683e-05
10,534	AdaNDV: Adaptive Number of Distinct Value Estimation via Learning to Select and Fuse Estimators	2025	VLDB	4.1945683e-05
10,590	ACE: A Cardinality Estimator for Set-Valued Queries	2025	VLDB	4.1945683e-05
10,619	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB	4.1945683e-05
10,627	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	4.1945683e-05
10,633	AQETuner: Reliable Query-level Configuration Tuning for Analytical Query Engines	2025	VLDB	4.1945683e-05
10,639	Cardinality Estimation for Having-Clauses	2025	VLDB	4.1945683e-05
10,699	The Accuracy of Cardinality Estimators: Unraveling the Evaluation Result Conundrum	2025	VLDB	4.1945683e-05
10,724	Privacy-Enhanced Database Synthesis for Benchmark Publishing	2025	VLDB	4.1945683e-05
10,840	Learned Cost Models for Query Optimization: From Batch to Streaming Systems	2025	VLDB	4.1945683e-05
10,859	Graph Transformers for Query Plan Representation: Potentials and Challenges	2025	VLDB	4.1945683e-05
10,942	Sub-optimal Join Order Identification with L1-error	2024	SIGMOD	4.1945683e-05
10,948	gSWORD: GPU-accelerated Sampling for Subgraph Counting	2024	SIGMOD	4.1945683e-05
11,752	Lusail: A System for Querying Linked Data at Scale	2018	VLDB	4.1945683e-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
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

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