Ripple joins for online aggregation

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 on-line 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 DBMS, 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

• AS72: Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
• Bil86: P. Billingsley. Probability and Measure. Wiley, New York, 1986.
• CGL83: T. F. Chan, G. H. Golub, and R. J. LeVeque. Algorithms for computing She sample variance: Analysis and recommendation. Amer. Statist., 37:242-247, 1983.
• DKO+84: David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• GG97: Jim Gray , Goetz Graefe, The five-minute rule ten years later, and other computer storage rules of thumb, ACM SIGMOD Record, v.26 n.4, p.63-68, Dec. 1997 [doi>10.1145/271074.271094]
• Gra93: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• Haa97: Peter J. Haas, Large-Sample and Deterministic Confidence Intervals for Online Aggregation, Proceedings of the Ninth International Conference on Scientific and Statistical Database Management, p.51-63, August 11-13, 1997 [doi>10.1109/SSDM.1997.621151]
• HAR99: J. M. Hellerstein, R. Avnur, and V. Raman. informix under CONTROL: Online query processing. Submitted for publication, 1999.
• HH98: P. J. Haas and J. M. Hellerstein. Join algorithms for online aggregation. IBM Research Report RJ 10126, IBM Almaden Research Center, San Jose, CA, 1998.
• HHW97: Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
• HN96: Joseph M. Hellerstein , Jeffrey F. Naughton, Query execution techniques for caching expensive methods, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.423-434, June 04-06, 1996, Montreal, Quebec, Canada
• HNS94: Peter J. Haas , Jeffrey F. Naughton , Arun N. Swami, On the relative cost of sampling for join selectivity estimation, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.14-24, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182594]
• HNSS96: Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Arun N. Swami, Selectivity and cost estimation for joins based on random sampling, Journal of Computer and System Sciences, v.52 n.3, p.550-569, June 1996 [doi>10.1006/jcss.1996.0041]
• Hoe48: W. Hoeffding. A class of statistics with asymptotically normal distribution. Ann. Math. Statist., 19:293-325, 1948.
• HOT88: Wen-Chi Hou , Gultekin Ozsoyoglu , Baldeo K. Taneja, Statistical estimators for relational algebra expressions, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.276-287, March 1988, Austin, Texas, United States [doi>10.1145/308386.308455]
• HOT89: Wen-Chi Hou , Gultekin Ozsoyoglu , Baldeo K. Taneja, Processing aggregate relational queries with hard time constraints, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.68-77, June 1989, Portland, Oregon, United States
• IBM97: IBM Corporation. IBM DB2 Universal Database Administration Guide, Version 5. North York, Ontario, Canada, 1997.
• Inf97: Informix Corporation. Informix Universal Server G~ide to SQL: Syntax, Version 9.01. Menlo Park, CA, March 1997.
• ODT+91: G. Ozsoyoglu, K. Du, A. Tjahjana, W. Hou, and D. Y. Rowland. On estimating COUNT, SUM, and AVERAGE relational algebra queries. In D. Dimitris Karagiannis, editor, Database and Expert Systems Applications, Proceedings of the International Conference in Berlin, Germany, 1991 (DEXA 91), pages 406-412. Springer-Verlag, 1991.
• OJ93: Vicki L. O'Day , Robin Jeffries, Orienteering in an information landscape: how information seekers get from here to there, Proceedings of the SIGCHI conference on Human factors in computing systems, p.438-445, April 24-29, 1993, Amsterdam, The Netherlands [doi>10.1145/169059.169365]
• Olk93: F. Olken. Random Sampling .from Databases. Ph.D. Dissertation, University of California, Berkeley, CA, 1993. Available as Tech. Report LBL-32883, Lawrence Berkeley Laboratories, Berkeley, CA.
• Ora97: Oracle Corporation. Oracle8 Server SQL Reference, Release 8.0. Redwood Shores, CA, June 1997.
• Pos98: PostgreSQL Home Page, 1998. http://www.postgre,aql .org.
• RRH99: Vijayshankar Raman , Bhaskaran Raman , Joseph M. Hellerstein, Online Dynamic Reordering for Interactive Data Processing, University of California at Berkeley, Berkeley, CA, 1999
• RSS94: R. Ramakrishnan , D. Srivastava , S. Sudarshan, Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs, IEEE Transactions on Knowledge and Data Engineering, v.6 n.4, p.501-517, August 1994 [doi>10.1109/69.298169]
• WA91: Annita N. Wilschut , Peter M. G. Apers, Dataflow query execution in a parallel main-memory environment, Proceedings of the first international conference on Parallel and distributed information systems, p.68-77, December 1991, Miami, Florida, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Design, Management, Measurement, Performance, Theory