Partial pre-aggregation in relational database queries

• US 20050240556A1
• Filed: 03/17/2005
• Published: 10/27/2005
• Est. Priority Date: 06/30/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Galindo-Legaria, Cesar A., Larson, Per-Ake
• Granted Patent: US 7,555,473 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• 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/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A partial pre-aggregation database operation improves processing efficiency of database queries by reducing the number of records input into a subsequent database operation, provided the query includes a final aggregation. A query optimizer is provided to determine when it is economical to partially pre-aggregate data records and when it is not. The partial pre-aggregation creates a record store in memory as input records are received. The record store is then used by another database operator, which saves the other database operator from having to re-create the record store.

Claims

1. One or more computer-readable media comprising computer-executable instructions for processing a database query, the computer-executable instructions comprising instructions for:

partially pre-aggregating records in a database according to a single grouping column to provide a result that contains at least two records having like grouping column values;

aggregating records derived from the partial pre-aggregation to provide a result that contains records having unique grouping column values; and

estimating the costs and benefits of the partial pre-aggregation, and partially pre-aggregating the records only if the estimating indicates that the benefits are greater than the costs.

2. The one or more computer-readable medium as recited in claim 1, wherein the partially pre-aggregating further comprises instructions for:

maintaining a record store in memory, the record store having one record for each different grouping column value encountered in the operation;

receiving a new record;

combining the new record with a record having the same grouping column value, if such a record exists; and

adding the new record to the record store in the memory if there is no record in the record store that has the same grouping column value as the new record.

3. The one or more computer-readable medium as recited in claim 2, further comprising instructions for:

adding additional new records to the record store until the record store reaches a capacity such that it can accept no new records; and

outputting one or more records from the record store to a subsequent database operator.

4. The one or more computer-readable medium as recited in claim 3, wherein after the one or more records have been output to the subsequent database operator, the instructions for adding and outputting are repeated until there are no new records to process.

5. The one or more computer-readable medium as recited in claim 4, comprising instructions for outputting any records, remaining in the record store after there are no new records to process, to the subsequent database operator.

6. The one or more computer-readable medium as recited in claim 3, wherein the subsequent database operator comprises instructions for a join.

7. The one or more computer-readable medium as recited in claim 1, wherein the partially pre-aggregating includes instructions for utilizing a hashing function.

8. The one or more computer-readable medium as recited in claim 1, wherein the partial pre-aggregating creates a record store in memory, and wherein the method further comprises utilizing the record store in memory for one or more other database operators.

9. A relational database computer program stored on a computer-readable medium, the relational database computer program comprising:

means for receiving a stream of input records;

means for aggregating the input records in the stream according to a single grouping column as it is received to create a record store;

means for joining records in the record store with other data;

means for aggregating the records output from the join;

means for determining if it is optimal to aggregate the input records prior to performing the join; and

means for performing the aggregation prior to the join only if a determination is made that it is optimal to perform an aggregation prior to the join;

wherein the records output from the join include at least two records that have an identical grouping column value in the single grouping column; and

10. The relational database computer program as recited in claim 9, wherein:

the record store has a capacity that is less than the number of records in the stream of input records; and

the means for aggregating each input record is performed until the record store reaches capacity.