Method and system for efficiently performing database table aggregation using an aggregation index

Claim 1

A method in a computer database system for aggregating a source table comprised of rows, each row having associated with it an aggregated value and a grouping value, the source table further having a grouping index on the grouping value of the rows of the source table and an aggregation index on the aggregated value of the rows of the source table, the method comprising the steps of: creating a set of bitmaps mapping from row to grouping value from the grouping index; using the aggregation index to identify the aggregated value of each row of the source table; using information derived from the grouping index to identify the grouping value of each row of the source table by using the bitmaps to identify the grouping value of each row of the source table; and for each row of the source table, aggregating the identified aggregated value into a result value for the identified grouping value.

Claim 2

A method in a computer database system for aggregating a source table comprised of rows, each row having associated with it an aggregated value and a grouping value, the source table further having a grouping index on the grouping value of the rows of the source table and an aggregation index on the aggregated value of the rows of the source table, the method comprising the steps of: creating a set of bitmaps mapping from row to grouping value from the grouping index; using the aggregation index to identify the aggregated value of each row of the source table; using information derived from the grouping index to identify the grouping value of each row of the source table by using the bitmaps to identify the grouping value of each row of the source table; and for each row of the source table, aggregating the identified aggregated value into a result value for the identified grouping value.

Claim 4

A method in a computer database system for aggregating a source table comprised of rows, each row having an aggregated value, a first grouping value, and a second grouping value, the method comprising the steps of: maintaining a grouping index mapping from each unique permutation of the first grouping value and the second grouping value among the rows to the rows having that permutation of the first grouping value and the second grouping value; maintaining an aggregation index on the rows; using the aggregation index to identify the aggregated value of each row of the source table; using the grouping index to identify the permutation of the first grouping value and the second grouping value for each row of the source table; for each row, aggregating the identified aggregated value into a result value for the identified permutation of the first grouping value and the second grouping value; using the grouping index to identify the first grouping value of each row of the source table; and for each row, aggregating the identified aggregated value into a result value for the identified first grouping value.

Claim 5

A method in a computer database system for aggregating a source table comprised of rows, each row having an aggregated value, a first grouping value, and a second grouping value, the method comprising the steps of: maintaining a grouping index mapping from each unique permutation of the first grouping value and the second grouping value among the rows to the rows having that permutation of the first grouping value and the second grouping value; maintaining an aggregation index on the rows; using the aggregation index to identify the aggregated value of each row of the source table; using the grouping index to identify the permutation of the first grouping value and the second grouping value for each row of the source table; for each row, aggregating the identified aggregated value into a result value for the identified permutation of the first grouping value and the second grouping value; using the grouping index to identify the first grouping value of each row of the source table; and for each row, aggregating the identified aggregated value into a result value for the identified first grouping value.

Claim 6

A method in a computer database system for efficiently aggregating a source table to produce a result table, the source table being comprised of rows and having a grouping column and an aggregated column, the columns each being comprised of one value for each row of the source table, the result table being comprised of one row for each unique value of the grouping column, the method comprising the steps of: maintaining indices on the grouping column and the aggregated column, the index on the grouping column mapping from values of the grouping column to rows of the source table, the index on the aggregated column value mapping from values of the aggregated column to rows of the source table; and creating a series of bitmaps from the index on the grouping column, one bitmap for each of a plurality of values of the grouping column, each bitmap indicating whether each row of the source table has the corresponding value of the grouping column; for each value of the aggregated column: identifying the rows of the source table for which the aggregated column contains this value using the index on the aggregated column, and for each identified row of the source table for which the aggregated column contains the value: identifying the value of the grouping columns for this row by interrogating the generated bitmaps in turn and identifying the value of the grouping column corresponding to the bitmap that indicates that this row of the source table has the corresponding value of the grouping column, and aggregating this aggregated column value into the result table for the identified grouping column value.

Claim 7

A method in a computer database system for efficiently aggregating a source table to produce a result table, the source table being comprised of rows and having a grouping column and an aggregated column, the columns each being comprised of one value for each row of the source table, the result table being comprised of one row for each unique value of the grouping column, the method comprising the steps of: maintaining indices on the grouping column and the aggregated column, the index on the grouping column mapping from values of the grouping column to rows of the source table, the index on the aggregated column value mapping from values of the aggregated column to rows of the source table; and creating a series of bitmaps from the index on the grouping column, one bitmap for each of a plurality of values of the grouping column, each bitmap indicating whether each row of the source table has the corresponding value of the grouping column; for each value of the aggregated column: identifying the rows of the source table for which the aggregated column contains this value using the index on the aggregated column, and for each identified row of the source table for which the aggregated column contains the value: identifying the value of the grouping columns for this row by interrogating the generated bitmaps in turn and identifying the value of the grouping column corresponding to the bitmap that indicates that this row of the source table has the corresponding value of the grouping column, and aggregating this aggregated column value into the result table for the identified grouping column value.

Claim 8

A method in a computer system for aggregating aggregated values of a plurality of data elements according to grouping values of the data elements, comprising the steps of: (a) maintaining a relation relating aggregated values and the identity of data elements that have that aggregated value; (b) maintaining a relation relating the identity of data elements and the grouping value of that data element by: (1) maintaining an index on the grouping values, and (2) creating a set of bitmaps from the index on the grouping values that each identify the data entries having one grouping value; (c) using the relation maintained in step (a) to identify the aggregated value of each data element; (d) using the relation maintained in step (b) to identify the grouping value yof each data element; and (e) for each data element, aggregating the aggregated value identified in step (c) into a result value for the grouping value identified in step (d).

Claim 9

A method in a computer system for aggregating aggregated values of a plurality of data elements according to grouping values of the data elements, comprising the steps of: (a) maintaining a relation relating aggregated values and the identity of data elements that have that aggregated value; (b) maintaining a relation relating the identity of data elements and the grouping value of that data element by: (1) maintaining an index on the grouping values, and (2) creating a set of bitmaps from the index on the grouping values that each identify the data entries having one grouping value; (c) using the relation maintained in step (a) to identify the aggregated value of each data element; (d) using the relation maintained in step (b) to identify the grouping value yof each data element; and (e) for each data element, aggregating the aggregated value identified in step (c) into a result value for the grouping value identified in step (d).

Claim 11

An apparatus for efficiently aggregating records, each having a grouping value and an aggregated value, comprising: a record indexing subsystem for producing a grouping index and an aggregation index on the records; a bitmap generator for generating a plurality of bitmaps, each corresponding to a unique grouping value and indicating whether each record has that grouping value; and an aggregation subsystem for aggregating the aggregated value for a record, derived from the aggregation index, into a result value for the grouping value for the record, derived from the grouping index, containing a bitmap application facility for deriving the grouping value for a record from the bitmaps generated by the bitmap generator.

Claim 12

An apparatus for efficiently aggregating records, each having a grouping value and an aggregated value, comprising: a record indexing subsystem for producing a grouping index and an aggregation index on the records; a bitmap generator for generating a plurality of bitmaps, each corresponding to a unique grouping value and indicating whether each record has that grouping value; and an aggregation subsystem for aggregating the aggregated value for a record, derived from the aggregation index, into a result value for the grouping value for the record, derived from the grouping index, containing a bitmap application facility for deriving the grouping value for a record from the bitmaps generated by the bitmap generator.