An array-based algorithm for simultaneous multidimensional aggregates

ABSTRACT

Computing multiple related group-bys and aggregates is one of the core operations of On-Line Analytical Processing (OLAP) applications. Recently, Gray et al. [GBLP95] proposed the “Cube” operator, which computes group-by aggregations over all possible subsets of the specified dimensions. The rapid acceptance of the importance of this operator has led to a variant of the Cube being proposed for the SQL standard. Several efficient algorithms for Relational OLAP (ROLAP) have been developed to compute the Cube. However, to our knowledge there is nothing in the literature on how to compute the Cube for Multidimensional OLAP (MOLAP) systems, which store their data in sparse arrays rather than in tables. In this paper, we present a MOLAP algorithm to compute the Cube, and compare it to a leading ROLAP algorithm. The comparison between the two is interesting, since although they are computing the same function, one is value-based (the ROLAP algorithm) whereas the other is position-based (the MOLAP algorithm). Our tests show that, given appropriate compression techniques, the MOLAP algorithm is significantly faster than the ROLAP algorithm. In fact, the difference is so pronounced that this MOLAP algorithm may be useful for ROLAP systems as well as MOLAP systems, since in many cases, instead of cubing a table directly, it is faster to first convert the table to an array, cube the array, then convert the result back to a table.

REFERENCES

• AADN96: Sameet Agarwal , Rakesh Agrawal , Prasad Deshpande , Ashish Gupta , Jeffrey F. Naughton , Raghu Ramakrishnan , Sunita Sarawagi, On the Computation of Multidimensional Aggregates, Proceedings of the 22th International Conference on Very Large Data Bases, p.506-521, September 03-06, 1996
• AS: Arbor Software. "The Role of the Multidimensional Database in a Data Warehousing Solution". White Paper, Arbor Software. http://www.arborsoft.com/papers/wareWOC.html
• CCS93: E.F. Codd, S.B. Codd, and C.T. Salley. "Providing OLAP (On-line Analytical Processing) to User-Analysts: An IT Mandate", White Paper, E.F. Codd and Associates. ht tp://w w w.arb orsoft .com/ papers / coddWO C. ht m 1
• DKOS84: 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
• GBLP95: J. Gray, A. Bosworth, A.Layman, and H.Pirahesh. "Data Cube: A relational aggregation operator generalizing group-by, cross-tabs and sub-totals. Technical Report MSR-TR-95-22, Microsoft Research, Advance Technology Division, Microsoft Corporation, Redmond, 1995.
• GC96: George Colliat, OLAP, relational, and multidimensional database systems, ACM SIGMOD Record, v.25 n.3, p.64-69, Sept. 1996 [doi>10.1145/234889.234901]
• IA: Information Advantage. "OLAP- Scaling to the Masses". White Paper, Information Advantage. http: / / www. infoad van .com /
• MC: Stanford Technology Group, Inc. "INFORMIX- MetaCube". Product Brochure. http://www.in formlx.com/in formix/products / new.plo / stgbroch / brochure.html
• MS: MicroStrategy Incorporated. "The Case For Relational OLAP". White Paper, MicroStrategy Incorporated. htt p: / / www.strategy.com / dwf/wp.b_al .html
• OC: Oracle Corporation. "Oracle OLAP Products". White Paper, Oracle Corporation. htt p: / / w w w.o racle, corn / prod ucts / collat rl/olapwp.p d f
• PSW: Pilot Software. "An Introduction to OLAP'. White Paper, Pilot Software. http://w ww. pilotsw .corn/r .an d_t/wht paper/olap/olap, htm
• RJ: Arbor Software Corporation, Robert J. Earle, U.S.Patent # 5359724
• SM94: Sunita Sarawagi , Michael Stonebraker, Efficient Organization of Large Multidimensional Arrays, Proceedings of the Tenth International Conference on Data Engineering, p.328-336, February 14-18, 1994
• Wel84: T.A. Welch. "A Technique for High-Performance Data Compression". IEEE Computer, 17(6), 1984.
• ZTN: Y.H. Zhao, K. Tufte, and J.F. Naughton. "On the Performance of an Array-Based ADT for OLAP Workloads". Technical Report CS-TR-96- 1313, University of Wisconsin-Madison, CS Department, May 1996.

INDEX TERMS

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

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  H. Information Systems
  H.2 DATABASE MANAGEMENT
  H.3 INFORMATION STORAGE AND RETRIEVAL

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Performance and usage measurement

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