Optimizing parallel queries using interesting distributions

• US 9,734,201 B2
• Filed: 11/27/2015
• Issued: 08/15/2017
• Est. Priority Date: 12/11/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Shankar, Srinath, Nehme, Rimma V.
• Primary Examiner(s): Perveen, Rehana
• Assistant Examiner(s): Tran, Loc
• Application Number:
  US14/953,297
• Publication Number:
  US 20160078090A1
• Time in Patent Office: 627 Days
• Field of Search: 707714, 707718, 707719
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/24573 using data annotations, e.g. user-defined metadata

Abstract

The present invention extends to methods, systems, and computer program products for optimizing parallel queries using interesting distributions. For each logical operator in an SQL server MEMO, in a top down manner from a root operator to the leaf operators, interesting distributions for the operators can be identified based on the properties of the operators. Identified interesting distributions can be propagated down to lower operators by annotating the lower operators with the interesting distributions. Thus, a SQL server MEMO can be annotated with interesting distributions propagated top down from root to leaf logical operators to generate an annotated SQL server MEMO. Parallel query plans can then be generated from the annotated SQL server MEMO in a bottom up manner from leaf operators to a root operator. Annotated interesting properties can be used to prune operators, thereby facilitating a more tractable search space for a parallel query plan.

Claims

1. A computer system, the computer system comprising:

one or more hardware processors;

system memory coupled to the one or more hardware processors, the system memory storing instructions that are executable by the one or more hardware processors; and

the one or more hardware processors executing the instructions stored in the system memory to optimize a query, including the following;

access a query plan search space for a query of a distributed database, the query plan search space including a hierarchical structure of a root group of logical operators, one or more intermediate groups of logical operators, and one or more leaf groups of logical operators; and

formulate an annotated query plan search space for the query, including;

identify a distribution property for a child group of at least one other group, the at least one other group selected from among;

the root group and the one or more intermediate groups, the distribution property indicating type of distribution relevant to the child group, the distribution property identifying a column that data for a parent group is distributed on, the parent group being above the child group in the hierarchical structure; and

annotate the child group with the type of distribution by attaching an indication of the identified column to the child group to propagate the identified type of distribution to the child group for use in query plan pruning.

2. The computer system of claim 1, wherein the one or more hardware processors executing the instructions to identify a distribution property comprises the one or more hardware processors executing the instructions to identify one or more of:

a hash-distribution on equi-join predicates for joins, a hash distribution of group-by/partitioning columns for grouping/partitioning operators, a replicated distribution for a join operator, a replicated distribution for a grouping operator, a replicated distribution for a partitioning operator, or an indication that a table is located on a control node of the distributed database.

3. The computer system of claim 1, wherein the one or more hardware processors executing the instructions to identify a distribution property comprises the one or more hardware processors executing the instructions to identify a distribution property that indicates a type of distribution for a top operator.

4. The computer system of claim 1, wherein the one or more hardware processors executing the instructions to identify a distribution property comprises the one or more hardware processors executing the instructions to identify distribution property for a type of distribution that includes a combination of a replicated distribution and an indication that a table is located on a control node of the distributed database.

5. The computer system of claim 1, wherein the one or more hardware processors executing the instructions to identify a distribution property comprises the one or more hardware processors executing the instructions to identify distribution property that indicates a type of distribution for an insert operator, the insert operator inserting rows from a source select statement into a table, the table being hash distributed on the column.

6. The computer system of claim 5, wherein the one or more hardware processors executing the instructions to identify a distribution property that indicates type of distribution for an insert operator comprises the one or more hardware processors executing the instructions to identify a distribution property that indicates the hash distribution of the column as the type of distribution for the insert operator.

7. The computer system of claim 1, wherein the one or more hardware processors executing the instructions to identify a distribution property comprises the one or more hardware processors executing the instructions to identify a distribution property for an inherited distribution type that originated at and was inherited from the parent group.

8. The computer system of claim 7, wherein the one or more hardware processors executing the instructions to annotate the child group with the type of distribution comprises the one or more hardware processors executing the instructions to propagate the inherited distribution type down to one or more further child groups of the child group, the one or more further child groups selected from among:

the one or more intermediate groups and the one or more leaf groups.

9. The computer system of claim 1, wherein the one or more hardware processors executing the instructions to identify a distribution property comprises the one or more hardware processors executing the instructions to identify a distribution identifier for a type of distribution generated by one or more logical operators in the at least one other group.

10. The computer system of claim 9, wherein the one or more hardware processors executing the instructions to annotate the child group with the type of distribution comprises the one or more hardware processors executing the instructions to add the type of distribution generated by the one or more logical operators to one or more further child groups of the child group, the one or more further child groups selected from among:

the one or more intermediate groups and the one or more leaf groups.

11. A method for use at a computer system, the computer system including one or more processors and system memory, the method for optimizing a query, the method comprising:

accessing a query plan search space for a query of a distributed database, the query plan search space including a hierarchical structure of a root group of logical operators, one or more intermediate groups of logical operators, and one or more leaf groups of logical operators; and

formulating an annotated query plan search space for the query by;

identifying a distribution property for a child group of at least one other group, the at least one other group selected from among;

the root group and the one or more intermediate groups, the distribution property indicating type of distribution relevant to the child group, the distribution property identifying a column that data for a parent group is distributed on, the parent group being above the child group in the hierarchical structure; and

annotating the child group with the type of distribution by attaching an indication of the identified column to the child group to propagate the identified type of distribution to the child group for use in query plan pruning.

12. The method of claim 11, wherein identifying a distribution property indicating a type of distribution relevant to the child group comprises identifying one or more of:

a hash-distribution on equi-join predicates for joins, a hash distribution of group-by/partitioning columns for grouping/partitioning operators, a replicated distribution for a join operator, a replicated distribution for a grouping operator, a replicated distribution for a partitioning operator, or an indication that a table is located on a control node of the distributed database.

13. The method of claim 11, wherein identifying a distribution property comprises identifying a distribution property of the at least one other group.

14. The method of claim 11, wherein identifying a distribution property comprises identifying distribution property that identifies a column that data for the parent group is distributed on, the parent group selected from among:

the root group and the one or more intermediate groups.

15. The method of claim 11, wherein identifying a distribution property comprises identifying a distribution property that indicates a type of distribution for an insert operator, the insert operator inserting rows from a source select statement into a table, the table being hash distributed on the column.

16. The method of claim 15, wherein identifying a distribution property that indicates a type of distribution for an insert operator comprises identifying the hash distribution of the column as the type of distribution for the insert operator.

17. The method of claim 11, wherein identifying a distribution property comprises identifying a distribution property for an inherited distribution type that originated at and was inherited from the parent group;

and

wherein annotating the child group with the type of distribution comprises propagating the inherited distribution type down to one or more further child groups of the child group.

18. The method of claim 11, wherein identifying a distribution property comprises identifying distribution property for a type of distribution generated by one or more logical operators in the at least one other group;

and

wherein annotating the child group with the type of distribution comprises;

annotating an intermediate group with the type of distribution, the intermediate group selected from among the one or more intermediate groups; and

adding the type of distribution to one or more further child groups of the intermediate group.