A Partial Pre-aggregation Scheme for HOLAP Engines

摘要

This paper describes a scheme for partial pre-aggregation to speed up the response time of queries that are posed for the array-like interface, subject to the constraint that all pre-computed aggregates must fit into storage of a predetermined size. The target query workload consists of all base and aggregate cells that are stored in a multidimensional array (i.e. cube). These queries are actually range queries pre-defined by users. Due to the huge size of all possible aggregate cells, the emphasis of our scheme is to reduce the overhead for query compilation. An efficient and effective query decomposition method is devised, which works well with a pre-aggregation scheme whereby pre-computed aggregates form a sub-cube of the full cube. A greedy algorithm is devised is to derive such a sub-cube. A HOLAP engine which implements this partial pre-aggregation scheme is described. Experimental results using both synthetic and real-life datasets are presented to demonstrate that the partial pre-aggregation scheme is viable, and for some complex queries, accelerates query execution by close to 300 times.