System and method for forcing a query execution plan

• US 7,464,071 B2
• Filed: 04/28/2005
• Issued: 12/09/2008
• Est. Priority Date: 04/28/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Yu, Wei, Krishnamoorthy, Ganapathy, Hanson, Eric N., Galindo-Legaria, Cesar, Joshi, Milind
• Primary Examiner(s): Alam; Hosain T
• Assistant Examiner(s): Ng; Amy
• Application Number:
  US11/117,586
• Publication Number:
  US 20060248046A1
• Time in Patent Office: 1,321 Days
• Field of Search: 707/2, 707/3
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24549 Run-time optimisation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A suggested query execution plan is used as a constraint on a guided optimization process such that all execution plans that do not conform to the suggested execution plan are eliminated as possible alternatives. If the guided optimization process successfully generates a resulting execution plan, then the result will conform to the suggested execution plan. If the guided optimization process fails to generate a resulting execution plan, then it may be determined that the suggested execution plan is invalid.

Claims

1. A method for forcing a query execution plan, the method comprising:

receiving a suggested execution plan;

generating a hint tree that is a structural representation of the suggested execution plan;

generating a plurality of execution plans; and

performing a guided query optimization in which execution plans that do not match the suggested execution plan are eliminated as candidates such that the guided query optimization generates a resulting execution plan that matches the suggested execution plan or a determination that the suggested execution plan is invalid, guided query optimization comprising

(a) setting a parent node to be a root node of an execution plan tree;

(b) generating a possible set of child nodes of the parent node;

(c) comparing the possible set of child nodes to a corresponding set of child nodes in the hint tree, and

(d) if the possible set of child nodes does not match the corresponding set of child nodes in the hint tree, then;

if there is another possible set of child nodes, then returning to step (b);

if there is no other possible set of child nodes, then determining that the hint tree is invalid;

(e) if the set of possible child nodes matches the corresponding set of child nodes in the hint tree, then;

if there is a remaining non-leaf node in the execution plan tree, then setting the parent node to be the remaining non-leaf node and returning to step (b); and

if there is no remaining non-leaf node in the execution plan tree, then generating the resulting execution plan in accordance with the execution plan tree in its current form.

2. The method of claim 1, comprising receiving a textual representation of the suggested execution plan that is encoded in extensible markup language showplan format.

3. The method of claim 1, comprising receiving the suggested execution plan that was generated by a previous query optimization.

4. The method of claim 3, comprising receiving the suggested execution plan that was generated by the previous query optimization and then subsequently edited.

5. The method of claim 1, further comprising associating the suggested execution plan to the query through reference to a lookup table.

6. A computer readable storage medium storing computer executable instructions for performing the following steps comprising:

receiving a suggested execution plan;

generating a hint tree that is a structural representation of the suggested execution plan;

generating a plurality of execution plans; and

performing a guided query optimization in which execution plans that do not match the suggested execution plan are eliminated as candidates such that the guided query optimization generates a resulting execution plan that matches the suggested execution plan or a determination that the suggested execution plan is invalid, guided query optimization comprising

(a) setting a parent node to be a root node of an execution plan tree;

(b) generating a possible set of child nodes of the parent node;

(c) comparing the possible set of child nodes to a corresponding set of child nodes in the hint tree, and

(d) if the possible set of child nodes does not match the corresponding set of child nodes in the hint tree, then;

if there is another possible set of child nodes, then returning to step (b);

if there is no other possible set of child nodes, then determining that the hint tree is invalid;

(e) if the set of possible child nodes matches the corresponding set of child nodes in the hint tree, then;

if there is a remaining non-leaf node in the execution plan tree, then setting the parent node to be the remaining non-leaf node and returning to step (b); and

if there is no remaining non-leaf node in the execution plan tree, then generating the resulting execution plan in accordance with the execution plan tree in its current form.

7. The computer readable storage medium of claim 6, wherein the suggested execution plan is encoded in extensible markup language showplan format.

8. The computer readable storage medium of claim 6, wherein the suggested execution plan is generated by a previous query optimization.

9. The computer readable storage medium of claim 6, wherein the suggested execution plan is generated by the previous query optimization and then subsequently edited.

10. The computer readable storage medium of claim 6, further comprising computer executable instructions for associating the suggested execution plan to the query through reference to a lookup table.

11. A system for forcing a query execution plan, the system comprising

a processor operative to execute computer executable instructions, and memory having stored therein computer executable instructions for performing the following steps:

receiving a suggested execution plan;

generating a hint tree that is a structural representation of the suggested execution plan;

generating a plurality of execution plans; and

performing a guided query optimization in which execution plans that do not match the suggested execution plan are eliminated as candidates such that the guided query optimization generates a resulting execution plan that matches the suggested execution plan or a determination that the suggested execution plan is invalid, guided query optimization comprising

(a) setting a parent node to be a root node of an execution plan tree;

(b) generating a possible set of child nodes of the parent node;

(c) comparing the possible set of child nodes to a corresponding set of child nodes in the hint tree, and

(d) if the possible set of child nodes does not match the corresponding set of child nodes in the hint tree, then;

if there is another possible set of child nodes, then returning to step (b);

if there is no other possible set of child nodes, then determining that the hint tree is invalid;

(e) if the set of possible child nodes matches the corresponding set of child nodes in the hint tree, then;

if there is a remaining non-leaf node in the execution plan tree, then setting the parent node to be the remaining non-leaf node and returning to step (b); and

if there is no remaining non-leaf node in the execution plan tree, then generating the resulting execution plan in accordance with the execution plan tree in its current form.

12. The system of claim 11, further comprising an execution plan generator that associates the suggested execution plan to the query.

13. The system of claim 12, further comprising lookup tables through which the execution plan generator associates the suggested execution plan to the query.

14. The system of claim 11, wherein the suggested execution plan is encoded in extensible markup language showplan format.

15. The system of claim 11, wherein the suggested execution plan is generated by a previous query optimization.

16. The system of claim 11, wherein the suggested execution plan is generated by the previous query optimization and then subsequently edited.