Exploiting partitioning, grouping, and sorting in query optimization

• US 8,745,037 B2
• Filed: 12/17/2009
• Issued: 06/03/2014
• Est. Priority Date: 12/17/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhou, Jingren, Chaiken, Ronnie Ira, Larson, Pre-Ake
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): ABRAHAM, AHMED M
• Application Number:
  US12/640,829
• Publication Number:
  US 20110153593A1
• Time in Patent Office: 1,629 Days
• Field of Search: 707/718, 707/719, 707/720, 707/721
• US Class Current: 707/718
• CPC Class Codes: G06F 16/24537 of operators

Abstract

An optimizer uses comprehensive reasoning regarding partitioning, sorting, and grouping properties for query optimization. When optimizing an input query expression, logical exploration generates alternative logical expressions. Physical optimization explores physical operator alternatives for logical operators. Required partitioning, sorting, and grouping properties of inputs to physical operators are determined. Additionally, delivered partitioning, sorting, and grouping properties of outputs from physical operators are determined. In some embodiments, enforcer rules are employed to modify structural property requirements to introduce alternatives for consideration. Property matching identifies valid execution plans in which the delivered partitioning, sorting, and grouping properties satisfy corresponding required partitioning, sorting, and grouping properties. An execution plan having the lowest cost is selected as the optimized execution plan.

Claims

1. One or more hardware memory devices, not being a signal per se, storing computer-useable instructions that, when used by one or more computing devices, cause the one or more computing devices to perform a method comprising:

receiving an input query expression and a set of one or more physical property requirements, the input query expression being represented as an operator tree comprising a plurality of logical operators;

performing logical exploration by applying transformation rules to generate a plurality of logical query expressions with varying logical operators;

performing physical optimization for each logical query expression by applying implementation rules to convert logical operators to physical operators

wherein physical optimization comprises;

for each physical operator considered for each logical operator, determining delivered structural properties output by the physical operator, the delivered structural properties including a partitioning property, a sorting property, and a grouping property, each defining a partition, sort, and group structure, respectively, of output data delivered from the physical operator;

for each physical operator considered for each logical operator, determining required structural properties as input for the physical operator, the required structural properties including a partitioning property, a sorting property, and a grouping property, each defining a partition, sort, and group structure, respectively, of input data required for the physical operator;

determining whether delivered structural properties satisfy corresponding required structural properties, wherein determining whether delivered structural properties satisfy corresponding required structural properties comprises;

(a) determining whether delivered partitioning properties satisfy required partitioning properties;

(b) determining whether delivered sorting properties satisfy required sorting properties; and

(c) determining whether delivered grouping properties satisfy required grouping properties;

identifying valid execution plans in which delivered structural properties satisfy required structural properties;

estimating costs associated with each of the valid execution plans; and

selecting, from the valid execution plans, an execution plan having a lowest cost as an optimized execution plan.

2. The one or more hardware memory devices of claim 1, wherein structural properties are represented by a combination of partitioning information and an ordered sequence of actions, each action either grouping on a set of columns or sorting on a single column.

3. The one or more hardware memory devices of claim 1, wherein satisfying each delivered structural properties to a corresponding required structural property comprises matching each delivered structural property to a corresponding required structural property.

4. The one or more hardware memory devices of claim 1, wherein determining whether delivered structural properties satisfy corresponding required structural properties comprises converting structural properties to normalized form.

5. The one or more hardware memory devices of claim 4, wherein converting structural properties to normalized form comprises:

in each partitioning property, sorting property, grouping property, and functional dependency, replacing each column with a representative column in an equivalence class; and

in each partitioning property, sorting property, and grouping property, removing columns that are functionally determined by some other columns.

6. The one or more hardware memory devices of claim 1, wherein determining whether delivered structural properties satisfy corresponding required structural properties comprises using inference rules to determine whether delivered structural properties satisfy required structural properties.

7. The one or more hardware memory devices of claim 1, wherein both non-partitioned and partitioned implementations are considered for each logical operator.

8. The one or more hardware memory devices of claim 1, wherein enforcer rules are employed to modify structural property requirements.

9. The one or more hardware memory devices of claim 8, wherein employing enforcer rules comprises:

determining whether a first physical operator can provide an output that satisfies a particular structural property requirement;

when the first physical operator can provide an output that satisfies the particular structural property requirement, considering the first physical operator for optimization and pushing structural property requirements imposed by the first physical operator to child expressions;

when the first physical operator cannot provide an output that satisfies the particular structural property requirement, and the first physical operator can preserve structural property requirements, considering the first physical operator for optimization and pushing the particular structural property requirement to child expressions, and

when the first physical operator cannot provide an output that satisfies the particular structural property requirement, considering the first physical operator for optimization, adding a new physical operator that satisfies the particular structural property requirement, and optimizing child expressions without imposing the particular structural requirement on child expressions.

10. One or more hardware memory devices, not being a signal per se, storing software components useable by one or more computing devices to provide query optimization, the software components comprising:

a required properties component for determining required structural properties for physical operators being considered during query optimization, the required structural properties including structural property requirements of inputs to the physical operators, the required structural properties including partitioning properties, grouping properties, and sorting properties, each defining the partition, sort, and group structure, respectively, of input data required from physical operators;

a delivered properties component for determining delivered structural properties for the physical operators, the delivered structural properties including structural properties of outputs from the physical operators, the delivered structural properties including partitioning properties, grouping properties, and sorting properties, each defining the partition, sort, and group structure, respectively, of output data delivered from physical operator; and

a property matching component for determining whether delivered structural properties satisfy required structural properties to identify one or more valid execution plans, determining whether delivered structural properties satisfy required structural properties, wherein determining whether delivered structural properties satisfy corresponding required structural properties comprises;

(a) determining whether delivered partitioning properties satisfy required partitioning properties;

(b) determining whether delivered sorting properties satisfy required sorting properties; and

(c) determining whether delivered grouping properties satisfy required grouping properties.

11. The one or more hardware memory devices of claim 10, wherein the software components further comprise an input component for receiving an input query expression and a set of one or more physical property requirements.

12. The one or more hardware memory devices of claim 11, wherein the software components further comprise a logical exploration component that applies transformation rules to the input query expression to generate a plurality of logical query expressions.

13. The one or more hardware memory devices of claim 12, wherein the software components further comprise a cost estimation component that estimates a cost associated with each valid execution plan.

14. The one or more hardware memory devices of claim 13, wherein the software components further comprise an optimized query selection component that selects an execution plan having a lowest cost.

15. The one or more hardware memory devices of claim 10, wherein structural properties are represented by a combination of partitioning information and an ordered sequence of actions, each action either grouping on a set of columns or sorting on a single column.

16. The one or more hardware memory devices of claim 10, wherein the property matching component further satisfies each delivered structural properties to a corresponding required structural property by matching each delivered structural property to a corresponding required structural property.

17. The one or more hardware memory devices of claim 10, wherein the property matching component determines whether delivered structural properties satisfy required structural properties by converting structural properties to normalized form, including in each partitioning property, sorting property, grouping property, and functional dependency, replacing each column with a representative column in an equivalence class, and in each partitioning property, sorting property, and grouping property, removing columns that are functionally determined by some other columns.

18. One or more hardware memory devices, not being a signal per se, storing computer-useable instructions that, when used by one or more computing devices, cause the one or more computing devices to perform a method comprising:

determining whether a first physical operator can provide an output that satisfies a particular structural property requirement based on at least matching the first physical operator output and the particular structural property requirement, wherein matching comprises comparing the first physical operator output to the particular structural property, the particular structural property requirement defines a partition, sort, and group structure of input data required from the first physical operator

when the first physical operator can provide an output that satisfies the particular structural property requirement, considering the first physical operator for optimization and pushing structural property requirements imposed by the first physical operator to child expressions; and

when the first physical operator cannot provide an output that satisfies the particular structural property requirement, and the first physical operator can preserve structural property requirements, considering the first physical operator for optimization and pushing the particular structural property requirement to child expressions, and

when the first physical operator cannot provide an output that satisfies the particular structural property requirement, considering the first physical operator for optimization, adding a new physical operator that satisfies the particular structural property requirement, and optimizing child expressions without imposing the particular structural requirement on child expressions.

19. The one or more hardware memory devices of claim 18, wherein the first physical operator comprises a particular delivered structural property that comprises at least one of a partitioning property, grouping property, and sorting property each defining a partition, sort, and group structure, respectively, of output data delivered from the first physical operator.

20. The one or more hardware memory devices of claim 18, wherein the method further comprises applying cost-based heuristics to prioritize physical operator alternatives and remove physical operator alternatives with higher costs.