Combining nested aggregators

• US 7,577,647 B2
• Filed: 12/07/2005
• Issued: 08/18/2009
• Est. Priority Date: 12/07/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Grabs, Torsten W., Graefe, Goetz, Seeliger, Oliver N., Kogan, Yevgeniy L.
• Primary Examiner(s): Fleurantin; Jean B
• Assistant Examiner(s): NGUYEN, PHONG H
• Application Number:
  US11/296,558
• Publication Number:
  US 20070130110A1
• Time in Patent Office: 1,350 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 709/203
• 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 implemented on a processor coupled to a memory, 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;

c. identifying an apply operator between the first and second aggregators in the query tree;

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

e. determining whether the first aggregator is a merged aggregator before the merging of the first and second aggregators;

f. if the first aggregator is a merged aggregator before the merging of the first and second aggregators, changing a join type of the apply operator from inner to full-outer with a false predicate;

g. if the first aggregator is not a merged aggregator before the merging of the first and second aggregators, determining whether the second aggregator is a right-hand child to the apply operator before the merging of the first and second aggregators;

h. if the second aggregator is a right-hand child to the apply operator before the merging of the first and second aggregators, changing a join type of the apply operator from inner to left-outer; and

i. if the second aggregator is not a right-hand child to the apply operator before the merging of the first and second aggregators, changing a join type of the apply operator from inner to right-outer.

2. The method according to claim 1, 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.

3. 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.

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

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

6. A computer storage 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. determining whether the first aggregator is a merged aggregator before the merging of the first and second aggregators; and

f. if the first aggregator is a merged aggregator before the merging of the first and second aggregators, changing a join type of the apply operator from inner to full-outer with a false predicate;

g. if the first aggregator is not a merged aggregator before the merging of the first and second aggregators, determining whether the second aggregator is a right-hand child to the apply operator before the merging of the first and second aggregators;

h. if the second aggregator is a right-hand child to the apply operator before the merging of the first and second aggregators, changing a join type of the apply operator from inner to left-outer; and

i. if the second aggregator is not a right-hand child to the apply operator before the merging of the first and second aggregators, changing a join type of the apply operator from inner to right-outer; and

j. creating a row set that is;

i. configured to be aggregated by the merged aggregator,

ii. configured so that no materialization of intermediate results is necessary during aggregation, and

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

7. A computer-implemented database system for executing a database query, the computer database system comprising:

a. a database server computer coupled to a database storage device that stores information in a database, the database query to be executed upon the information stored in the database;

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

c. 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, the optimizer;

A. determines whether the first aggregator is a merged aggregator before the merging of the first and second aggregators;

B. if the first aggregator is a merged aggregator before the merging of the first and second aggregators, as the optimizer transforms the query tree, the optimizer changes a join type of the apply operator from inner to full-outer with a false predicate;

C. if the first aggregator is not a merged aggregator before the merging of the first and second aggregators, the optimizer determines whether the second aggregator is a right-hand child to the apply operator before the merging of the first and second aggregators;

D. if the second aggregator is a right-hand child to the apply operator before the merging of the first and second aggregators, as the optimizer transforms the query tree, the optimizer changes a join type of the apply operator from inner to left-outer; and

E. if the second aggregator is not a right-hand child to the apply operator before the merging of the first and second aggregators, as the optimizer transforms the query tree, the optimizer changes a join type of the apply operator from inner to right-outer.

8. The computer-implemented database system according to claim 7, 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.