alpha to omega: The Greek Alphabet of Sampling

Summary: Probabilistic analysis of sampling for cardinality estimation that replaces the standard k·n/m rule with optimal estimators and tight bounds on l and q-error. Also gives sample-size formulas to meet q-error targets and yields much improved selection/join estimates. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h5112d9d5c31a0e33
Venue: CIDR
Year: 2020
Pagerank: 5.3480813e-05
Overall Rank: 8,351 | 43.88%
DOI: -
PDF: Download (CC BY 3.0)

Incoming Non-self Citations Over Time

Authors

1. Guido Moerkotte (University of Mannheim)
2. Axel Hertzschuch (Technical University of Dresden)

BibTeX Citation

@inproceedings{moerkotte_cidr20,
        address = {Amsterdam, Netherlands},
        series = {{CIDR} '20},
        title = {{alpha to omega: The Greek Alphabet of Sampling}},
        booktitle = {Proceedings of the {Conference} on {Innovative} {Data} {Systems} {Research}},
        author = {Moerkotte, Guido and Hertzschuch, Axel},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,983	Simplicity Done Right for Join Ordering	2021	CIDR	6.8722161e-05
5,236	FASTgres: Making Learned Query Optimizer Hinting Effective	2023	VLDB	6.2153504e-05
10,032	Cardinality Estimation of LIKE Predicate Queries using Deep Learning	2025	SIGMOD	5.0901632e-05
10,212	Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections	2022	VLDB	5.0579923e-05
11,265	ACE: A Cardinality Estimator for Set-Valued Queries	2025	VLDB	4.9769913e-05
11,298	Cardinality Estimation for Having-Clauses	2025	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 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.00061067652
57	On Random Sampling over Joins	1999	SIGMOD	0.00040095727
91	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00034748721
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029618887
267	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022713652
295	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00021908194
346	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00020320726
386	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019446558
688	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00014749318
795	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013934719
827	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD	0.00013629035
1,203	Fixed-Precision Estimation of Join Selectivity	1993	PODS	0.00011543634
1,678	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.9056116e-05
1,892	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.4150583e-05
2,432	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	8.4742372e-05
5,816	Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA	2014	SIGMOD	5.9817821e-05
6,108	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB	5.8831615e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,132	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR
2	1,011	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS
3	9,856	Analysis and Application of Adaptive Sampling	2000	PODS
4	2,455	A Sampling Algebra for Aggregate Estimation	2013	VLDB
5	58	Statistical Estimators for Relational Algebra Expressions	1988	PODS
6	688	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR
7	1,258	Sampling-Based Query Re-Optimization	2016	SIGMOD
8	2,432	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD
9	9,640	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD
10	79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD