Fast Rollup on Recursive Hierarchy in OLAP

Rollup, a key operation in OLAP queries, is to aggregate multidimensional data on dimensional hierarchies. While the operation can be efficiently implemented on regular hierarchies in data warehouse, its application to recursive hierarchies proved to be problematic. Due to the stratification restriction, aggregate is not permitted to be wrapped within SQL recursion. Representing rollup operations on recursive hierarchies as SQL recursive queries will cause considerable overhead and is thus inefficient. This paper proposes an iteration-based evaluation strategy that aims to solve this inefficiency problem in OLAP queries. In our solution, aggregation on recursive hierarchies is modeled as a binary operator tree that is stored in its postfix notation and executed by a push down stack. We also demonstrate how to seamlessly embed this novel strategy into data warehouse that is based on ORDBMS. Experiment results show that our proposed solution is quite efficient compared with the SQL recursive evaluation strategy