How Out-of-Bounds Are Your Cardinality Estimates?

Summary: Introduces a soundness checker that compares DBMS cardinality estimates against provable xBound/LpBound lower and upper bounds. Demonstrates severe violations in established optimizers and explores bound quality across benchmark queries and parameters. (summarized by gpt-5.6-luna on Aug 28 2026)

Paper ID: h1661f445e85f9189
Venue: VLDB
Year: 2026
Pagerank: 4.9793485e-05
Overall Rank: 10,955 | 26.35%
DOI: 10.14778/3827998.3828052

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Mihail Stoian (University of Technology Nuremberg)
2. Tiemo Bang (Microsoft)
3. Hangdong Zhao (Microsoft)
4. Jesús Camacho-Rodríguez (Microsoft Fabric Data Warehouse)
5. Yuanyuan Tian (Microsoft)
6. Andreas Kipf (University of Technology Nuremberg)

BibTeX Citation

@article{stoian_vldb26,
        title = {{How Out-of-Bounds Are Your Cardinality Estimates?}},
        author = {Stoian, Mihail and Bang, Tiemo and Zhao, Hangdong and Camacho-Rodríguez, Jesús and Tian, Yuanyuan and Kipf, Andreas},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {12},
        pages = {4510--4513},
        doi = {10.14778/3827998.3828052},
        url = {https://doi.org/10.14778/3827998.3828052},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
85	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035864347
145	Neo: A Learned Query Optimizer	2019	VLDB	0.0002908188
318	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021167555
406	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00019045544
982	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00012714044
2,846	FactorJoin: A New Cardinality Estimation Framework for Join Queries	2023	SIGMOD	7.9453616e-05
4,132	SQLStorm: Taking Database Benchmarking into the LLM Era	2025	VLDB	6.7885553e-05
4,852	LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences	2025	SIGMOD	6.3806134e-05
5,219	SafeBound: A Practical System for Generating Cardinality Bounds	2023	SIGMOD	6.222726e-05
5,683	How Good are Learned Cost Models, Really? Insights from Query Optimization Tasks	2025	SIGMOD	6.0392183e-05
9,478	LpBound in Action: Cardinality Estimation with One-Sided Guarantees	2025	SIGMOD	5.1708619e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,367	Exact Cardinality Query Optimization for Optimizer Testing	2009	VLDB
2	5,199	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD
3	10,627	CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations	2026	SIGMOD
4	386	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB
5	569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
6	982	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB
7	2,974	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB
8	5,219	SafeBound: A Practical System for Generating Cardinality Bounds	2023	SIGMOD
9	9,478	LpBound in Action: Cardinality Estimation with One-Sided Guarantees	2025	SIGMOD
10	4,852	LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences	2025	SIGMOD