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.1472849e-05
Overall Rank: 9,632 | 35.25%
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,389	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	5.3413016e-05
10,205	Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections	2022	VLDB	5.0603873e-05
11,283	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	4.9793485e-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
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
85	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035864347
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033894985
255	The History of Histograms (abridged)	2003	VLDB	0.00022981861
371	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00019829769
386	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019444411
406	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00019045544
569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016245271
688	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00014753664
692	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00014741011
827	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD	0.00013632674
1,508	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD	0.00010440205
1,542	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	0.00010308631
2,433	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	8.4766785e-05
3,271	Estimating Cardinalities with Deep Sketches	2019	SIGMOD	7.4744941e-05
3,406	Native Store Extension for SAP HANA	2019	VLDB	7.3281944e-05
3,982	Simplicity Done Right for Join Ordering	2021	CIDR	6.8750228e-05
4,234	Adaptive Statistics in Oracle 12c	2017	VLDB	6.7134191e-05
5,815	Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA	2014	SIGMOD	5.9844993e-05
6,106	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB	5.8859291e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,364	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD
2	688	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR
3	1,542	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB
4	10,700	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,347	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR
7	3,361	Conditional Selectivity for Statistics on Query Expressions	2004	SIGMOD
8	3,131	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR
9	2,433	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD
10	1,257	Sampling-Based Query Re-Optimization	2016	SIGMOD