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.00040095727
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.0010515896
26 Models and Issues in Data Stream Systems 2002 PODS 0.00052097907
152 Query Processing, Resource Management, and Approximation in a Data Stream Management System 2003 CIDR 0.00028657752
168 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00027151132
208 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00024899872
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.0001971778
406 Deep Unsupervised Cardinality Estimation 2020 VLDB 0.00019050182
564 Congressional Samples for Approximate Answering of Group-By Queries 2000 SIGMOD 0.00016297598
596 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015782051
751 Automatic Physical Database Tuning: A Relaxation-based Approach 2005 SIGMOD 0.00014251362
772 VerdictDB: Universalizing Approximate Query Processing 2018 SIGMOD 0.0001409096
795 Random Sampling over Joins Revisited 2018 SIGMOD 0.00013934719
837 Proactive Re-Optimization 2005 SIGMOD 0.00013551072
841 Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters 2016 SIGMOD 0.00013543
930 Dynamic Sample Selection for Approximate Query Processing 2003 SIGMOD 0.00013009255
962 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.00012818013
1,061 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00012208639
1,090 Scalable Approximate Query Processing With The DBO Engine 2007 SIGMOD 0.00012074369
1,182 ICICLES: Self-tuning Samples for Approximate Query Answering 2000 VLDB 0.00011615497
1,431 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010676907
1,509 Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation 2015 SIGMOD 0.00010436933
1,608 SciBORQ: Scientific data management with Bounds On Runtime and Quality 2011 CIDR 0.00010085907
1,828 DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models 2019 SIGMOD 9.547768e-05
2,118 Generating Example Data for Dataflow Programs 2009 SIGMOD 9.0107134e-05
2,173 Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling 2005 VLDB 8.9197633e-05
2,217 Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models 2017 VLDB 8.8151982e-05
2,320 When Can We Trust Progress Estimators for SQL Queries? 2005 SIGMOD 8.6429103e-05
2,432 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD 8.4742372e-05
2,455 A Sampling Algebra for Aggregate Estimation 2013 VLDB 8.4377251e-05
2,626 Optimal Sampling from Sliding Windows 2009 PODS 8.205667e-05
2,654 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD 8.1670397e-05
2,757 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 8.0487636e-05
2,890 Query Optimizers: Time to Rethink the Contract? 2009 SIGMOD 7.9010819e-05
3,208 Efficiently Approximating Selectivity Functions using Low Overhead Regression Models 2020 VLDB 7.5355264e-05
3,494 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 7.2548566e-05
3,729 Memory-Limited Execution of Windowed Stream Joins 2004 VLDB 7.0664086e-05
3,819 Spatial Online Sampling and Aggregation 2016 VLDB 7.0027383e-05
3,852 Graph-Based Synopses for Relational Selectivity Estimation 2006 SIGMOD 6.9756022e-05
3,872 A Bi-Level Bernoulli Scheme for Database Sampling 2004 SIGMOD 6.9512121e-05
4,218 A Disk-Based Join With Probabilistic Guarantees* 2005 SIGMOD 6.7242128e-05
4,299 ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads 2024 VLDB 6.6766173e-05
4,448 Fast Manhattan Sketches in Data Streams 2010 PODS 6.5938243e-05
4,644 Efficient Join Synopsis Maintenance for Data Warehouse 2020 SIGMOD 6.4869417e-05
4,872 Estimating arbitrary subset sums with few probes 2005 PODS 6.3707831e-05
4,960 Similarity Join Size Estimation using Locality Sensitive Hashing 2011 VLDB 6.3365273e-05
5,431 xPAD: A Platform for Analytic Data Flows 2013 SIGMOD 6.13111e-05
5,457 Early Hash Join: A Configurable Algorithm for the Efficient and Early Production of Join Results 2005 VLDB 6.1214435e-05
5,598 StatAdvisor: Recommending Statistical Views 2009 VLDB 6.0690976e-05
5,609 On Producing Join Results Early 2003 PODS 6.0665543e-05
5,610 Responsible Data Integration: Next-generation Challenges 2022 SIGMOD 6.0660772e-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.00076265429
36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00047864281
175 Simple Random Sampling from Relational Databases 1986 VLDB 0.00026776696
491 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.0001740646
746 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00014282427
1,467 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00010563809
Previous Page 1 / 1 Next

Semantically Similar Papers

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