DISTANCE-BASED LOGICAL EXPLORATION IN A RELATIONAL DATABASE QUERY OPTIMIZER

• US 20140280035A1
• Filed: 03/14/2013
• Published: 09/18/2014
• Est. Priority Date: 03/14/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Galindo-Legaria, Cesar, Richardson, Andrew S., Fraser, Campbell B., Papadimos, Vasileios, Clinciu, Ciprian G.
• Granted Patent: US 9,892,159 B2
• Time in Patent Office: Days
• US Class Current: 707/718
• CPC Class Codes: G06F 16/24542 Plan optimisation

Abstract

Systems and methods are described that generate an execution plan for a query in a relational database system. The systems and methods generate the execution plan by generating one or more initial logical representations of the query, performing an exploration process around each of the one or more initial logical representations of the query, the performing of the exploration process around a particular initial logical representation of the query comprising applying transformation rules to generate one or more additional logical representations of the query that are logically equivalent to the particular initial logical representation of the query and that are within a maximum allowable transformation distance of the particular initial logical representation of the query, generating one or more execution plans for each initial logical representation of the query and each additional logical representation of the query, and selecting an execution plan from among the generated execution plans.

Claims

1. A method for generating an execution plan for a query in a relational database system, comprising:

generating one or more initial logical representations of the query;

performing an exploration process around each of the one or more initial logical representations of the query, the performing of the exploration process around a particular initial logical representation of the query comprising applying transformation rules to generate one or more additional logical representations of the query that are logically equivalent to the particular initial logical representation of the query and that are within a maximum allowable transformation distance of the particular initial logical representation of the query;

generating one or more execution plans for each initial logical representation of the query and each additional logical representation of the query; and

selecting an execution plan from among the generated execution plans.

2. The method of claim 1 wherein generating the one or more initial logical representations of the query comprises generating one or more initial logical operator trees;

and

wherein generating the one or more additional logical representations of the query comprises generating one or more additional logical operator trees.

3. The method of claim 1, wherein generating the one or more initial logical representations of the query comprises:

applying one or more global heuristics to the query to generate the one or more initial logical representations of the query.

4. The method of claim 3, wherein applying the one or more global heuristics to the query comprises:

applying one or more global heuristics selected or specified by a user of the relational database system.

5. The method of claim 1, wherein selecting the execution plan from among the generated execution plans comprises:

associating a cost with each execution plan in the generated execution plans; and

selecting an execution plan from among the generated execution plans that has a lowest cost associated therewith.

6. The method of claim 1, further comprising:

obtaining the maximum allowable transformation distance from a user;

deriving the maximum allowable transformation distance from other information provided by a user;

or

determining the maximum allowable transformation distance based on one or more factors associated with data in the relational database system or with computing devices used to implement the relational database system.

7. The method of claim 1, further comprising:

in response to determining that a cost associated with the selected execution plan is not acceptable;

increasing the maximum allowable transformation distance; and

continuing the performance of the exploration process around each of the one or more initial logical representations of the query using the increased maximum allowable transformation distance to generate one or more further logical representations of the query.

8. The method of claim 1, further comprising:

in response to determining that an area of a plan search space explored by performing the exploration process a merits further exploration,

increasing the maximum allowable transformation distance; and

continuing the performance of the exploration process in the area of the plan search space using the increased maximum allowable transformation distance.

9. A method for generating an execution plan for a query in a relational database system, comprising:

generating one or more initial logical representations of the query, each initial logical representation including a plurality of operators;

performing a bounded exploration process comprising;

(a) adding the operators of the one or more initial logical representations to a data structure;

(b) identifying zero or more patterns of operators within the data structure that are eligible for the application of a transformation rule, a pattern of operators being eligible for the application of a transformation rule if (i) the pattern of operators matches a pattern associated with the transformation rule and (ii) a search distance associated with one or more of the operators in the pattern of operators is less than a maximum allowable search distance;

(c) applying a transformation rule to each eligible pattern of operators identified in step (b) to generate a logically-equivalent pattern of operators within the data structure, thereby generating one or more additional logical representations of the query within the data structure;

(d) assigning a search distance to each operator within each logically-equivalent pattern of operators generated during step (c), the assigned search distance being a function of a search distance of one or more operators within the eligible pattern of operators to which the logically-equivalent pattern of operators corresponds; and

(e) repeatedly performing steps (b), (c) and (d) until no further patterns of operators that are eligible for the application of a transformation rule can be identified within the data structure;

obtaining one or more physical implementation alternatives for each of the logical representations of the query included in the data structure; and

selecting one of the physical implementation alternatives as the execution plan.

10. The method of claim 9, wherein generating the one or more initial logical representations of the query comprises:

applying one or more global heuristics to the query to generate the one or more initial logical representations of the query.

11. The method of claim 10, wherein applying the one or more global heuristics to the query comprises applying one or more global heuristics selected or specified by a user of the relational database system.

12. The method of claim 9, wherein step (a) comprises:

adding the operators of the initial logical representations of the query to a MEMO data structure.

13. The method of claim 9, wherein obtaining the one or more physical implementation alternatives for each of the logical representations of the query included in the data structure comprises:

converting one or more logical operators in the data structure to physical operators.

14. The method of claim 9, wherein selecting one of the physical implementation alternatives as the execution plan comprises:

calculating a cost associated with each physical implementation alternative obtained for each of the logical representations of the query included in the data structure; and

selecting a physical implementation alternative having the lowest cost associated therewith as the execution plan.

15. The method of claim 9, wherein step (b) further comprises:

determining that a search distance associated with one or more operators in a pattern of operators is less than the maximum allowable search distance, the determining including;

determining a greatest search distance associated with an operator in the pattern of logical operators; and

comparing the greatest search distance to the maximum allowable search distance.

16. The method of claim 9, wherein step (d) comprises:

identifying a function to be used to assign a search distance to each operator within a particular logically-equivalent pattern of operators based on the transformation rule that was applied to generate the particular logically-equivalent pattern of operators.

17. The method of claim 9, further comprising:

obtaining the maximum allowable search distance from a user;

deriving the maximum allowable search distance from other information provided by a user;

or

determining the maximum allowable search distance based on one or more factors associated with data in the relational database system or with computing devices used to implement the relational database system.

18. The method of claim 9, further comprising:

in response to determining that a cost associated with the physical implementation alternative that was selected as the execution plan is not acceptable;

increasing the maximum allowable search distance; and

performing step (e) to generate one or more further logical representations of the query within the data structure.

19. A system, comprising:

one or more processors; and

a storage medium that stores computer program logic that is executable by the one or more processors, the computer program logic comprising;

first computer program logic that is programmed to cause the one or more processors to generate one or more initial logical representations of a query;

second computer program logic that is programmed to cause the one or more processors to perform an exploration process around each of the one or more initial logical representations of the query, the performing of the exploration process around a particular initial logical representation of the query comprising applying transformation rules to generate one or more additional logical representations of the query that are logically equivalent to the particular initial logical representation of the query and that are within a maximum allowable transformation distance of the particular initial logical representation of the query;

third computer program logic that is programmed to cause the one or more processors to generate one or more execution plans for each initial logical representation of the query and each additional logical representation of the query; and

fourth computer program logic that is programmed to cause the one or more processors to select an execution plan from among the generated execution plans.

20. The system of claim 19, wherein the first computer program logic is programmed to cause the one or more processors to generate the one or more initial logical representations of the query by applying one or more global heuristics to the query.