Digital Symposium Collection 2000  

 
 
 
 
 
 

 



















Ripple Joins for Online Aggregation

Peter J. Haas and Joseph M. Hellerstein

  View Paper (PDF)  

Return to Adaptive Query Optimization

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. Traditional offline join algorithms are designed to minimize the time to completion of the query. In contrast, ripple joins are designed to minimize the time until an acceptably precise estimate of the query result is available, as measured by the length of a confidence interval. Ripple joins are adaptive, adjusting their behavior during processing in accordance with the statistical properties of the data. Ripple joins also permit the user to dynamically trade off the two key performance factors of online aggregation: the time between successive updates of the running aggregate, and the amount by which the confidence-interval length decreases at each update. We show how ripple joins can be implemented in an existing dbms using iterators, and we give an overview of the methods used to compute confidence intervals and to adaptively optimize the ripple join "aspect-ratio" parameters. In experiments with an initial implementation of our algorithms in the POSTGRES DMBS , the time required to produce reasonably precise online estimates was up to two orders of magnitude smaller than the time required for the best offline join algorithms to produce exact answers.


References

Note: References link to DBLP on the Web.

[AS72]
...
[Bil86]
...
[CGL83]
...
[DKO+84]
David J. DeWitt , Randy H. Katz , Frank Olken , Leonard D. Shapiro , Michael Stonebraker , David A. Wood : Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984 : 1-8
[GG97]
Jim Gray , Goetz Graefe : The Five-Minute Rule Ten Years Later, and Other Computer Storage Rules of Thumb. SIGMOD Record 26(4) : 63-68(1997)
[Gra93]
Goetz Graefe : Query Evaluation Techniques for Large Databases. Computing Surveys 25(2) : 73-170(1993)
[Haa97]
Peter J. Haas : Large-Sample and Deterministic Confidence Intervals for Online Aggregation. SSDBM 1997 : 51-63
[HAR99]
...
[HH98]
...
[HHW97]
Joseph M. Hellerstein , Peter J. Haas , Helen Wang : Online Aggregation. SIGMOD Conference 1997 : 171-182
[HN96]
Joseph M. Hellerstein , Jeffrey F. Naughton : Query Execution Techniques for Caching Expensive Methods. SIGMOD Conf. 1996 : 423-434
[HNS94]
Peter J. Haas , Jeffrey F. Naughton , Arun N. Swami : On the Relative Cost of Sampling for Join Selectivity Estimation. PODS 1994 : 14-24
[HNSS96]
Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Arun N. Swami : Selectivity and Cost Estimation for Joins Based on Random Sampling. JCSS 52(3) : 550-569(1996)
[Hoe48]
...
[HOT88]
Wen-Chi Hou , Gultekin Özsoyoglu , Baldeo K. Taneja : Statistical Estimators for Relational Algebra Expressions. PODS 1988 : 276-287
[HOT89]
Wen-Chi Hou , Gultekin Özsoyoglu , Baldeo K. Taneja : Processing Aggregate Relational Queries with Hard Time Constraints. SIGMOD Conference 1989 : 68-77
[IBM97]
...
[Inf97]
...
[ODT+91]
Gultekin Özsoyoglu , Kaizheng Du , A. Tjahjana , Wen-Chi Hou , D. Y. Rowland : On Estimating COUNT, SUM, and AVERAGE. DEXA 1991 : 406-412
[OJ93]
...
[Olk93]
...
[Ora97]
...
[Pos98]
...
[RRH99]
...
[RSS94]
Raghu Ramakrishnan , Divesh Srivastava , S. Sudarshan : Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs. TKDE 6(4) : 501-517(1994)
[WA91]
Annita N. Wilschut , Peter M. G. Apers : Dataflow Query Execution in a Parallel Main-Memory Environment. PDIS 1991 : 68-77

Referenced by

  1. Kian-Lee Tan , Cheng Hian Goh , Beng Chin Ooi : Online Feedback for Nested Aggregate Queries with Multi-Threading. VLDB 1999 : 18-29
  2. Vijayshankar Raman , Bhaskaran Raman , Joseph M. Hellerstein : Online Dynamic Reordering for Interactive Data Processing. VLDB 1999 : 709-720
  3. Peter J. Haas : Techniques for Online Exploration of Large Object-Relational Datasets. SSDBM 1999 : 4-12
  4. Noga Alon , Phillip B. Gibbons , Yossi Matias , Mario Szegedy : Tracking Join and Self-Join Sizes in Limited Storage. PODS 1999 : 10-20

BIBTEX

@inproceedings{DBLP:conf/sigmod/HaasH99,
  author    = {Peter J. Haas and
                Joseph M. Hellerstein},
   editor    = {Alex Delis and
                Christos Faloutsos and
                Shahram Ghandeharizadeh},
   title     = {Ripple Joins for Online Aggregation},
   booktitle = {SIGMOD 1999, Proceedings ACM SIGMOD International Conference
                on Management of Data, June 1-3, 1999, Philadephia, Pennsylvania,
                USA},
   publisher = {ACM Press},
   year      = {1999},
   isbn      = {1-58113-084-8},
   pages     = {287-298},
   crossref  = {DBLP:conf/sigmod/99},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


























Copyright(C) 2000 ACM