Range queries in OLAP data cubes

ABSTRACT

A range query applies an aggregation operation over all selected cells of an OLAP data cube where the selection is specified by providing ranges of values for numeric dimensions. We present fast algorithms for range queries for two types of aggregation operations: SUM and MAX. These two operations cover techniques required for most popular aggregation operations, such as those supported by SQL. For range-sum queries, the essential idea is to precompute some auxiliary information (prefix sums) that is used to answer ad hoc queries at run-time. By maintaining auxiliary information which is of the same size as the data cube, all range queries for a given cube can be answered in constant time, irrespective of the size of the sub-cube circumscribed by a query. Alternatively, one can keep auxiliary information which is 1/bd of the size of the d-dimensional data cube. Response to a range query may now require access to some cells of the data cube in addition to the access to the auxiliary information, but the overall time complexity is typically reduced significantly. We also discuss how the precomputed information is incrementally updated by batching updates to the data cube. Finally, we present algorithms for choosing the subset of the data cube dimensions for which the auxiliary information is computed and the blocking factor to use for each such subset. Our approach to answering range-max queries is based on precomputed max over balanced hierarchical tree structures. We use a branch-and-bound-like procedure to speed up the finding of max in a region. We also show that with a branch-and-bound procedure, the average-case complexity is much smaller than the worst-case complexity.

REFERENCES

• AAD+96: 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
• AGS97: Rakesh Agrawal , Ashish Gupta , Sunita Sarawagi, Modeling Multidimensional Databases, Proceedings of the Thirteenth International Conference on Data Engineering, p.232-243, April 07-11, 1997
• Ben80: Jon Louis Bentley, Multidimensional divide-and-conquer, Communications of the ACM, v.23 n.4, p.214-229, April 1980 [doi>10.1145/358841.358850]
• BF79: Jon Louis Bentley , Jerome H. Friedman, Data Structures for Range Searching, ACM Computing Surveys (CSUR), v.11 n.4, p.397-409, Dec. 1979 [doi>10.1145/356789.356797]
• BKSS90: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• BR91: M. Berger and I. Regoutsos. An algorithm point clustering and grid generation. IEEE Transactions on Systems, Man and Cybernetics, 21(5):1278-86, 1991.
• Cha90: Bernard Chazelle, Lower bounds for orthogonal range searching: part II. The arithmetic model, Journal of the ACM (JACM), v.37 n.3, p.439-463, July 1990 [doi>10.1145/79147.79149]
• CLS86: G.D. Cohen, A.C. Lobstein, and N.j.A. Sloane. b-k~her results on the covering radius of codes. IEJEB Trans. Information Theory, IT-32(5):680- 694, September 1986.
• CM89: M. C. Chen , L. P. McNamee, On the Data Model and Access Method of Summary Data Management, IEEE Transactions on Knowledge and Data Engineering, v.1 n.4, p.519-529, December 1989 [doi>10.1109/69.43426]
• Cod93: E.F. Codd. Providing OLAP (on-line analytical processing) to user-analysts: An IT mandate. Technical report, E. F. Codd and Associates, 1993.
• Col96: 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]
• Com79: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• CR89: B. Chazelle , B. Rosenberg, Computing partial sums in multidimensional arrays, Proceedings of the fifth annual symposium on Computational geometry, p.131-139, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73848]
• CS94: Surajit Chaudhuri , Kyuseok Shim, Including Group-By in Query Optimization, Proceedings of the 20th International Conference on Very Large Data Bases, p.354-366, September 12-15, 1994
• GBLP96: Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total, Proceedings of the Twelfth International Conference on Data Engineering, p.152-159, February 26-March 01, 1996
• GHQ95: Ashish Gupta , Venky Harinarayan , Dallan Quass, Aggregate-Query Processing in Data Warehousing Environments, Proceedings of the 21th International Conference on Very Large Data Bases, p.358-369, September 11-15, 1995
• GHRU97: Himanshu Gupta , Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Index Selection for OLAP, Proceedings of the Thirteenth International Conference on Data Engineering, p.208-219, April 07-11, 1997
• HBA97: Ching-Tien Ho , Jehoshua Bruck , Rakesh Agrawal, Partial-sum queries in OLAP data cubes using covering codes, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.228-237, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263686]
• HRU96: Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.205-216, June 04-06, 1996, Montreal, Quebec, Canada
• IBM95: IBM. DB~ SQL Reference }or Common Servers Version ~, 1995.
• JD88: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• JS96: T. Johnson and D. Shasha. Hierarchically sprit cube forests for decision support: description and tuned design, 1996. Working Paper.
• Lom95: D. Lomet, editor. Special Issue on Materialized Views and Data Warehousing. IEEE Data Engineering Bulletin, 18(2), June 1995.
• Meh84: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• Mic92: Zbigniew Michalewicz, Statistical and scientific databases, Ellis Horwood, Upper Saddle River, NJ, 1991
• Mit70: L. Mitten. Branch and bound methods: General formulation and properties. Operations Research, 18:24-34, 1970.
• OLA96: The CLAP Council. MD-API the OLAP Applzcation Program Interface Version 0.5 Specification, September 1996.
• RND77: E.M. Reingold, J. Nievergelt, and N. Dec. Combinatorial Algorithms. Prentice-Hall, Englewood Cliffs. N J, 1977.
• Sam89: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• SAM96: John C. Shafer , Rakesh Agrawal , Manish Mehta, SPRINT: A Scalable Parallel Classifier for Data Mining, Proceedings of the 22th International Conference on Very Large Data Bases, p.544-555, September 03-06, 1996
• SB95: P. Schroeter and j. Bigun. Hierarchical image segmentation by multi-dimensional clustering and orientation-adaptive boundary refinement. Pattern Recognition, 25(5):695-709, May 1995.
• SDNR96: Amit Shukla , Prasad Deshpande , Jeffrey F. Naughton , Karthikeyan Ramasamy, Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies, Proceedings of the 22th International Conference on Very Large Data Bases, p.522-531, September 03-06, 1996
• SR96: B. Salzberg and A. Reuter. Indexing for aggregation, 1996. Working Paper.
• STL89: J. Srivastava , J. S. E. Tan , V. Y. Lum, TBSAM: An Access Method for Efficient Processing of Statistical Queries, IEEE Transactions on Knowledge and Data Engineering, v.1 n.4, p.414-423, December 1989 [doi>10.1109/69.43417]
• Vai85: P M Vaidya, Space-time tradeoffs for orthogonal range queries, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.169-174, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22164]
• WL85: Dan E. Willard , George S. Lueker, Adding range restriction capability to dynamic data structures, Journal of the ACM (JACM), v.32 n.3, p.597-617, July 1985 [doi>10.1145/3828.3839]
• Yao85: Andrew Yao. On the complexity of maintaining partial sums. SIAM J. Computing, 14(2):277- 288, May 1985.
• YL95: Weipeng P. Yan , Per-Åke Larson, Eager Aggregation and Lazy Aggregation, Proceedings of the 21th International Conference on Very Large Data Bases, p.345-357, September 11-15, 1995

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
  H.3 INFORMATION STORAGE AND RETRIEVAL

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

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