Efficient multidimensional data aggregation operator implementation
First Claim
1. A computer readable medium containing computer executable instructions to perform a method for generating a data cube from a results set of a database query, said method comprising:
- identifying a roll-up string of attributes from said results set;
generating at least one aggregate from said roll-up string by way of a minimum union of roll-up operator calls based on a barrel shift of said roll-up string;
saving said at least one aggregate in said data cube; and
generating at least one super-aggregate from said at least one aggregate by way of a minimum number of aggregation function calls dictated by an aggregation function classification selected from a group of aggregation categories consisting of;
distributive, algebraic, and holistic.
5 Assignments
0 Petitions
Accused Products
Abstract
An efficient implementation of a multidimensional data aggregation operator that generates all aggregates and super-aggregates for all available values in a results set by first generating a minimal number of aggregates at the lowest possible system level using a minimal number of function calls, and second categorizing the aggregate function being applied and applying the aggregate function with the fewest possible function calls. The aggregates are generated from a union of roll-ups of the n attributes to the GROUP BY clause of the SELECT statement. The number of roll-ups are minimized by including a barrel shift of the attributes being rolled up. A scoreboard array of 2n bits is updated during the roll-up and barrel shifting process to keep track of which roll-ups are complete and with are not yet complete. Generating super-aggregates is further optimized by identifying the type of aggregate function being applied and facilitating the most efficient application of the aggregate function. A lter-- super() function is implemented to facilitate the most efficient application of algebraic aggregate functions that require access to intermediate aggregate data that heretofore was not available to any algebraic aggregation operator.
315 Citations
14 Claims
-
1. A computer readable medium containing computer executable instructions to perform a method for generating a data cube from a results set of a database query, said method comprising:
-
identifying a roll-up string of attributes from said results set; generating at least one aggregate from said roll-up string by way of a minimum union of roll-up operator calls based on a barrel shift of said roll-up string; saving said at least one aggregate in said data cube; and generating at least one super-aggregate from said at least one aggregate by way of a minimum number of aggregation function calls dictated by an aggregation function classification selected from a group of aggregation categories consisting of;
distributive, algebraic, and holistic. - View Dependent Claims (6)
-
-
2. A method according to claim I wherein said step of generating at least one aggregate includes:
-
executing a roll-up operation on said roll-up string; executing said barrel shift of said roll-up string; and executing a roll-up operation on said barrel shift of said roll-up string. - View Dependent Claims (3, 4, 5)
-
-
7. A computer readable medium containing computer executable instructions to perform a method for generating a data cube from a results set of a database query, said method comprising:
-
generating at least one aggregate from said results set by way of a minimum union of roll-up operator calls on a barrel shift of an attribute set; saving said at least one aggregate in said data cube; and categorizing an applicable aggregation function according to a group of aggregation categories consisting of;
distributive, algebraic, and holistic;assigning a handle to each value presently in said data cube that is subject to aggregation by an algebraic aggregation function; and generating at least one super-aggregate from said at least one sub-aggregate by way of a minimum number of aggregation function calls dictated by said aggregation function category. - View Dependent Claims (8, 9, 10, 11)
-
-
12. A computer readable medium containing computer executable instructions to perform a method comprising:
-
determine a minimum plurality of aggregate operations required for n attributes of an n-dimensional results set; executing said minimum plurality of aggregate operations in a manner comprising; executing an aggregate roll-up operation on said n attributes; repeatedly generating a unique barrel shift sub-set string of said n attributes and executing said aggregate roll-up operation on said unique barrel shift sub-set string until no unique barrel shift set string of said n attributes exists; tracking completed aggregations of said aggregate roll-up operation in a scoreboard array; examining said scoreboard array to verify that a complete set of aggregates exists; executing a roll-up operation on an attribute string associated with each unset entry in said scoreboard array; and generating at least one super-aggregate from said complete set of sub-aggregates dictated by at least one aggregate function selected from a group of aggregate function categories consisting of;
distributive, algebraic, and holistic. - View Dependent Claims (13, 14)
-
Specification