Simultaneous optimization and evaluation of multiple dimensional queries

ABSTRACT

Database researchers have made significant progress on several research issues related to multidimensional data analysis, including the development of fast cubing algorithms, efficient schemes for creating and maintaining precomputed group-bys, and the design of efficient storage structures for multidimensional data. However, to date there has been little or no work on multidimensional query optimization. Recently, Microsoft has proposed “OLE DB for OLAP” as a standard multidimensional interface for databases. OLE DB for OLAP defines Multi-Dimensional Expressions (MDX), which have the interesting and challenging feature of allowing clients to ask several related dimensional queries in a single MDX expression. In this paper, we present three algorithms to optimize multiple related dimensional queries. Two of the algorithms focus on how to generate a global plan from several related local plans. The third algorithm focuses on generating a good global plan without first generating local plans. We also present three new query evaluation primitives that allow related query plans to share portions of their evaluation. Our initial performance results suggest that the exploitation of common subtask evaluation and global optimization can yield substantial performance improvements when relational database systems are used as data sources for multidimensional analysis.

REFERENCES

• 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
• CR96: Damianos Chatziantoniou , Kenneth A. Ross, Querying Multiple Features of Groups in Relational Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.295-306, September 03-06, 1996
• DKLPY94: David J. DeWitt , Navin Kabra , Jun Luo , Jignesh M. Patel , Jie-Bing Yu, Client-Server Paradise, Proceedings of the 20th International Conference on Very Large Data Bases, p.558-569, September 12-15, 1994
• 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
• 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
• MS: Microsoft Corporated. "OLE DB for OLAP Design Specification- Beta 2". http://www, mlcrosoft, corn / data/ oledb / olap / pro dinfo, ht ml
• OQ97: Patrick O'Neil , Dallan Quass, Improved query performance with variant indexes, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.38-49, May 11-15, 1997, Tucson, Arizona, United States
• PS88: Jooseok Park , Arie Segev, Using Common Subexpressions to Optimize Multiple Queries, Proceedings of the Fourth International Conference on Data Engineering, p.311-319, February 01-05, 1988
• S88: Timos K. Sellis, Multiple-query optimization, ACM Transactions on Database Systems (TODS), v.13 n.1, p.23-52, March 1988 [doi>10.1145/42201.42203]
• SS94: Kyuseok Shim , Timos Sellis , Dana Nau, Improvements on a heuristic algorithm for multiple-query optimization, Data & Knowledge Engineering, v.12 n.2, p.197-222, March 1994 [doi>10.1016/0169-023X(94)90014-0]
• 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
• Su96: Prakash Sundaresan, Data warehousing features in Informix OnLine XPS, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.288, December 18-20, 1996, Miami Beach, Florida, United States
• 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
• ZTN96: 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
      H.2.7 Database Administration
          Subjects: Data warehouse and repository

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

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

General Terms:
Algorithms, Measurement