Partial pre-aggregation in relational database queries

• US 7,593,926 B2
• Filed: 03/17/2005
• Issued: 09/22/2009
• Est. Priority Date: 06/30/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Galindo-Legaria, Cesar A., Larson, Per-Ake
• Primary Examiner(s): Mofiz; Apu M
• Assistant Examiner(s): Nguyen; Cindy
• Application Number:
  US11/082,390
• Publication Number:
  US 20050240577A1
• Time in Patent Office: 1,650 Days
• Field of Search: 707 2- 5
• 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. A computer-implemented method of processing a database query, wherein the database query comprises a join operator and an aggregation operator, the method comprising:

inputting one or more records into a single record store memory, wherein the one or more records represent one or more rows of a table, the table having columns representing one or more fields;

determining a value of a column associated with an aggregation operator;

determining a value of a column associated with a join operator;

determining when the value of the column associated with the aggregation operator is equivalent to the value of the column associated with the join operator;

estimating costs and benefits of a partial pre-aggregation, and if indicated by the estimate, utilizing the aggregation operator to partially pre-aggregate the one or more records input into the single record store memory to form partially pre-aggregated records as the one or more records are loaded into the single record store memory;

joining the partially pre-aggregated records if the estimation indicates in the single record store memory utilizing the join operator while concurrently processing a partial pre-aggregation of the records from the database; and

outputting a resulting set of records from the single record store memory to a subsequent database operation.

2. The method as recited in claim 1, wherein the partially pre-aggregating comprises:

maintaining the record store in memory, the record store having no more than one record for each different value of the column associated with the grouping operator;

receiving a new record;

combining the new record with a record in the record store having the same value of the grouping column, 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 value in the grouping column as the new record.

3. The method as recited in claim 2, wherein the partially pre-aggregating further comprises:

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.

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

5. The method as recited in claim 4, wherein outputting the one or more records comprises outputting any records remaining in the record store after there are no new records to process.

6. The method of claim 1, wherein the partially pre-aggregating comprises:

grouping the records from the database into as many groups as there are unique grouping column values; and

partially removing duplicate records from one or more of the groups.

7. The method as recited in claim 1, wherein the partially pre-aggregating includes utilizing a hashing function.

8. One or more computer-readable storage media having computer-executable instructions stored thereon that, when executed, direct a computer to perform the method recited in claim 1.

19. The method as recited in claim 1, wherein:

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

the partially pre-aggregating each record from the database is performed until the single record store reaches capacity.

9. A relational database system configured to process a database query, the relational database system comprising:

memory for storing a record store, the memory having a portion available for query processing; and

a query processor coupled to the memory to process the query using the record store, wherein processing the query using the record store comprises;

one or more records in a single record store memory, wherein the one or more records represent one or more rows of a table, the table having columns representing one or more fields;

a value of a column associated with an aggregation operator;

a value of a column associated with a join operator, when the value of the column associated with the aggregation operator is equivalent to the value of the column associated with the join operator;

an estimation estimating a cost and benefit of a partial pre-aggregation, and if indicated by the estimate, utilizing the aggregation operator to partially pre-aggregate the one or more records input into the single record store memory to form partially pre-aggregated records as the one or more records are loaded into the single record store memory;

a join operator joining the partially pre-aggregated records in the single record store memory utilizing the join operator while concurrently processing a partial pre-aggregation of the records from the database; and

a resulting set of records output from the single record store memory to a subsequent database operation.

10. The relational database system as recited in claim 9, wherein the processing the query using the record store further comprises:

confirming that the database query specifies a same column as a grouping column and as a join column;

maintaining the record store in volatile memory, the record store having no more than one record for each different grouping column value encountered during the partial pre-aggregatlon;

receiving an input record from non-volatile memory;

combining the input record with a record in the record store that has the same grouping column value, if there is such a record; and

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

11. The relational database system as recited in claim 9, wherein the processing the query using the record store further comprises:

continually adding input records to the record store; and

outputting one or more records from the record store to a subsequent database operator when the record store reaches a capacity such that the record store can accept no more new records, or whenever there are no new records to process.

12. The relational database system as recited in claim 9, wherein the processing the query using the record store further comprises utilizing the record store in processing of another database operator.

13. The relational database system as recited in claim 9, wherein the query processor is further configured to utilize hashing to perform the partial pre-aggregatlon.

14. The relational database system as recited in claim 9, wherein the query processor is further configured to utilize hashing and partitioning to perform the partial pre-aggregation.

15. A computer-readable storage medium having computer-executable instructions stored thereon that, when executed, direct a computer to perform a method of processing a database query, wherein the query comprises a join operator and an aggregation operator, the method comprising:

inputting one or more records into a single record store memory, wherein the one or more records represent one or more rows of a table, the table having columns representing one or more fields;

determining a value of a column associated with an aggregation operator;

determining a value of a column associated with a join operator;

determining when the value of the column associated with the aggregation operator is equivalent to the value of the column associated with the join operator;

estimating costs and benefits of a partial pre-aggregation, and if indicated by the estimate, utilizing the aggregation operator to partially pre-aggregate the one or more records input into the single record store memory to form partially pre-aggregated records as the one or more records are loaded into the single record store memory;

joining the partially pre-aggregated records if the estimation indicates in the single record store memory utilizing the join operator while concurrently processing a partial pre-aggregation of the records from the database; and

outputting a resulting set of records from the single record store memory to a subsequent database operation.

16. The computer-readable storage medium as recited in claim 15, wherein the partially pre-aggregating the records from the database according to the aggregation operator comprises:

maintaining the single record store in memory, the single record store having one record for each different grouping column value encountered in the partial pre-aggregation;

receiving a new record;

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

adding the new record to the single record store if no record in the single record store that has the same grouping column value as the new record;

continuously adding additional new records to the single record store until the single record store has reached a record store capacity;

outputting one or more records from the single record store to a subsequent database operator when the single record store has reached the record store capacity; and

outputting the records in the single record store when there are no new records to process.

17. A relational database computer program stored on a computer-readable storage medium, the relational database computer program comprising computer-executable instructions that, when executed, direct a computer to perform a method of processing a query, wherein the query comprises a join operator and an aggregation operator, the method comprising:

inputting one or more records into a single record store memory, wherein the one or more records represent one or more rows of a table, the table having columns representing one or more fields;

determining a value of a column associated with an aggregation operator;

determining a value of a column associated with a join operator;

determining when the value of the column associated with the aggregation operator is equivalent to the value of the column associated with the join operator;

estimating costs and benefits of a partial pre-aggregation, and if indicated by the estimate, utilizing the aggregation operator to partially pre-aggregate the one or more records input into the single record store memory to form partially pre-aggregated records as the one or more records are loaded into the single record store memory;

joining the partially pre-aggregated records if the estimation indicates in the single record store memory utilizing the join operator while concurrently processing a partial pre-aggregation of the records from the database; and

outputting a resulting set of records from the single record store memory to a subsequent operation.

18. The relational database computer program as recited in claim 17, wherein:

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

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

20. A method for processing a database query according to at least one grouping column value, the method comprising:

estimating costs and benefits of a partial pre-aggregation, wherein an estimate of a number of records that would be output from the partial pre-aggregation is based on a formula having inputs comprising;

a memory space for group records, M;

a number of input records, N, N being greater than a number, D, of records after full aggregation; and

an absorption power term, wherein the absorption power term comprises a summation of D terms, each term including a probability of a record belonging in a group of records;

partially pre-aggregating records in a database to provide a result that contains at least two records having like grouping column values, wherein the partially pre-aggregating further comprises;

maintaining a record store in memory, the record store having one record for each different grouping column 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;

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

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.