DBScholar

Back to papers

Joins on Samples: A Theoretical Guide for Practitioners

Summary: Provides a theoretical guide to sample-based join AQP, separating output cardinality from estimator variance and proving variance lower bounds. A hybrid stratified/universe/Bernoulli scheme is constant-factor optimal, with a decentralized implementation for distributed systems. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h843370efc39377ef
Venue
VLDB
Year
2020
Pagerank
5.9569427e-05
Overall Rank
5,841 | 60.85%
DOI
10.14778/3372716.3372726
PDF
Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{huang_vldb20,
        title = {{Joins on Samples: A Theoretical Guide for Practitioners}},
        author = {Huang, Dawei and Yoon, Dong Young and Pettie, Seth and Mozafari, Barzan},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {4},
        pages = {547--560},
        doi = {10.14778/3372716.3372726},
        url = {https://doi.org/10.14778/3372716.3372726},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank Citing Paper Year Venue Pagerank
2,772 Instance-Optimized Data Layouts for Cloud Analytics Workloads 2021 SIGMOD 8.0148928e-05
3,060 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 7.6828463e-05
3,093 Correlation Sketches for Approximate Join-Correlation Queries 2021 SIGMOD 7.6378811e-05
5,435 Towards Distribution-aware Query Answering in Data Markets 2022 VLDB 6.1167862e-05
7,745 PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees 2025 SIGMOD 5.4457135e-05
8,790 One Size Does Not Fit All: A Bandit-Based Sampler Combination Framework with Theoretical Guarantees 2022 SIGMOD 5.2633515e-05
9,454 Towards Observability for Production Machine Learning Pipelines 2022 VLDB 5.1607878e-05
10,480 Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees 2026 SIGMOD 4.9605343e-05
11,591 Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024 SIGMOD 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 37 of 37 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
9 Online Aggregation 1997 SIGMOD 0.00076079812
57 On Random Sampling over Joins 1999 SIGMOD 0.0003999751
84 Learned Cardinalities: Estimating Correlated Joins with Deep Learning 2019 CIDR 0.00035920657
135 Ripple Joins for Online Aggregation 1999 SIGMOD 0.00029805026
138 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00029532435
594 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015814493
689 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00014725904
752 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00014234789
770 VerdictDB: Universalizing Approximate Query Processing 2018 SIGMOD 0.00014086699
793 Random Sampling over Joins Revisited 2018 SIGMOD 0.00013903938
841 Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters 2016 SIGMOD 0.00013503124
844 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00013498392
935 Dynamic Sample Selection for Approximate Query Processing 2003 SIGMOD 0.00012968914
951 Aqua: A Fast Decision Support System Using Approximate Query Answers 1999 VLDB 0.00012886042
1,022 Online Aggregation for Large MapReduce Jobs 2011 VLDB 0.00012400958
1,156 QuickSel: Quick Selectivity Learning with Mixture Models 2020 SIGMOD 0.00011759683
1,186 ICICLES: Self-tuning Samples for Approximate Query Answering 2000 VLDB 0.00011581468
1,254 Blink and It's Done: Interactive Queries on Very Large Data 2012 VLDB 0.00011314204
1,261 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00011289724
1,435 Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems 2014 SIGMOD 0.00010659454
1,681 Two-Level Sampling for Join Size Estimation 2017 SIGMOD 9.8821344e-05
1,828 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 9.5396315e-05
1,832 A Scalable Hash Ripple Join Algorithm 2002 SIGMOD 9.5365548e-05
1,924 The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing 2014 SIGMOD 9.3535088e-05
2,040 Database Learning: Toward a Database that Becomes Smarter Every Time 2017 SIGMOD 9.1319608e-05
2,108 Vizdom: Interactive Analytics through Pen and Touch 2015 VLDB 9.0229444e-05
2,362 Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries 2008 VLDB 8.5601252e-05
2,871 SnappyData: A Unified Cluster for Streaming, Transactions, and Interactive Analytics 2017 CIDR 7.9024682e-05
2,896 Distributed Lock Management with RDMA: Decentralization without Starvation 2018 SIGMOD 7.8855049e-05
3,092 Continuous Sampling for Online Aggregation Over Multiple Queries 2010 SIGMOD 7.638249e-05
3,220 Turbo-Charging Estimate Convergence in DBO 2009 VLDB 7.5077984e-05
3,348 I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making 2017 VLDB 7.3783668e-05
3,871 Is Min-Wise Hashing Optimal for Summarizing Set Intersection? 2014 PODS 6.9414117e-05
3,884 A Bi-Level Bernoulli Scheme for Database Sampling 2004 SIGMOD 6.9285249e-05
4,236 A Disk-Based Join With Probabilistic Guarantees* 2005 SIGMOD 6.7028998e-05
5,324 CliffGuard: A Principled Framework for Finding Robust Database Designs 2015 SIGMOD 6.1645235e-05
6,014 Approximate Query Engines: Commercial Challenges and Research Opportunities 2017 SIGMOD 5.8956963e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 432 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS
2 1,435 Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems 2014 SIGMOD
3 1,206 Fixed-Precision Estimation of Join Selectivity 1993 PODS
4 1,681 Two-Level Sampling for Join Size Estimation 2017 SIGMOD
5 2,014 Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee 2016 SIGMOD
6 793 Random Sampling over Joins Revisited 2018 SIGMOD
7 10,464 Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries 2026 PODS
8 7,490 Reservoir Sampling over Joins 2024 SIGMOD
9 6,198 Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing 2021 SIGMOD
10 57 On Random Sampling over Joins 1999 SIGMOD