Heuristic optimization of OLAP queries in multidimensionally hierarchically clustered databases

On-Line Analytical Processing (OLAP) is a technology that encompasses applications requiring a multidimen-sional and hierarchical view of data. OLAP applica-tions often require fast response time to complex group-ing/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. How-ever, in many cases, multidimensional access methods outperform one-dimensional indexing methods. We present an architecture for multidimensional data-bases that are clustered with respect to multiple hi-erarchical dimensions. It is based on the star schema and is called CSB star. Then, we focus on heuristi-cally optimizing OLAP queries over this schema using multidimensional access methods. Users can still formu-late their queries over a traditional star schema, 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. 1