Ripple joins for online aggregation
Published 1 June 1999Open access
Peter J. Haas, Joseph M. Hellerstein
Citations169
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.
TL;DR
It is shown how ripple joins can be implemented in an existing DBMS using iterators, and an overview of the methods used to compute confidence intervals and to adaptively optimize the ripple join “aspect-ratio” parameters are given.
Abstract
We present a new family of join algorithms, called ripple joins, for online processing of multi-table aggregation queries in a relational database management system (DBMS). Such queries arise naturally in interactive exploratory decision-support applications.
Keywords
Computer Science
The Annals of Mathematical StatisticsA Class of Statistics with Asymptotically Normal Distribution
1,844 Citations1948Wassily Hoeffding
ACM Computing SurveysQuery evaluation techniques for large databases
1,260 Citations1993Goetz Graefe
This survey describes a wide array of practical query evaluation techniques for both relational and postrelational database systems, including iterative execution of complex query evaluation plans, the duality of sort- and hash-based set-matching algorithms, types of parallel query execution and their implementation, and special operators for emerging database application domains.
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.
Implementation techniques for main memory database systems
817 Citations1984David J. DeWitt, Randy H. Katz +4 more
This paper considers the changes necessary to permit a relational database system to take advantage of large amounts of main memory, and evaluates AVL vs B+-tree access methods, hash-based query processing strategies vs sort-merge, and study recovery issues when most or all of the database fits in main memory.
Probability and Measure
474 Citations2012Billingsley, Patrick
The American StatisticianAlgorithms for Computing the Sample Variance: Analysis and Recommendations
312 Citations1983Tony F. Chan, Gene H. Golub +1 more
A survey of possible algorithms and their round-off error bounds is presented, including some new analysis for computations with shifted data, and experimental results confirm these bounds and illustrate the dangers of some algorithms.
Orienteering in an information landscape
209 Citations1993Vicki L. O’Day, Robin Jeffries
The implications of the interconnected search pattern, triggers and stop conditions, common analysis techniques, and intermediary roles for the design of information access systems are discussed.
Statistical estimators for relational algebra expressions
144 Citations1988Wen‐Chi Hou, Gültekin Özsoyoğlu +1 more
This paper designs a sampling plan based on the cluster sampling method to improve the utilization of sampled data and to reduce the cost of sampling, and proposes consistent and unbiased estimators for arbitrary COUNT(E) type queries.
Journal of Computer and System SciencesSelectivity and Cost Estimation for Joins Based on Random Sampling
138 Citations1996Peter J. Haas, Jeffrey F. Naughton +2 more
A partial ordering that compares the variability of the estimators for the different procedures after an arbitrary fixed number of sampling steps and implies a partial ordering of the corresponding fixed-precision procedures with respect to sampling cost.
ACM SIGMOD RecordThe five-minute rule ten years later, and other computer storage rules of thumb
124 Citations1997Jim Gray, Goetz Graefe
Simple economic and performance arguments suggest appropriate lifetimes for main memory pages and suggest optimal page sizes, and motivate the importance of the new Kaps, Maps, Scans, and $/Kaps, $/Maps,$/TBscan metrics.
Large-sample and deterministic confidence intervals for online aggregation
110 Citations2002Peter J. Haas
It is shown how new and existing central limit theorems, simple bounding arguments, and the delta method can be used to derive formulas for both large sample and deterministic confidence intervals, which contain the final query result with probability 1.
Query execution techniques for caching expensive methods
97 Citations1996Joseph M. Hellerstein, Jeffrey F. Naughton
It is demonstrated that Hybrid Cache always dominates memoization, and significantly outperforms sorting in many instances, which provides new insights into the tradeoff between hashing and sorting for unary operations.
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.
Database and Expert Systems ApplicationsOn Estimating COUNT, SUM, and AVERAGE Relational Algebra Queries
23 Citations1991Gültekin Özsoyoğlu, K. Du +3 more
This paper extends earlier work on statistical estimators of CASE-DB with the following features: new statistical estimator for COUNT queries with projection, extending the methodology for SUM and AVERAGE aggregate queries, and new sampling plans based on systematic sampling and stratified sampling.