DBScholar

Back to papers

Small Selectivities Matter: Lifting the Burden of Empty Samples

Summary: Addresses zero-tuple selectivities in sampling-based cardinality estimation with a novel approach compatible with any DBMS capable of sampling. Shows up to two orders of magnitude reduction in estimation error and 1.3-1.8x faster responses for complex filters, with negligible impact on optimization time. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h57088dc706648d26
Venue
SIGMOD
Year
2021
Pagerank
5.1278365e-05
Overall Rank
9,667 | 35.21%
DOI
10.1145/3448016.3452805

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{hertzschuch_sigmod21,
        title = {{Small Selectivities Matter: Lifting the Burden of Empty Samples}},
        author = {Hertzschuch, Axel and Moerkotte, Guido and Lehner, Wolfgang and May, Norman and Wolf, Florian and Fricke, Lars},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3452805},
        url = {https://dl.acm.org/doi/10.1145/3448016.3452805},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank Citing Paper Year Venue Pagerank
8,412 PARQO: Penalty-Aware Robust Plan Selection in Query Optimization 2024 VLDB 5.3211467e-05
10,249 Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections 2022 VLDB 5.0412674e-05
11,347 Robust Plan Evaluation based on Approximate Probabilistic Machine Learning 2025 VLDB 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 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.00061463175
84 Learned Cardinalities: Estimating Correlated Joins with Deep Learning 2019 CIDR 0.00035920657
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033847446
254 The History of Histograms (abridged) 2003 VLDB 0.00022999992
372 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00019768921
381 Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors 2009 VLDB 0.00019497061
405 Deep Unsupervised Cardinality Estimation 2020 VLDB 0.00019020138
568 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD 0.00016221103
689 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00014725904
690 Selectivity Estimation for Range Predicates using Lightweight Models 2019 VLDB 0.00014703258
824 Adaptive Ordering of Pipelined Stream Filters 2004 SIGMOD 0.0001360282
1,511 Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation 2015 SIGMOD 0.00010408003
1,541 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 0.00010288394
2,438 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD 8.4532693e-05
3,282 Estimating Cardinalities with Deep Sketches 2019 SIGMOD 7.4491295e-05
3,408 Native Store Extension for SAP HANA 2019 VLDB 7.3093844e-05
3,995 Simplicity Done Right for Join Ordering 2021 CIDR 6.8530469e-05
4,252 Adaptive Statistics in Oracle 12c 2017 VLDB 6.6894038e-05
5,815 Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA 2014 SIGMOD 5.9683874e-05
6,122 Optimization of Conjunctive Predicates for Main Memory Column Stores 2016 VLDB 5.8638562e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 7,387 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD
2 689 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR
3 1,541 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB
4 10,771 Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries 2026 VLDB
5 79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD
6 8,363 alpha to omega: The Greek Alphabet of Sampling 2020 CIDR
7 3,136 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR
8 3,371 Conditional Selectivity for Statistics on Query Expressions 2004 SIGMOD
9 2,438 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD
10 1,261 Sampling-Based Query Re-Optimization 2016 SIGMOD