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
3167
Venue
SIGMOD
Year
1999
Pagerank
0.00040810225
Overall Rank
54 | 99.64%
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.0010686205
26 Models and Issues in Data Stream Systems 2002 PODS 0.00052982574
150 Query Processing, Resource Management, and Approximation in a Data Stream Management System 2003 CIDR 0.00029208207
169 Efficient Exact Set-Similarity Joins 2006 VLDB 0.0002743469
211 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00024797217
363 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.0002005475
401 Deep Unsupervised Cardinality Estimation 2020 VLDB 0.00019092557
553 Congressional Samples for Approximate Answering of Group-By Queries 2000 SIGMOD 0.00016590619
593 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00016027871
768 Automatic Physical Database Tuning: A Relaxation-based Approach 2005 SIGMOD 0.00014173242
772 VerdictDB: Universalizing Approximate Query Processing 2018 SIGMOD 0.00014147905
802 Random Sampling over Joins Revisited 2018 SIGMOD 0.00013907725
819 Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters 2016 SIGMOD 0.00013815639
829 Proactive Re-Optimization 2005 SIGMOD 0.00013769838
909 Dynamic Sample Selection for Approximate Query Processing 2003 SIGMOD 0.00013291205
973 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.00012874284
1,064 Scalable Approximate Query Processing With The DBO Engine 2007 SIGMOD 0.00012336248
1,108 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00012145154
1,166 ICICLES: Self-tuning Samples for Approximate Query Answering 2000 VLDB 0.00011850439
1,397 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010906135
1,503 Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation 2015 SIGMOD 0.000105564
1,582 SciBORQ: Scientific data management with Bounds On Runtime and Quality 2011 CIDR 0.00010295367
1,799 DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models 2019 SIGMOD 9.7326398e-05
2,077 Generating Example Data for Dataflow Programs 2009 SIGMOD 9.2085989e-05
2,128 Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling 2005 VLDB 9.1271562e-05
2,203 Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models 2017 VLDB 8.9610447e-05
2,270 When Can We Trust Progress Estimators for SQL Queries? 2005 SIGMOD 8.8310714e-05
2,404 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD 8.6225576e-05
2,413 A Sampling Algebra for Aggregate Estimation 2013 VLDB 8.6116764e-05
2,576 Optimal Sampling from Sliding Windows 2009 PODS 8.3964437e-05
2,608 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD 8.347674e-05
2,777 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 8.1352657e-05
2,944 Query Optimizers: Time to Rethink the Contract? 2009 SIGMOD 7.9335187e-05
3,162 Efficiently Approximating Selectivity Functions using Low Overhead Regression Models 2020 VLDB 7.6785856e-05
3,453 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 7.4004131e-05
3,657 Memory-Limited Execution of Windowed Stream Joins 2004 VLDB 7.2217692e-05
3,741 Spatial Online Sampling and Aggregation 2016 VLDB 7.1586403e-05
3,788 Graph-Based Synopses for Relational Selectivity Estimation 2006 SIGMOD 7.1244416e-05
3,803 A Bi-Level Bernoulli Scheme for Database Sampling 2004 SIGMOD 7.1114677e-05
4,138 A Disk-Based Join With Probabilistic Guarantees* 2005 SIGMOD 6.8779166e-05
4,349 ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads 2024 VLDB 6.7504619e-05
4,370 Fast Manhattan Sketches in Data Streams 2010 PODS 6.7387541e-05
4,630 Efficient Join Synopsis Maintenance for Data Warehouse 2020 SIGMOD 6.5955933e-05
4,761 Estimating arbitrary subset sums with few probes 2005 PODS 6.5196044e-05
4,857 Similarity Join Size Estimation using Locality Sensitive Hashing 2011 VLDB 6.4752373e-05
5,319 xPAD: A Platform for Analytic Data Flows 2013 SIGMOD 6.2671857e-05
5,467 On Producing Join Results Early 2003 PODS 6.2074577e-05
5,510 Responsible Data Integration: Next-generation Challenges 2022 SIGMOD 6.1919207e-05
5,514 StatAdvisor: Recommending Statistical Views 2009 VLDB 6.1901666e-05
5,551 PGMJoins: Random Join Sampling with Graphical Models 2021 SIGMOD 6.1782856e-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.00077458002
36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00048351457
173 Simple Random Sampling from Relational Databases 1986 VLDB 0.00027273858
484 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00017746696
730 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00014539362
1,440 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00010778889
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 4,800 Scalable Reservoir Sampling on Many-Core CPUs 2019 SIGMOD
2 9,512 Poisson Sampling over Acyclic Joins 2026 SIGMOD
3 9,719 Subset Sampling over Joins 2026 PODS
4 10,169 Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries 2026 PODS
5 1,664 Two-Level Sampling for Join Size Estimation 2017 SIGMOD
6 76 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD
7 5,743 Joins on Samples: A Theoretical Guide for Practitioners 2020 VLDB
8 7,335 Reservoir Sampling over Joins 2024 SIGMOD
9 802 Random Sampling over Joins Revisited 2018 SIGMOD
10 173 Simple Random Sampling from Relational Databases 1986 VLDB