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)
Incoming Non-self Citations Over Time
Authors
- 1. Surajit Chaudhuri (Microsoft)
- 2. Rajeev Motwani (Stanford University)
- 3. Vivek Narasayya (Microsoft)
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 40 of 90 citing papers.
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 |