Database Paper Browser

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
3106
Venue
SIGMOD
Year
1999
Pagerank
0.00092569117
Overall Rank
18 | 99.88%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 86 citing papers.

Rank Citing Paper Year Venue Pagerank
3 Pig Latin: A Not-So-Foreign Language for Data Processing 2008 SIGMOD 0.0024217964
43 Models and Issues in Data Stream Systems 2002 PODS 0.00072660894
194 Query Processing, Resource Management, and Approximation in a Data Stream Management System 2003 CIDR 0.00035402379
264 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00029950264
341 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00026850764
430 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00023406426
736 Congressional Samples for Approximate Answering of Group-By Queries 2000 SIGMOD 0.00017414831
752 Deep Unsupervised Cardinality Estimation 2020 VLDB 0.00017138049
941 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015147831
1,018 Automatic Physical Database Tuning: A Relaxation-based Approach 2005 SIGMOD 0.00014626746
1,161 VerdictDB: Universalizing Approximate Query Processing 2018 SIGMOD 0.00013579831
1,207 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.0001327437
1,257 Dynamic Sample Selection for Approximate Query Processing 2003 SIGMOD 0.00013002384
1,268 Proactive Re-Optimization 2005 SIGMOD 0.00012914584
1,320 Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters 2016 SIGMOD 0.00012606067
1,331 ICICLES: Self-tuning Samples for Approximate Query Answering 2000 VLDB 0.00012553948
1,372 Random Sampling over Joins Revisited 2018 SIGMOD 0.0001233325
1,425 Scalable Approximate Query Processing With The DBO Engine 2007 SIGMOD 0.00012044433
1,574 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00011289028
1,712 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010786152
1,735 SciBORQ: Scientific data management with Bounds On Runtime and Quality 2011 CIDR 0.00010713691
2,035 Generating Example Data for Dataflow Programs 2009 SIGMOD 9.7131385e-05
2,113 When Can We Trust Progress Estimators for SQL Queries? 2005 SIGMOD 9.5207583e-05
2,167 Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation 2015 SIGMOD 9.3879598e-05
2,269 Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling 2005 VLDB 9.1507118e-05
2,494 DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models 2019 SIGMOD 8.6457436e-05
2,807 Optimal Sampling from Sliding Windows 2009 PODS 8.096649e-05
2,813 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD 8.0816314e-05
2,971 Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models 2017 VLDB 7.7935535e-05
2,995 A Sampling Algebra for Aggregate Estimation 2013 VLDB 7.7606324e-05
3,013 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD 7.7082045e-05
3,386 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 7.151562e-05
3,402 Query Optimizers: Time to Rethink the Contract? 2009 SIGMOD 7.134261e-05
3,557 Fast Manhattan Sketches in Data Streams 2010 PODS 6.9711051e-05
3,597 Graph-Based Synopses for Relational Selectivity Estimation 2006 SIGMOD 6.9337747e-05
3,955 Efficiently Approximating Selectivity Functions using Low Overhead Regression Models 2020 VLDB 6.5895015e-05
4,032 Spatial Online Sampling and Aggregation 2016 VLDB 6.5131946e-05
4,100 A Bi-Level Bernoulli Scheme for Database Sampling 2004 SIGMOD 6.4473679e-05
4,139 Memory-Limited Execution of Windowed Stream Joins 2004 VLDB 6.4126764e-05
4,244 A Disk-Based Join With Probabilistic Guarantees* 2005 SIGMOD 6.3228453e-05
4,432 Sampling Dirty Data for Matching Attributes 2010 SIGMOD 6.1858589e-05
4,926 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 5.8184457e-05
4,961 Estimating arbitrary subset sums with few probes 2005 PODS 5.7992561e-05
5,048 xPAD: A Platform for Analytic Data Flows 2013 SIGMOD 5.7285145e-05
5,128 Efficient Join Synopsis Maintenance for Data Warehouse 2020 SIGMOD 5.6728511e-05
5,222 Similarity Join Size Estimation using Locality Sensitive Hashing 2011 VLDB 5.6180462e-05
5,405 ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads 2024 VLDB 5.5243727e-05
5,523 On Producing Join Results Early 2003 PODS 5.4648346e-05
5,547 Supporting Time-Constrained SQL Queries in Oracle 2007 VLDB 5.4452585e-05
5,657 FluxQuery: An Execution Framework for Highly Interactive Query Workloads 2016 SIGMOD 5.3873634e-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
14 Online Aggregation 1997 SIGMOD 0.0010813443
28 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00080571183
46 Simple Random Sampling from Relational Databases 1986 VLDB 0.00071588702
291 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00028778973
553 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00020272747
803 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00016438972
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,254 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00013018797
4,926 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 5.8184457e-05
4,689 Scalable Reservoir Sampling on Many-Core CPUs 2019 SIGMOD 5.9899401e-05
8,467 Sampling Big Ideas in Query Optimization 2023 PODS 4.4995247e-05
2,254 Two-Level Sampling for Join Size Estimation 2017 SIGMOD 9.1871115e-05
92 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00051431888
6,481 Joins on Samples: A Theoretical Guide for Practitioners 2020 VLDB 5.039683e-05
8,964 Reservoir Sampling over Joins 2024 SIGMOD 4.4163852e-05
1,372 Random Sampling over Joins Revisited 2018 SIGMOD 0.0001233325
46 Simple Random Sampling from Relational Databases 1986 VLDB 0.00071588702