SafeBound: A Practical System for Generating Cardinality Bounds

Summary: SafeBound is the first practical system for guaranteed upper bounds on cardinalities with predicate support. Extends degree-sequence bounds via compression and inference, delivering up to 80% gains vs PostgreSQL and 500x faster planning, with less space. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hdc9aa3f22b027bc3
Venue: SIGMOD
Year: 2023
Pagerank: 6.2197808e-05
Overall Rank: 5,224 | 64.89%
DOI: 10.1145/3588907
PDF: Download (CC BY 4.0)

Incoming Non-self Citations Over Time

Authors

1. Kyle B. Deeds (University of Washington)
2. Dan Suciu (University of Washington)
3. Magdalena Balazinska (University of Washington)

BibTeX Citation

@inproceedings{deeds_sigmod23,
        title = {{SafeBound: A Practical System for Generating Cardinality Bounds}},
        author = {Deeds, Kyle B. and Suciu, Dan and Balazinska, Magdalena},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3588907},
        url = {https://dl.acm.org/doi/10.1145/3588907},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,854	LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences	2025	SIGMOD	6.3775929e-05
5,910	Join Size Bounds using l_p-Norms on Degree Sequences	2024	PODS	5.9478947e-05
6,824	ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation	2024	SIGMOD	5.670071e-05
8,690	Galley: Modern Query Optimization for Sparse Tensor Programs	2025	SIGMOD	5.2880532e-05
9,556	Athena: An Effective Learning-based Framework for Query Optimizer Performance Improvement	2025	SIGMOD	5.1580326e-05
9,723	A Practical Theory of Generalization in Selectivity Learning	2025	VLDB	5.1329654e-05
10,107	Still Asking: How Good Are Query Optimizers, Really?	2025	VLDB	5.0765311e-05
10,186	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS	5.0628015e-05
10,187	Path-centric Cardinality Estimation for Subgraph Matching	2025	VLDB	5.0628015e-05
10,221	Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation	2025	VLDB	5.0560976e-05
10,300	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB	5.0407989e-05
10,343	An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL	2025	SIGMOD	5.0176429e-05
10,368	I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server	2026	CIDR	4.9769913e-05
10,638	CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations	2026	SIGMOD	4.9769913e-05
10,964	How Out-of-Bounds Are Your Cardinality Estimates?	2026	VLDB	4.9769913e-05
11,544	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
85	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035876108
318	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021166957
408	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00018894165
458	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017880664
510	NeuroCard: One Cardinality Estimator for All Tables	2021	VLDB	0.00017059914
981	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00012713454
1,065	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012202293
1,091	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012068611
1,465	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	0.00010572023
1,735	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	9.7566604e-05
2,002	FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation	2021	VLDB	9.2076835e-05
2,342	Learned Cardinality Estimation: An In-depth Study	2022	SIGMOD	8.6074783e-05
2,583	Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation	2021	VLDB	8.2589842e-05
2,975	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.7905662e-05
3,053	A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation	2021	SIGMOD	7.7041081e-05
3,742	FACE: A Normalizing Flow based Cardinality Estimator	2022	VLDB	7.0564546e-05
3,983	Simplicity Done Right for Join Ordering	2021	CIDR	6.8722161e-05
6,745	Computing Join Queries with Functional Dependencies	2016	PODS	5.6890943e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,664	Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation	2023	SIGMOD
2	10,186	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS
3	9,489	LpBound in Action: Cardinality Estimation with One-Sided Guarantees	2025	SIGMOD
4	5,630	Sample-Efficient Cardinality Estimation Using Geometric Deep Learning	2024	VLDB
5	5,200	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD
6	10,964	How Out-of-Bounds Are Your Cardinality Estimates?	2026	VLDB
7	1,465	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD
8	569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
9	981	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB
10	4,854	LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences	2025	SIGMOD