DBScholar

Back to papers

On Random Sampling over Joins

Summary: Random sampling over joins: feasibility of sampling join outputs without full evaluation; theoretical limits on efficiency. Proposes new join-sampling algorithms for settings where limits don't apply; empirical evaluation on SQL Server 7.0 shows efficiency gains. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h79d1755b9f1d7b67
Venue
SIGMOD
Year
1999
Pagerank
0.0003999751
Overall Rank
57 | 99.62%
DOI
10.1145/304182.304206

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{chaudhuri_sigmod99,
        title = {{On Random Sampling over Joins}},
        author = {Chaudhuri, Surajit and Motwani, Rajeev and Narasayya, Vivek},
        series = {{SIGMOD} '99},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/304182.304206},
        url = {https://dl.acm.org/doi/10.1145/304182.304206},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 90 citing papers.

Rank Citing Paper Year Venue Pagerank
6 Pig Latin: A Not-So-Foreign Language for Data Processing 2008 SIGMOD 0.0010494385
26 Models and Issues in Data Stream Systems 2002 PODS 0.00051942573
152 Query Processing, Resource Management, and Approximation in a Data Stream Management System 2003 CIDR 0.00028566618
169 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00027077763
208 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00024929198
374 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019698889
405 Deep Unsupervised Cardinality Estimation 2020 VLDB 0.00019020138
564 Congressional Samples for Approximate Answering of Group-By Queries 2000 SIGMOD 0.00016251304
594 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015814493
756 Automatic Physical Database Tuning: A Relaxation-based Approach 2005 SIGMOD 0.00014209974
770 VerdictDB: Universalizing Approximate Query Processing 2018 SIGMOD 0.00014086699
793 Random Sampling over Joins Revisited 2018 SIGMOD 0.00013903938
838 Proactive Re-Optimization 2005 SIGMOD 0.00013528646
841 Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters 2016 SIGMOD 0.00013503124
935 Dynamic Sample Selection for Approximate Query Processing 2003 SIGMOD 0.00012968914
941 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.00012938573
1,065 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00012181098
1,095 Scalable Approximate Query Processing With The DBO Engine 2007 SIGMOD 0.00012036913
1,186 ICICLES: Self-tuning Samples for Approximate Query Answering 2000 VLDB 0.00011581468
1,439 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010641857
1,511 Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation 2015 SIGMOD 0.00010408003
1,614 SciBORQ: Scientific data management with Bounds On Runtime and Quality 2011 CIDR 0.00010054823
1,839 DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models 2019 SIGMOD 9.5187688e-05
2,134 Generating Example Data for Dataflow Programs 2009 SIGMOD 8.9819242e-05
2,184 Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling 2005 VLDB 8.8972748e-05
2,228 Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models 2017 VLDB 8.7912743e-05
2,329 When Can We Trust Progress Estimators for SQL Queries? 2005 SIGMOD 8.6188984e-05
2,438 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD 8.4532693e-05
2,461 A Sampling Algebra for Aggregate Estimation 2013 VLDB 8.4123214e-05
2,633 Optimal Sampling from Sliding Windows 2009 PODS 8.1798806e-05
2,661 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD 8.1414177e-05
2,766 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 8.0221503e-05
2,888 Query Optimizers: Time to Rethink the Contract? 2009 SIGMOD 7.8895201e-05
3,212 Efficiently Approximating Selectivity Functions using Low Overhead Regression Models 2020 VLDB 7.5145409e-05
3,502 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 7.2308675e-05
3,735 Memory-Limited Execution of Windowed Stream Joins 2004 VLDB 7.0431286e-05
3,825 Spatial Online Sampling and Aggregation 2016 VLDB 6.9795872e-05
3,858 Graph-Based Synopses for Relational Selectivity Estimation 2006 SIGMOD 6.9543709e-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
4,315 ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads 2024 VLDB 6.6545412e-05
4,442 Fast Manhattan Sketches in Data Streams 2010 PODS 6.5823839e-05
4,661 Efficient Join Synopsis Maintenance for Data Warehouse 2020 SIGMOD 6.4656621e-05
4,895 Estimating arbitrary subset sums with few probes 2005 PODS 6.3498065e-05
4,981 Similarity Join Size Estimation using Locality Sensitive Hashing 2011 VLDB 6.3161219e-05
5,445 xPAD: A Platform for Analytic Data Flows 2013 SIGMOD 6.1126502e-05
5,473 Early Hash Join: A Configurable Algorithm for the Efficient and Early Production of Join Results 2005 VLDB 6.1015044e-05
5,611 StatAdvisor: Recommending Statistical Views 2009 VLDB 6.0498181e-05
5,620 On Producing Join Results Early 2003 PODS 6.0466546e-05
5,622 Responsible Data Integration: Next-generation Challenges 2022 SIGMOD 6.0460189e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 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
36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00047770864
175 Simple Random Sampling from Relational Databases 1986 VLDB 0.00026701703
492 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00017359343
750 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00014246313
1,469 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00010533259
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 4,725 Scalable Reservoir Sampling on Many-Core CPUs 2019 SIGMOD
2 9,669 Poisson Sampling over Acyclic Joins 2026 SIGMOD
3 8,300 Subset Sampling over Joins 2026 PODS
4 10,464 Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries 2026 PODS
5 1,681 Two-Level Sampling for Join Size Estimation 2017 SIGMOD
6 79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD
7 5,841 Joins on Samples: A Theoretical Guide for Practitioners 2020 VLDB
8 7,490 Reservoir Sampling over Joins 2024 SIGMOD
9 793 Random Sampling over Joins Revisited 2018 SIGMOD
10 175 Simple Random Sampling from Relational Databases 1986 VLDB