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: 6618
Venue: SIGMOD
Year: 2023
Pagerank: 6.1663946e-05
Overall Rank: 5,576 | 61.75%
DOI: 10.1145/3588907

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

Rank	Citing Paper	Year	Venue	Pagerank
5,639	LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences	2025	SIGMOD	6.1385102e-05
6,257	Join Size Bounds using l_p-Norms on Degree Sequences	2024	PODS	5.9397944e-05
6,704	ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation	2024	SIGMOD	5.797374e-05
8,513	Galley: Modern Query Optimization for Sparse Tensor Programs	2025	SIGMOD	5.4119882e-05
9,920	Still Asking: How Good Are Query Optimizers, Really?	2025	VLDB	5.1955087e-05
9,958	A Practical Theory of Generalization in Selectivity Learning	2025	VLDB	5.1879626e-05
9,971	Athena: An Effective Learning-based Framework for Query Optimizer Performance Improvement	2025	SIGMOD	5.1845938e-05
9,994	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS	5.1814573e-05
9,996	Path-centric Cardinality Estimation for Subgraph Matching	2025	VLDB	5.1814573e-05
10,027	Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation	2025	VLDB	5.1745962e-05
10,108	An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL	2025	SIGMOD	5.1347137e-05
10,135	I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server	2026	CIDR	5.093636e-05
10,438	CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations	2026	SIGMOD	5.093636e-05
10,875	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB	5.093636e-05
11,196	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	5.093636e-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
84	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035838391
323	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021264788
438	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00018471721
477	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017851226
513	NeuroCard: One Cardinality Estimator for All Tables	2021	VLDB	0.00017190574
1,061	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012369764
1,109	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012142685
1,122	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.0001209124
1,499	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	0.00010564536
1,876	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	9.5717543e-05
1,988	FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation	2021	VLDB	9.3501502e-05
2,543	Learned Cardinality Estimation: An In-depth Study	2022	SIGMOD	8.4445934e-05
2,620	Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation	2021	VLDB	8.3363963e-05
3,070	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.7900444e-05
3,086	A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation	2021	SIGMOD	7.7708642e-05
3,688	FACE: A Normalizing Flow based Cardinality Estimator	2022	VLDB	7.201795e-05
3,959	Simplicity Done Right for Join Ordering	2021	CIDR	6.9879431e-05
6,672	Computing Join Queries with Functional Dependencies	2016	PODS	5.8070233e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,438	CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations	2026	SIGMOD
2	6,543	Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation	2023	SIGMOD
3	9,994	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS
4	10,726	LpBound in Action: Cardinality Estimation with One-Sided Guarantees	2025	SIGMOD
5	5,712	Sample-Efficient Cardinality Estimation Using Geometric Deep Learning	2024	VLDB
6	5,137	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD
7	1,499	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD
8	566	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
9	1,122	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB
10	5,639	LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences	2025	SIGMOD