DBScholar

Back to papers

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.6141006e-05
Overall Rank
3,131 | 78.96%
DOI
-

Incoming Non-self Citations Over Time

Authors

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
373 Umbra: A Disk-Based System with In-Memory Performance 2020 CIDR 0.00019711632
1,596 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 0.00010127607
4,330 MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions 2019 SIGMOD 6.6595681e-05
4,852 LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences 2025 SIGMOD 6.3806134e-05
5,239 DuckPGQ: Bringing SQL/PGQ to DuckDB 2023 VLDB 6.215736e-05
5,987 SetSketch: Filling the Gap between MinHash and HyperLogLog 2021 VLDB 5.9259433e-05
6,561 MotherDuck: DuckDB in the cloud and in the client 2024 CIDR 5.7481696e-05
7,061 UltraLogLog: A Practical and More Space-Efficient Alternative to HyperLogLog for Approximate Distinct Counting 2024 VLDB 5.6103223e-05
7,364 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 5.5418075e-05
7,471 Fast Detection of Denial Constraint Violations 2022 VLDB 5.5176505e-05
7,774 Adaptive Factorization Using Linear-Chained Hash Tables 2025 CIDR 5.4549846e-05
7,907 A Practical Approach to Groupjoin and Nested Aggregates 2021 VLDB 5.4287568e-05
9,509 Panakos: Chasing the Tails for Multidimensional Data Streams 2023 VLDB 5.1707704e-05
10,521 A Fast, Mergeable, and LDP Compatible Sketch for Counting the Number of Distinct Values in Fully Dynamic Tables 2026 SIGMOD 4.9793485e-05
10,700 Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries 2026 VLDB 4.9793485e-05
10,909 Incremental Query Optimizer Statistics in Amazon Redshift 2026 VLDB 4.9793485e-05
11,765 Asymptotically Better Query Optimization Using Indexed Algebra 2023 VLDB 4.9793485e-05
Previous Page 1 / 1 Next

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.00061066921
77 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00036828234
160 CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies 2004 SIGMOD 0.00027837289
267 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00022722971
295 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00021914399
688 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00014753664
727 Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms 2015 VLDB 0.00014443394
1,536 Cardinality Estimation: An Experimental Survey 2018 VLDB 0.00010327422
1,542 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 0.00010308631
2,000 Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee 2016 SIGMOD 9.2112617e-05
2,433 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD 8.4766785e-05
4,234 Adaptive Statistics in Oracle 12c 2017 VLDB 6.7134191e-05
4,462 DigitHist: a Histogram-Based Data Summary with Tight Error Bounds 2017 VLDB 6.5880099e-05
5,108 Efficient Estimation of Inclusion Coefficient using HyperLogLog Sketches 2018 VLDB 6.2696201e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 842 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD
2 36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD
3 688 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR
4 2,000 Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee 2016 SIGMOD
5 2,433 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD
6 7,566 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 750 Join Size Estimation Subject to Filter Conditions 2015 VLDB
9 9,632 Small Selectivities Matter: Lifting the Burden of Empty Samples 2021 SIGMOD
10 58 Statistical Estimators for Relational Algebra Expressions 1988 PODS