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: hd442b1611950e8fe
Venue: CIDR
Year: 2019
Pagerank: 7.5902303e-05
Overall Rank: 3,136 | 78.99%
DOI: -
PDF: Download (CC BY 3.0)

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 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
375	Umbra: A Disk-Based System with In-Memory Performance	2020	CIDR	0.00019660459
1,603	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	0.00010090639
4,329	MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions	2019	SIGMOD	6.64569e-05
4,882	LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences	2025	SIGMOD	6.3565046e-05
5,265	DuckPGQ: Bringing SQL/PGQ to DuckDB	2023	VLDB	6.1922502e-05
5,998	SetSketch: Filling the Gap between MinHash and HyperLogLog	2021	VLDB	5.9035525e-05
6,572	MotherDuck: DuckDB in the cloud and in the client	2024	CIDR	5.7274794e-05
7,075	UltraLogLog: A Practical and More Space-Efficient Alternative to HyperLogLog for Approximate Distinct Counting	2024	VLDB	5.5911909e-05
7,387	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.5212177e-05
7,496	Fast Detection of Denial Constraint Violations	2022	VLDB	5.4968024e-05
7,782	Adaptive Factorization Using Linear-Chained Hash Tables	2025	CIDR	5.4368388e-05
7,927	A Practical Approach to Groupjoin and Nested Aggregates	2021	VLDB	5.4082473e-05
8,574	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	5.297131e-05
10,598	A Fast, Mergeable, and LDP Compatible Sketch for Counting the Number of Distinct Values in Fully Dynamic Tables	2026	SIGMOD	4.9605343e-05
10,771	Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries	2026	VLDB	4.9605343e-05
10,979	Incremental Query Optimizer Statistics in Amazon Redshift	2026	VLDB	4.9605343e-05
11,815	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB	4.9605343e-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
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061463175
78	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036725074
160	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00027775994
268	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022654182
296	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00021874894
689	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00014725904
727	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014426954
1,534	Cardinality Estimation: An Experimental Survey	2018	VLDB	0.00010309919
1,541	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	0.00010288394
2,014	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.1775869e-05
2,438	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	8.4532693e-05
4,252	Adaptive Statistics in Oracle 12c	2017	VLDB	6.6894038e-05
4,480	DigitHist: a Histogram-Based Data Summary with Tight Error Bounds	2017	VLDB	6.566036e-05
5,132	Efficient Estimation of Inclusion Coefficient using HyperLogLog Sketches	2018	VLDB	6.2462533e-05

Semantically Similar Papers

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