Combining nested aggregators

• US 20070130110A1
• Filed: 12/07/2005
• Published: 06/07/2007
• Est. Priority Date: 12/07/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Graefe, Goetz, Kogan, Yevgeniy, Seeliger, Oliver, Grabs, Torsten
• Granted Patent: US 7,577,647 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24537 of operators
• 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 method and system for transforming a query tree that includes more than one aggregator. The method includes identifying a first aggregator in the query tree, identifying a second aggregator that is located below the first aggregator in the query tree, and merging the second aggregator with the first aggregator to form a merged aggregator.

Claims

1. A method for transforming a query tree that includes more than one aggregator, the method comprising:

a. identifying a first aggregator in the query tree;

b. identifying a second aggregator that is located below the first aggregator in the query tree; and

c. merging the second aggregator with the first aggregator to form a merged aggregator.

2. The method according to claim 1, further comprising identifying a join operator that is located in the query tree between the first aggregator and the second aggregator.

3. The method according to claim 1, further comprising:

a. identifying an apply operator having a join type that is located between the first aggregator and the second aggregator in the query tree; and

b. changing the join type of the apply operator.

4. The method according to claim 3, wherein the join type of the apply operator is changed to a join type selected from the group consisting of left-outer, right-outer, and full-outer.

5. The method according to claim 3, wherein:

a. the second aggregator is a right-hand child to the apply operator; and

b. the join type of the apply operator is changed from inner to left-outer.

6. The method according to claim 3, wherein:

a. the second aggregator is a left-hand child to the apply operator; and

b. the join type of the apply operator is changed from inner to right-outer.

7. The method according to claim 3, wherein:

a. the first aggregator is a merged form of two or more aggregators;

b. the second aggregator is a child to the apply operator; and

c. the join type of the apply operator is changed from inner to full-outer.

8. The method according to claim 3, wherein:

a. the method further comprises;

i. identifying a first relational input that is input to the apply operator, and

ii. identifying a second relational input that is input to the second aggregator before the transformation of the query tree;

b. wherein the second relational input is input to the apply operator after the transformation of the query tree.

9. The method according to claim 1, further comprising creating a row set that is:

a. configured to be aggregated by the merged aggregator;

b. configured to avoid materialization of intermediate results during aggregation; and

c. configured to allow the merged aggregator to perform streaming aggregation.

10. The method according to claim 1, wherein the first aggregator, the second aggregator, and the merged aggregator are complex aggregators.

11. The method according to claim 1, wherein the first aggregator, the second aggregator, and the merged aggregator are selected from the group consisting of XML aggregators and group-by aggregators.

12. A computer-readable medium having computer-executable instructions for performing a method of transforming a query tree, the method comprising:

a. identifying a first aggregator in the query tree;

b. identifying an apply operator having a join type below the first aggregator in the query tree;

c. identifying a second aggregator that is located below the apply operator in the query tree;

d. merging the second aggregator with the first aggregator to form a merged aggregator;

e. changing the join type of the apply operator; and

f. creating a row set that is;

i. configured to be aggregated by the merged aggregator,

ii. configured to avoid materialization of intermediate results during aggregation, and

iii. configured to allow the merged aggregator to perform streaming aggregation.

13. The computer-readable medium according to claim 12, wherein:

a. the second aggregator is a right-hand child to the apply operator; and

b. the join type of the apply operator is changed from inner to left-outer.

14. The computer-readable medium according to claim 12, wherein:

a. the second aggregator is a left-hand child to the apply operator; and

b. the join type of the apply operator is changed from inner to right-outer.

15. The computer-readable medium according to claim 12, wherein:

a. the first aggregator is a merged form of two or more aggregators;

b. the second aggregator is a child to the apply operator; and

c. the join type of the apply operator is changed from inner to full-outer.

16. A computer database system for executing a database query, the computer database system comprising:

a. a database management system that is configured both to receive the database query and to convert the database query into a query tree;

b. wherein;

i. the database management system includes an optimizer that is configured to transform the query tree,

ii. the query tree includes;

A. a first aggregator, and

B. a second aggregator that is located below the first aggregator, and

iii. the optimizer transforms the query tree by merging the second aggregator with the first aggregator to form a merged aggregator.

17. The computer database system according to claim 16, wherein:

a. the query tree includes an apply operator having a join type that is located between the first aggregator and the second aggregator in the query tree;

b. the second aggregator is a right-hand child to the apply operator; and

c. the optimizer changes the join type of the apply operator from inner to left-outer as the optimizer transforms the query tree.

18. The computer database system according to claim 16, wherein:

a. the query tree includes an apply operator having a join type that is located between the first aggregator and the second aggregator in the query tree;

b. the second aggregator is a left-hand child to the apply operator; and

c. the optimizer changes the join type of the apply operator from inner to right-outer as the optimizer transforms the query tree.

19. The computer database system according to claim 16, wherein:

a. the query tree includes an apply operator having a join type that is located between the first aggregator and the second aggregator in the query tree;

b. the first aggregator is a merged form of two or more aggregators;

c. the second aggregator is a child to the apply operator; and

d. the optimizer changes the join type of the apply operator from inner to full-outer as the optimizer transforms the query tree.

20. The computer database system according to claim 16, wherein the optimizer creates a row set that is:

a. configured to be aggregated by the merged aggregator;

b. configured to avoid materialization of intermediate results during aggregation; and

c. configured to allow the merged aggregator to perform streaming aggregation.