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.6107287e-05
Overall Rank
3,132 | 78.96%
DOI
-
PDF
Download (CC BY 3.0)

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.00019705706
1,596 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 0.00010122962
4,330 MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions 2019 SIGMOD 6.6564176e-05
4,854 LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences 2025 SIGMOD 6.3775929e-05
5,244 DuckPGQ: Bringing SQL/PGQ to DuckDB 2023 VLDB 6.2127936e-05
5,987 SetSketch: Filling the Gap between MinHash and HyperLogLog 2021 VLDB 5.9231381e-05
6,563 MotherDuck: DuckDB in the cloud and in the client 2024 CIDR 5.7454485e-05
7,055 UltraLogLog: A Practical and More Space-Efficient Alternative to HyperLogLog for Approximate Distinct Counting 2024 VLDB 5.6097402e-05
7,368 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 5.5392867e-05
7,476 Fast Detection of Denial Constraint Violations 2022 VLDB 5.5150385e-05
7,768 Adaptive Factorization Using Linear-Chained Hash Tables 2025 CIDR 5.4548741e-05
7,911 A Practical Approach to Groupjoin and Nested Aggregates 2021 VLDB 5.4261869e-05
9,520 Panakos: Chasing the Tails for Multidimensional Data Streams 2023 VLDB 5.1683226e-05
10,532 A Fast, Mergeable, and LDP Compatible Sketch for Counting the Number of Distinct Values in Fully Dynamic Tables 2026 SIGMOD 4.9769913e-05
10,710 Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries 2026 VLDB 4.9769913e-05
10,918 Incremental Query Optimizer Statistics in Amazon Redshift 2026 VLDB 4.9769913e-05
11,771 Asymptotically Better Query Optimization Using Indexed Algebra 2023 VLDB 4.9769913e-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.00061067652
77 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00036817139
160 CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies 2004 SIGMOD 0.00027827605
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
688 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00014749318
728 Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms 2015 VLDB 0.00014436728
1,537 Cardinality Estimation: An Experimental Survey 2018 VLDB 0.00010324934
1,543 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 0.00010305662
2,003 Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee 2016 SIGMOD 9.2071735e-05
2,432 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD 8.4742372e-05
4,234 Adaptive Statistics in Oracle 12c 2017 VLDB 6.7104002e-05
4,463 DigitHist: a Histogram-Based Data Summary with Tight Error Bounds 2017 VLDB 6.5861255e-05
5,112 Efficient Estimation of Inclusion Coefficient using HyperLogLog Sketches 2018 VLDB 6.2668086e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 843 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,003 Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee 2016 SIGMOD
5 2,432 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD
6 7,572 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 749 Join Size Estimation Subject to Filter Conditions 2015 VLDB
9 9,640 Small Selectivities Matter: Lifting the Burden of Empty Samples 2021 SIGMOD
10 58 Statistical Estimators for Relational Algebra Expressions 1988 PODS