Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates

Summary: Hybrid estimator combining per-column sketches that capture full-frequency information with small random samples to correct inter-column correlation bias, enabling accurate group-by distinct-count estimates for arbitrary attribute combinations. Achieves near-perfect per-column accuracy, high multi-column accuracy, low integration overhead, and negligible estimation time via an efficient sample-scan algorithm. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 328
Venue: CIDR
Year: 2019
Pagerank: 7.6324234e-05
Overall Rank: 3,215 | 77.95%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Michael Freitag (Technical University of Munich)
2. Thomas Neumann (Technical University of Munich)

BibTeX Citation

@inproceedings{freitag_cidr19,
        address = {Amsterdam, Netherlands},
        series = {{CIDR} '19},
        title = {{Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates}},
        booktitle = {Proceedings of the {Conference} on {Innovative} {Data} {Systems} {Research}},
        author = {Freitag, Michael and Neumann, Thomas},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
422	Umbra: A Disk-Based System with In-Memory Performance	2020	CIDR	0.00018732744
1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.875587e-05
4,409	MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions	2019	SIGMOD	6.7178579e-05
5,639	LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences	2025	SIGMOD	6.1385102e-05
5,864	SetSketch: Filling the Gap between MinHash and HyperLogLog	2021	VLDB	6.0619574e-05
6,439	DuckPGQ: Bringing SQL/PGQ to DuckDB	2023	VLDB	5.8787285e-05
6,481	MotherDuck: DuckDB in the cloud and in the client	2024	CIDR	5.8669399e-05
6,920	UltraLogLog: A Practical and More Space-Efficient Alternative to HyperLogLog for Approximate Distinct Counting	2024	VLDB	5.7390922e-05
7,256	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.6625146e-05
7,396	Fast Detection of Denial Constraint Violations	2022	VLDB	5.6257228e-05
7,787	A Practical Approach to Groupjoin and Nested Aggregates	2021	VLDB	5.5449593e-05
8,232	Adaptive Factorization Using Linear-Chained Hash Tables	2025	CIDR	5.4612012e-05
9,329	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	5.2894515e-05
10,310	A Fast, Mergeable, and LDP Compatible Sketch for Counting the Number of Distinct Values in Fully Dynamic Tables	2026	SIGMOD	5.093636e-05
10,515	Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries	2026	VLDB	5.093636e-05
11,453	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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
75	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00037277061
159	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00028129426
255	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00023174541
288	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00022296371
694	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00014911698
729	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014539421
1,516	Cardinality Estimation: An Experimental Survey	2018	VLDB	0.00010520885
1,536	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	0.00010460864
1,962	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.3978414e-05
2,404	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	8.6225576e-05
4,277	Adaptive Statistics in Oracle 12c	2017	VLDB	6.7873816e-05
4,405	DigitHist: a Histogram-Based Data Summary with Tight Error Bounds	2017	VLDB	6.7218674e-05
5,257	Efficient Estimation of Inclusion Coefficient using HyperLogLog Sketches	2018	VLDB	6.2971456e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
2	36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD
3	694	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR
4	1,962	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD
5	2,404	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD
6	7,747	Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries	2024	SIGMOD
7	76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
8	737	Join Size Estimation Subject to Filter Conditions	2015	VLDB
9	9,455	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD
10	55	Statistical Estimators for Relational Algebra Expressions	1988	PODS