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: 6148
Venue: SIGMOD
Year: 2021
Pagerank: 5.2653318e-05
Overall Rank: 9,455 | 35.14%
DOI: 10.1145/3448016.3452805

Incoming Non-self Citations Over Time

Authors

1. Axel Hertzschuch (Technical University of Dresden)
2. Guido Moerkotte (University of Mannheim)
3. Wolfgang Lehner (Technical University of Dresden)
4. Norman May (SAP)
5. Florian Wolf (SAP)
6. Lars Fricke (SAP)

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,305	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	5.4568571e-05
10,016	Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections	2022	VLDB	5.1764556e-05
10,881	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	5.093636e-05

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
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
84	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035838391
101	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00034376651
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
365	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00020041735
388	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019410042
401	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00019092557
566	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016436005
694	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00014911698
697	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00014888851
813	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD	0.00013846487
1,503	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD	0.000105564
1,536	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	0.00010460864
2,404	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	8.6225576e-05
3,213	Estimating Cardinalities with Deep Sketches	2019	SIGMOD	7.6328677e-05
3,367	Native Store Extension for SAP HANA	2019	VLDB	7.4718829e-05
3,959	Simplicity Done Right for Join Ordering	2021	CIDR	6.9879431e-05
4,277	Adaptive Statistics in Oracle 12c	2017	VLDB	6.7873816e-05
5,693	Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA	2014	SIGMOD	6.1189424e-05
6,009	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB	6.0113733e-05

Semantically Similar Papers

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