Adaptive parallel aggregation algorithms

ABSTRACT

Aggregation and duplicate removal are common in SQL queries. However, in the parallel query processing literature, aggregate processing has received surprisingly little attention; furthermore, for each of the traditional parallel aggregation algorithms, there is a range of grouping selectivities where the algorithm performs poorly. In this work, we propose new algorithms that dynamically adapt, at query evaluation time, in response to observed grouping selectivities. Performance analysis via analytical modeling and an implementation on a workstation-cluster shows that the proposed algorithms are able to perform well for all grouping selectivities. Finally, we study the effect of data skew and show that for certain data sets the proposed algorithms can even outperform the best of traditional approaches.

REFERENCES

• BBDW83: Dina Bitton , Haran Boral , David J. DeWitt , W. Kevin Wilkinson, Parallel algorithms for the execution of relational database operations, ACM Transactions on Database Systems (TODS), v.8 n.3, p.324-353, Sept. 1983 [doi>10.1145/319989.319991]
• BCL93: Kurt P. Brown , Michael J. Carey , Miron Livny, Managing Memory to Meet Multiclass Workload Response Time Goals, Proceedings of the 19th International Conference on Very Large Data Bases, p.328-341, August 24-27, 1993
• BF93: J. Bunge and M. Fitzpatrick. Estimating the Number of Species: A Review. Journal of the Amemcan Statistical Association, 88(421), March 1993.
• DGS+90: D. J. Dewitt , S. Ghandeharizadeh , D. A. Schneider , A. Bricker , H. -I. Hsiao , R. Rasmussen, The Gamma Database Machine Project, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.44-62, March 1990 [doi>10.1109/69.50905]
• Eps79: R. Epstein. Techniques for Processing of Aggregates in Relational Database Systems. Memo UCB/ERL M79/8, E.R.L., College of Eng., Univ. of Calif., Berkeley, Feb. 1979.
• ER61: P. Erd5s and A. R~nyi. On a Classical Problem of Probability Theory. MTA Mat. Kut. Int. KSzl, 6A, 1961. Also in Selected Papers of A. Rfinyi, v. 2, Akademiai Kiado, Budapest.
• 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]
• Oak93: Oak Ridge National Lab. P VM 3 User's Guide and Reference Manual, May 1993.
• Ses92: S. Seshadri, Probabilistic methods in query processing, University of Wisconsin at Madison, Madison, WI, 1992
• SM82: Stanley Y. W. Su , Krishna P. Mikkilineni, Parallel Algorithms and Their Implementation in MICRONET, Proceedings of the 8th International Conference on Very Large Data Bases, p.310-324, September 08-10, 1982
• TPC94: TPC. TPC BenchmarkTM D (Decision Support). Working draft 6.5, Transaction Processing Performance Council, Feb. 1994.
• WDJ91: Christopher B. Walton , Alfred G. Dale , Roy M. Jenevein, A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins, Proceedings of the 17th International Conference on Very Large Data Bases, p.537-548, September 03-06, 1991

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Algorithms, Measurement, Performance