On random sampling over joins
ACM SIGMOD RecordPublished 1 June 1999Open access
Surajit Chaudhuri, Rajeev Motwani, Vivek Narasayya
Citations303
SJR quartileQ2
SJR score0.69
SNIP0.92
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
A major bottleneck in implementing sampling as a primitive relational operation is the inefficiency of sampling the output of a query. It is not even known whether it is possible to generate a sample of a join tree without first evaluating the join tree completely. We undertake a detailed study of this problem and attempt to analyze it in a variety of settings. We present theoretical results explaining the difficulty of this problem and setting limits on the efficiency that can be achieved. Based on new insights into the interaction between join and sampling, we develop join sampling techniques for the settings where our negative results do not apply. Our new sampling algorithms are significantly more efficient than those known earlier. We present experimental evaluation of our techniques on Microsoft's SQL Server 7.0.
Keywords
Computer ScienceDecision Sciences
Cambridge University Press eBooksRandomized Algorithms
4,069 Citations1995Rajeev Motwani, Prabhakar Raghavan
ACM Transactions on Mathematical SoftwareRandom sampling with a reservoir
1,759 Citations1985Jeffrey Scott Vitter
Theoretical and empirical results indicate that Algorithm Z outperforms current methods by a significant margin, and an efficient Pascal-like implementation is given that incorporates these modifications and that is suitable for general use.
Online aggregation
923 Citations1997Joseph M. Hellerstein, Peter J. Haas +1 more
A new online aggregation interface is proposed that permits users to both observe the progress of their aggregation queries and control execution on the fly, and a suite of techniques that extend a database system to meet these requirements are presented.
Accurate estimation of the number of tuples satisfying a condition
342 Citations1984Gregory Piatetsky-Shapiro, Charles W. Connell
A new method for estimating the number of tuples satisfying a condition of the type attribute rel constant, where rel is one of "=", ">", "<, "≥", "≤" , which gives highly accurate, yet easy to compute, estimates.
Random sampling for histogram construction
236 Citations1998Surajit Chaudhuri, Rajeev Motwani +1 more
A conservative error metric is introduced capturing the intuition that for an approximate histogram to have low error, the error must be small in all regions of the histogram and an optimal bound on the amount of sampling required for pre-specified error bounds is presented.
eScholarship (California Digital Library)Simple Random Sampling from Relational Databases
156 Citations1986Frank Olken, Doron Rotem
Sampling as a fundamental operation for the auditing and statistical analysis of large databases is discussed and how samples of relational queries can often be computed for a small fraction of the effort of computing the entire relational query is shown.
Bifocal sampling for skew-resistant join size estimation
97 Citations1996Šumit Ganguly, Phillip B. Gibbons +2 more
The estimate obtained by the bifocal sampling algorithm is proven to lie with high probability within a small constant factor of the actual join size, regardless of the skew, as long as the join size is Ω(n lg n), for relations consisting of n tuples.
Theoretical Computer ScienceEfficient sampling strategies for relational database operations
96 Citations1993Richard J. Lipton, Jeffrey F. Naughton +2 more
The proposed adaptive, random-sampling algorithm for general query size estimation in databases is investigated as applied to the relational database operations select, project, and join to provide significantly improved bounds on the amount of sampling necessary for a given level of accuracy.
On the relative cost of sampling for join selectivity estimation
63 Citations1994Peter J. Haas, Jeffrey F. Naughton +1 more
The cost of estimating the selectivity of a “star join” using sampling procedure t-cross is compared to the cost of simply computing the join and obtaining the exact answer and bounds and approximations for the relative cost of sampling are shown.
Lecture notes in computer scienceOn estimating the size of projections
35 Citations1990Jeffrey F. Naughton, S. Seshadri
A new sampling algorithm for estimating the number of tuples in the projection of a relation that requires no assumptions about the distributions of values in the attributes of the relation and converges faster and smoother than previous sampling algorithms for the problem.
Sampling from spatial databases
34 Citations2002Frank Olken, Doron Rotem
This paper deals with techniques for obtaining random point samples from spatial databases by discussing two fundamental approaches to sampling with spatial predicates, depending on whether the authors sample first or evaluate the predicate first.