Back to papers
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.2721634e-05
Overall Rank
5,075 | 65.99%
DOI
10.1145/3588907
PDF
Download
(CC BY 4.0)
Incoming Non-self Citations Over Time
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 17 of 17 citing papers.
Rank
Citing Paper
Year
Venue
Pagerank
4,882
LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences 2025
SIGMOD
6.3565046e-05
5,925
Join Size Bounds using l_p-Norms on Degree Sequences 2024
PODS
5.9282898e-05
6,840
ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation 2024
SIGMOD
5.6513231e-05
8,710
Galley: Modern Query Optimization for Sparse Tensor Programs 2025
SIGMOD
5.2705676e-05
9,583
Athena: An Effective Learning-based Framework for Query Optimizer Performance Improvement 2025
SIGMOD
5.140977e-05
9,753
A Practical Theory of Generalization in Selectivity Learning 2025
VLDB
5.1159926e-05
9,810
Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation 2025
VLDB
5.112328e-05
10,143
Still Asking: How Good Are Query Optimizers, Really? 2025
VLDB
5.0597449e-05
10,220
Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints 2025
PODS
5.0460607e-05
10,221
Path-centric Cardinality Estimation for Subgraph Matching 2025
VLDB
5.0460607e-05
10,327
Data-Agnostic Cardinality Learning from Imperfect Workloads 2025
VLDB
5.0241309e-05
10,370
An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL 2025
SIGMOD
5.0010514e-05
10,379
Algebraic Subgraph Counting 2027
SIGMOD
4.9605343e-05
10,435
I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server 2026
CIDR
4.9605343e-05
10,699
CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026
SIGMOD
4.9605343e-05
11,025
How Out-of-Bounds Are Your Cardinality Estimates? 2026
VLDB
4.9605343e-05
11,593
A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions 2024
SIGMOD
4.9605343e-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.00035920657
320
DeepDB: Learn from Data, not from Queries! 2020
VLDB
0.00021128745
408
DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views 2012
VLDB
0.00018836656
461
The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds 2020
VLDB
0.00017835351
508
NeuroCard: One Cardinality Estimator for All Tables 2021
VLDB
0.00017108973
983
Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022
VLDB
0.00012677179
1,064
Are We Ready For Learned Cardinality Estimation? 2021
VLDB
0.00012181459
1,096
What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017
PODS
0.00012035761
1,444
Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019
SIGMOD
0.00010616242
1,740
Flow-Loss: Learning Cardinality Estimates That Matter 2021
VLDB
9.7289523e-05
2,009
FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation 2021
VLDB
9.1813272e-05
2,348
Learned Cardinality Estimation: An In-depth Study 2022
SIGMOD
8.5910072e-05
2,584
Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation 2021
VLDB
8.2435322e-05
2,987
Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022
VLDB
7.767043e-05
3,060
A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021
SIGMOD
7.6828463e-05
3,740
FACE: A Normalizing Flow based Cardinality Estimator 2022
VLDB
7.0398782e-05
3,995
Simplicity Done Right for Join Ordering 2021
CIDR
6.8530469e-05
6,761
Computing Join Queries with Functional Dependencies 2016
PODS
5.6705551e-05
Semantically Similar Papers