Heuristic optimization of OLAP queries in multidimensionally hierarchically clustered databases

ABSTRACT

On-line analytical processing (OLAP) is a technology that encompasses applications requiring a multidimensional and hierarchical view of data. OLAP applications often require fast response time to complex grouping/aggregation queries on enormous quantities of data. Commercial relational database management systems use mainly multiple one-dimensional indexes to process OLAP queries that restrict multiple dimensions. However, in many cases, multidimensional access methods outperform one-dimensional indexing methods.We present an architecture for multidimensional databases that are clustered with respect to multiple hierarchical dimensions. It is based on the star schema and is called CSB star. Then, we focus on heuristically optimizing OLAP queries over this schema using multidimensional access methods. Users can still formulate their queries over a traditional star scheme, which are then rewritten by the query processor over the CSB star. We exploit the different clustering features of the CSB star to efficiently process a class of typical OLAP queries. We detect special cases where the construction of an evaluation plan can be simplified and we discuss improvements of our technique.

REFERENCES

• 1: Rudolf Bayer, The Universal B-Tree for Multidimensional Indexing: general Concepts, Proceedings of the International Conference on Worldwide Computing and Its Applications, p.198-209, March 10-11, 1997
• 2: 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
• 3: Surajit Chaudhuri , Kyuseok Shim, Optimizing Queries with Aggregate Views, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.167-182, March 25-29, 1996
• 4: Divesh Srivastava , Shaul Dar , H. V. Jagadish , Alon Y. Levy, Answering Queries with Aggregation Using Views, Proceedings of the 22th International Conference on Very Large Data Bases, p.318-329, September 03-06, 1996
• 5: [5] K. Elhardt. EDITH query processing. Technical report, Transaction Software, Jan 2001.
• 6: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 7: 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
• 8: 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
• 9: [9] A. Gupta and I. S. Mumick. Maintenance of materialized views: Problems, techniques and applications. Data Engineering, 18(2):3-18, 1995.
• 10: 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
• 11: 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
• 12: [12] R. Kimball. The Data Warehouse Toolkit. John Wiley & Sons, 1996.
• 13: Yannis Kotidis , Nick Roussopoulos, DynaMat: a dynamic view management system for data warehouses, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.371-382, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 14: Volker Markl , Frank Ramsak , Rudolf Bayer, Improving OLAP Performance by Multidimensional Hierarchical Clustering, Proceedings of the 1999 International Symposium on Database Engineering & Applications, p.165, August 02-04, 1999
• 15: Processing Operations with Restrictions in RDBMS without External Sorting: The Tetris Algorithm, Proceedings of the 15th International Conference on Data Engineering, p.562, March 23-26, 1999
• 16: 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
• 17: Frank Ramsak , Volker Markl , Robert Fenk , Martin Zirkel , Klaus Elhardt , Rudolf Bayer, Integrating the UB-Tree into a Database System Kernel, Proceedings of the 26th International Conference on Very Large Data Bases, p.263-272, September 10-14, 2000
• 18: [18] S. Sarawagi. Indexing OLAP Data. Data Engineering, 20(1):36-43, 1997.
• 19: Dimitri Theodoratos , Timos K. Sellis, Data Warehouse Configuration, Proceedings of the 23rd International Conference on Very Large Data Bases, p.126-135, August 25-29, 1997
• 20: [20] D. Theodoratos and T. Sellis. Answering Queries on Cubes Using Other Cubes. In Proc. of the 23rd Intl. Conference on Scientific and Statistical Databases, pages 109-122, 2000.
• 21: [21] TPC benchmark D. Technical report, Transaction Processing Performance council, 1997.
• 22: Weipeng P. Yan , Per-Åke Larson, Performing Group-By before Join, Proceedings of the Tenth International Conference on Data Engineering, p.89-100, February 14-18, 1994
• 23: 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
• 24: Chendong Zou , Betty Salzberg , Rivka Ladin, Back to the Future: Dynamic Hierarchical Clustering, Proceedings of the Fourteenth International Conference on Data Engineering, p.578-587, February 23-27, 1998

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.6 Optimization

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Theory