Method and system for efficiently performing database table aggregation using a bitmask-based index

• US 6,064,999 A
• Filed: 04/15/1998
• Issued: 05/16/2000
• Est. Priority Date: 06/30/1994
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dalal, Ketan
• Primary Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US09/060,860
• Time in Patent Office: 762 Days
• Field of Search: 707/2, 707/3, 707/1, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06Q 30/06 Buying, selling or leasing transactions
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method and system for efficiently performing database table aggregation is provided. In a preferred embodiment, an aggregation facility efficiently aggregates a source table using indices on an aggregated column of the source table and a grouping column of the source table. The facility uses the index on the aggregated column to identify the contents of the aggregated column in each row of the source table. The facility further uses information derived from the index on the grouping column to identify the contents of the grouping column in each row of the source table. For each row of the source table, the facility aggregates the identified aggregated column contents into a result value for the identified grouping column contents. In a further preferred embodiment, the facility generates a relation mapping from source table row to grouping column, which the facility uses to identify the contents of the grouping column in each row of the source table. In a further preferred embodiment, the facility may be used to perform multiple-level aggregations, as well as aggregations in which there are multiple grouping columns, multiple aggregated columns, and/or multiple result columns.

Claims

1. A method in a computer system for aggregating an aggregated value for each of a number of records based upon a grouping value for each record, the method comprising the steps of:

maintaining a first index on the grouping value for each record, the first index constituting a mapping between grouping values and records having the grouping values, the first index comprising, for each different value of the grouping values, a bitmap identifying the records having the grouping value;

maintaining a second index on the aggregated value for each record, the second index constituting a mapping between aggregated values and records having the aggregated values;

using the second index to identify the aggregated value for each record;

using the first index to identify the grouping value for each record; and

for each record, aggregating the identified aggregated value into a result value for the identified grouping value.

2. The method of claim 1 wherein each bitmap is a series of bits each corresponding in a one-to-one manner with one of the records, each bit either being set or being not set, and wherein the step of using the first index to identify the grouping value for each record comprises the steps of:

for each different grouping value,

for each record,

determining whether the bit corresponding to the record in the bitmap for the grouping value is set.

3. 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 method comprising the steps of:

maintaining a grouping index on the rows of the source table, the grouping index constituting a mapping between grouping values and rows having the grouping values, the grouping index comprising, for each different value of the grouping values, a bitmap identifying the records having the grouping value;

maintaining an aggregation index on the rows of the source table the aggregation index constituting a mapping between aggregated values and rows having the aggregated values;

using the aggregation index to identify the aggregated value of each row of the source table;

using the grouping index 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.

4. The method of claim 3 wherein the aggregating step includes the steps of:

aggregating the identified aggregated value into a first component of the result value using a first aggregation function; and

aggregating the identified aggregated value into a second component of the result value using a second aggregation function.

5. The method of claim 3 wherein each bitmap is a series of bits each corresponding in a one-to-one manner with one of the records, each bit either being set or being not set, and wherein the step of using the grouping index to identify the grouping value for each record comprises the steps of:

for each different grouping value,

for each record,

determining whether the bit corresponding to the record in the bitmap for the grouping value is set.

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, the index on the grouping column being comprised of a different bitmap for each different value of the aggregated column, each bitmap comprising a group of bits each corresponding to a different row, each bit either being set to indicate that the row has the value or being clear to indicate that the row does not have the value; and

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 column for this row by determining whether the bit corresponding to this row in the bitmap of the index on the grouping column for this aggregated column is set, and

aggregating this aggregated column value into the result table for the identified grouping column value.

7. An apparatus for aggregating aggregated values of a plurality of data elements according to grouping values of the data elements, comprising:

an index generator for generating an aggregation index constituting a mapping between aggregated values and data elements having those aggregated values and for generating a grouping index constituting a mapping between data elements and grouping values of those data elements, the grouping index comprising, for each different value of the grouping values, a bitmap identifying the records having the grouping value; and

an aggregation subsystem for, for each data element, aggregating the aggregated value for the data element, derived from the first relation, into a result value for the grouping value for the data element, derived from the second relation.

8. 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; 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; and

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 wherein the aggregation subsystem contains a bitmap application facility for deriving the grouping value for a record from the bitmaps generated by the bitmap generator.

9. A computer-readable medium whose contents cause a computer system to aggregate an aggregated value for each of a number of records based upon a grouping value for each record by performing the steps of:

maintaining a first index on the grouping value for each record, the first index constituting a mapping between grouping values and records having the grouping values;

maintaining a second index on the aggregated value for each record, the second index constituting a mapping between aggregated values and records having the aggregated values, for each different value of the grouping values, a bitmap identifying the records having the grouping value;

using the second index to identify the aggregated value for each record;

using the first index to identify the grouping value for each record; and

for each record, aggregating the identified aggregated value into a result value for the identified grouping value.

10. A computer-readable medium whose contents cause a computer system to aggregate a source table comprised of rows, each row having associated with it an aggregated value and a grouping value, by performing the steps of:

maintaining a grouping index on the rows of the source table, the grouping index constituting a mapping between grouping values and rows having the grouping values;

maintaining an aggregation index on the rows of the source table, the aggregation index constituting a mapping between aggregated values and rows having the aggregated values, the grouping index comprising, for each different value of the grouping values, a bitmap identifying the records having the grouping value;

using the aggregation index to identify the aggregated value of each row of the source table;

using the grouping index 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.

11. The computer-readable medium of claim 10 wherein the aggregating step includes the steps of:

aggregating the identified aggregated value into a first component of the result value using a first aggregation function; and

aggregating the identified aggregated value into a second component of the result value using a second aggregation function.

12. A method in a computer system for aggregating aggregated values of a plurality of data elements according to grouping values of the data elements, the method comprising the steps of:

generating an aggregation index constituting a mapping between aggregated values and data elements having those aggregated values;

generating a grouping index constituting a mapping between data elements and grouping values of those data elements, the grouping index comprising, for each different value of the grouping values, a bitmap identifying the records having the grouping value; and

for each data element, aggregating the aggregated value for the data element, derived from the aggregation index, into a result value for the grouping value for the data element, derived from the grouping index.

13. A computer-readable medium whose contents cause a computer system to aggregate values of a plurality of data elements according to grouping values of the data elements, by performing the steps of:

generating an aggregation index constituting a mapping between aggregated values and data elements having those aggregated values;

generating a grouping index constituting a mapping between data elements and grouping values of those data elements, the grouping index comprising, for each different value of the grouping values, a bitmap identifying the records having the grouping value; and

for each data element, aggregating the aggregated value for the data element, derived from the aggregation index, into a result value for the grouping value for the data element, derived from the grouping index.