CubiST(++): A new approach to improving the performance of ad-hoc cube queries

We provide a new approach to speeding up the evaluation of cube queries, an important class of OLAP queries which return aggregated values rather than sets of tuples. Our new algorithm called CubiST (Cubing with Statistics Trees) represents a drastic departure from existing approaches in that it does not use the familiar view lattice approach to compute and materialize new views from existing views. Instead, CubiST computes and stores all possible aggregate views in the leaves of a statistics tree during a one-time scan of the detailed data. To be able to handle queries that involve dimension hierarchies, we have developed an improved version of CubiST called CubiST++ which uses a family of trees instead of a single statistics tree. CubiST ++ applies a greedy strategy to select a family of candidate trees which represent superviews for the different hierarchy levels of the dimensions. In addition, we have developed an algorithm to compute and materialize the candidate trees that make up the family starting from a single statistics tree (base tree). Given an input query, our new query evaluation algorithm selects the smallest tree in the family which can answer the query. CubiST ++ significantly reduced I/O time and improved in-memory performance when compared with CubiST.; For cube queries that contain holistic operations e.g. median, top N, etc., we have reduced the 1-dimensional holistic cubing to quantiling and selection problems. To implement holistic operations efficiently, we have developed two new algorithms, namely, deterministic bucketing (DB) and random bucketing (RB).; Experimental evaluations of our CubiST++ prototype implementation have demonstrated its superior run-time performance and scalability when compared to existing OLAP systems.