OPTIMIZING PARALLEL QUERIES USING INTERESTING DISTRIBUTIONS

• US 20160078090A1
• Filed: 11/27/2015
• Published: 03/17/2016
• 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.
• Granted Patent: US 9,734,201 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 processors;

system memory; and

a distribution identifier, using one of the one or more processors, configured to;

access a query plan search space for a query of a distributed database; and

formulate an annotated query plan search space, including;

for a group of logical operators in the query plan search space, identify a distribution property indicating an interesting type of distribution relevant to the group, the distribution property identifying a column that data for a parent group of the group is distributed on; and

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

2. The computer system of claim 1, wherein a distribution identifier, using one of the one or more processors, configured to identify a distribution property indicating an interesting type of distribution relevant to the group comprises the distribution identifier, using one of the one or more processors, configured 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, and an indication that a table is located on a control node of the distributed database.

3. The computer system of claim 1, wherein a distribution identifier, using one of the one or more processors, configured to identify a distribution property indicating an interesting type of distribution relevant to the group comprises the distribution identifier, using one of the one or more processors, configured to identify an interesting type of distribution for a top operator.

4. The computer system of claim 1, wherein a distribution identifier, using one of the one or more processors, configured to identify a distribution property indicating an interesting type of distribution relevant to the group comprises the distribution identifier, using one of the one or more processors, configured to identify an interesting 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 a distribution identifier, using one of the one or more processors, configured to identify a distribution property indicating an interesting type of distribution relevant to the group comprises the distribution identifier, using one of the one or more processors, configured to identify an interesting 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 1, wherein a distribution identifier, using one of the one or more processors, configured to identify a distribution property indicating an interesting type of distribution relevant to the group comprises the distribution identifier, using one of the one or more processors, configured to identify the hash distribution of the column as an interesting distribution for the insert operator.

7. The computer system of claim 1, wherein a distribution identifier, using one of the one or more processors, configured to identify a distribution property indicating an interesting type of distribution relevant to the group comprises the distribution identifier, using one of the one or more processors, configured to identify an inherited interesting distribution that originated at and was inherited from a parent group of the group.

8. The method of claim 7, wherein a distribution identifier, using one of the one or more processors, configured to annotate the group with the interesting type of distribution comprises the distribution identifier, using one of the one or more processors, configured to propagate the inherited interesting distribution down to the child groups.

9. The computer system of claim 1, wherein a distribution identifier, using one of the one or more processors, configured to identifying a distribution property indicating an interesting type of distribution relevant to the group comprises the distribution identifier, using one of the one or more processors, configured to identify an interesting distribution generated by the one or more logical operators in the group.

10. The method of claim 9, wherein a distribution identifier, using one of the one or more processors, configured to annotate the group with the interesting type of distribution comprises a distribution identifier, using one of the one or more processors, configured to add the interesting distribution generated by the one or more logical operators in the group to one or more child groups.

11. A method for use at a computer system, the computer system including one or more processors and system memory, a method for identifying and propagating interesting properties within a query plan search space, the method comprising:

accessing a query plan search space for a query of a distributed database; and

formulating an annotated query plan search space by;

for a group of logical operators in the query plan search space, identifying a distribution property indicating an interesting type of distribution relevant to the group, the distribution property identifying a column that data for a parent group of the group is distributed on; and

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

12. The method of claim 11, wherein identifying a distribution property indicating an interesting type of distribution relevant to the 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, and 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 indicating an interesting type of distribution relevant to the group comprises identifying an interesting type of distribution for a top operator.

14. The method of claim 11, wherein identifying a distribution property indicating an interesting type of distribution relevant to the group comprises identifying an interesting 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.

15. The method of claim 11, wherein identifying a distribution property indicating an interesting type of distribution relevant to the group comprises identifying an interesting 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 11, wherein identifying a distribution property indicating an interesting type of distribution relevant to the group comprises identifying the hash distribution of the column as an interesting distribution for the insert operator.

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

and

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

18. The method of claim 11, wherein identifying a distribution property indicating an interesting type of distribution relevant to the group comprises identifying an interesting distribution generated by the one or more logical operators in the group;

and

wherein annotating the group with the interesting type of distribution comprises adding the interesting distribution generated by the one or more logical operators in the group to one or more child groups.

19. A computer program product for use at a computer system, the computer program product for implementing a method for identifying and propagating interesting properties within a query plan search space, the computer program product comprising one or more computer storage devices having stored thereon computer-executable instructions that, when executed at a processor, cause the computer system to perform the method, including the following.

access a query plan search space for a query of a distributed database;

and

formulate an annotated query plan search space, including;

for a group of logical operators in the query plan search space, identify a distribution property indicating an interesting type of distribution relevant to the group, the distribution property identifying a column that data for a parent group of the group is distributed on; and

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

20. The program product of claim 19, wherein computer-executable instructions that, when executed, cause the computer system to identify a distribution property indicating an interesting type of distribution relevant to the group comprise computer-executable instructions that, when executed, cause the computer system 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, and an indication that a table is located on a control node of the distributed database.