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.00040108301
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.001052036
26 Models and Issues in Data Stream Systems 2002 PODS 0.00052121228
152 Query Processing, Resource Management, and Approximation in a Data Stream Management System 2003 CIDR 0.0002867034
168 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00027163517
208 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00024884544
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019720059
406 Deep Unsupervised Cardinality Estimation 2020 VLDB 0.00019045544
564 Congressional Samples for Approximate Answering of Group-By Queries 2000 SIGMOD 0.00016296665
596 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015785583
751 Automatic Physical Database Tuning: A Relaxation-based Approach 2005 SIGMOD 0.0001425375
784 VerdictDB: Universalizing Approximate Query Processing 2018 SIGMOD 0.00014012614
795 Random Sampling over Joins Revisited 2018 SIGMOD 0.00013938779
836 Proactive Re-Optimization 2005 SIGMOD 0.00013557047
840 Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters 2016 SIGMOD 0.0001354605
931 Dynamic Sample Selection for Approximate Query Processing 2003 SIGMOD 0.00013011667
961 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.0001282305
1,082 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00012122749
1,090 Scalable Approximate Query Processing With The DBO Engine 2007 SIGMOD 0.00012077577
1,183 ICICLES: Self-tuning Samples for Approximate Query Answering 2000 VLDB 0.00011616705
1,431 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010681774
1,508 Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation 2015 SIGMOD 0.00010440205
1,607 SciBORQ: Scientific data management with Bounds On Runtime and Quality 2011 CIDR 0.0001008742
1,829 DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models 2019 SIGMOD 9.5510333e-05
2,116 Generating Example Data for Dataflow Programs 2009 SIGMOD 9.0149557e-05
2,171 Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling 2005 VLDB 8.9239861e-05
2,216 Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models 2017 VLDB 8.8177753e-05
2,318 When Can We Trust Progress Estimators for SQL Queries? 2005 SIGMOD 8.6464837e-05
2,433 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD 8.4766785e-05
2,456 A Sampling Algebra for Aggregate Estimation 2013 VLDB 8.4377192e-05
2,624 Optimal Sampling from Sliding Windows 2009 PODS 8.2095532e-05
2,655 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD 8.1706092e-05
2,757 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 8.0525756e-05
2,891 Query Optimizers: Time to Rethink the Contract? 2009 SIGMOD 7.9021718e-05
3,210 Efficiently Approximating Selectivity Functions using Low Overhead Regression Models 2020 VLDB 7.5363533e-05
3,494 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 7.2582926e-05
3,727 Memory-Limited Execution of Windowed Stream Joins 2004 VLDB 7.0696489e-05
3,818 Spatial Online Sampling and Aggregation 2016 VLDB 7.0060535e-05
3,851 Graph-Based Synopses for Relational Selectivity Estimation 2006 SIGMOD 6.9785886e-05
3,871 A Bi-Level Bernoulli Scheme for Database Sampling 2004 SIGMOD 6.9543581e-05
4,217 A Disk-Based Join With Probabilistic Guarantees* 2005 SIGMOD 6.7271293e-05
4,311 ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads 2024 VLDB 6.6727978e-05
4,446 Fast Manhattan Sketches in Data Streams 2010 PODS 6.5969248e-05
4,642 Efficient Join Synopsis Maintenance for Data Warehouse 2020 SIGMOD 6.4898745e-05
4,870 Estimating arbitrary subset sums with few probes 2005 PODS 6.3737999e-05
4,958 Similarity Join Size Estimation using Locality Sensitive Hashing 2011 VLDB 6.3394776e-05
5,427 xPAD: A Platform for Analytic Data Flows 2013 SIGMOD 6.1340137e-05
5,452 Early Hash Join: A Configurable Algorithm for the Efficient and Early Production of Join Results 2005 VLDB 6.1242445e-05
5,597 StatAdvisor: Recommending Statistical Views 2009 VLDB 6.0718206e-05
5,608 On Producing Join Results Early 2003 PODS 6.0692914e-05
5,609 Responsible Data Integration: Next-generation Challenges 2022 SIGMOD 6.0689501e-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.00076195956
36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00047863192
175 Simple Random Sampling from Relational Databases 1986 VLDB 0.00026784195
492 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00017408001
745 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00014288286
1,467 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00010567959
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 8,553 Sampling Big Ideas in Query Optimization 2023 PODS
2 9,634 Poisson Sampling over Acyclic Joins 2026 SIGMOD
3 8,279 Subset Sampling over Joins 2026 PODS
4 10,386 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,831 Joins on Samples: A Theoretical Guide for Practitioners 2020 VLDB
8 7,467 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