Exploiting hierarchical clustering in evaluating multidimensional aggregation queries

ABSTRACT

Multidimensional aggregation queries constitute the single most important class of queries for data warehousing applications and decision support systems. The bottleneck in the evaluation of these queries is the join of the usually huge fact table with the restricted dimension tables (star-join). Recently, a multidimensional hierarchical clustering schema for star schemas is suggested. Subsequently, query evaluation plans for multidimensional queries appeared that essentially implement a star join as a multidimensional range restriction.We present a number of transformations for such plans. The transformations place grouping/aggregation operations before joins and safely prune aggregated tuples. They can be applied at no or minimal extra I/O cost. We show how these transformations can be used to construct a new evaluation plan for grouping/aggregation queries over multidimensional hierarchically clustered schemas. The new plan improves previous results by grouping and aggregating tuples and by excluding aggregated tuples from further consideration at an early stage of the computation of a query.

REFERENCES

• 1: Chee-Yong Chan , Yannis E. Ioannidis, Bitmap index design and evaluation, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.355-366, June 01-04, 1998, Seattle, Washington, United States
• 2: Surajit Chaudhuri , Umeshwar Dayal, An overview of data warehousing and OLAP technology, ACM SIGMOD Record, v.26 n.1, p.65-74, March 1997 [doi>10.1145/248603.248616]
• 3: 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
• 4: 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
• 5: 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]
• 6: 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
• 7: 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
• 8: N. Karayannidis, A. Tsois, T. K. Sellis, R. Pieringer, V.Markl, F. Ramsak, R. Fenk, K. Elhardt, and R. Bayer. Processing Star Queries on Hierarchically-Clustered Fact Tables. In Proc. of the 28th VLDB Conf., 2002.
• 9: R. Kimball. The Data Warehouse Toolkit. John Wiley & Sons, 1996.
• 10: 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
• 11: 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
• 12: Patrick O'Neil , Goetz Graefe, Multi-table joins through bitmapped join indices, ACM SIGMOD Record, v.24 n.3, p.8-11, Sept. 1995 [doi>10.1145/211990.212001]
• 13: 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
• 14: S. Sarawagi. Indexing OLAP Data. Data Engineering, 20(1):36--43, 1997.
• 15: Dimitri Theodoratos , Aris Tsois, Heuristic optimization of OLAP queries in multidimensionally hierarchically clustered databases, Proceedings of the 4th ACM international workshop on Data warehousing and OLAP, p.48-55, November 09-09, 2001, Atlanta, Georgia, USA [doi>10.1145/512236.512243]
• 16: A. Tsois and T. Sellis. The Generalized Pre-Grouping Transformation: Aggregate-Query Optimization in the Presence of Dependencies. In Proc. of the 29th Intl. Conf. on Very Large Data Bases, 2003.
• 17: 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
• 18: 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
• 19: 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

General Terms:
Algorithms, Performance

Keywords:
multidimensional aggregation query, multidimensional hierarchical clustering, query transformations, star join