OPTIMIZING PARAMETERIZED QUERIES IN A RELATIONAL DATABASE MANAGEMENT SYSTEM

• US 20080052266A1
• Filed: 08/25/2006
• Published: 02/28/2008
• Est. Priority Date: 08/25/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Larson, Per-Ake, Zhou, Jingren, Goldstein, Jonathan D.
• Granted Patent: US 8,032,522 B2
• Time in Patent Office: Days
• US Class Current: 707/2
• CPC Class Codes: G06F 16/24549 Run-time optimisation

Abstract

Parameterized queries are optimized by a transformational optimizer. The optimizer produces a dynamic plan that embeds multiple plan options that may be selected to execute a particular query. Parameter distribution improves query execution efficiency and performance by exploring a sample parameter space representative of the parameter values actually used. The dynamic plans can be simplified while maintaining an acceptable level of optimality by reducing the number of plan options. The reduction is achieved by eliminating switch unions to alternatives that are close in cost. Both approaches of parameter space exploration and dynamic plan generation are deeply integrated into the query optimizer.

Claims

1. A system that facilitates dynamic plan generation, comprising:

a parameter distribution component that receives a parameterized query and selects a representative sample of parameter values in view of an entire parameter space;

a costing analysis component that calculates costs of plan options corresponding to the selected representative sample of parameter values, the plan options set forth execution of queries; and

a plan generation component that generates a dynamic plan that incorporates more than one plan option as a function of the calculated costs.

2. The system of claim 1, the parameter distribution component, the costing analysis component, and the plan generation component are integrated into a transformational optimizer.

3. The system of claim 1, the plan generation component adjusts the dynamic plan based on a balance of optimality and simplicity.

4. The system of claim 3, the plan generation component maximizes simplicity of the dynamic plan while staying within a predetermined bound of suboptimality.

5. The system of claim 3, the plan generation component receives cost information of plan options that are suboptimal from the costing analysis component and eliminates switch unions in the dynamic plan based on the cost information.

6. The system of claim 1, the parameter distribution component selects the representative sample of parameter values based on parameter values employed by users to execute queries.

7. The system of claim 1, further comprising:

a query execution component that determines a query result based on query execution using the dynamic plan.

8. A method that facilitates dynamic plan generation, comprising the following acts:

calculating costs associated with a plurality of query execution plan options that provide support for query execution; and

generating a dynamic query execution plan that integrates at least two query execution plan options based on the calculated costs.

9. The method of claim 8, further comprising randomly selecting a query execution plan option when two or more query execution plan options have one of identical and similar calculated costs.

10. The method of claim 8, further comprising tuning the dynamic plan as a function of query execution optimization and simplicity of plan structure.

11. The method of claim 10, further comprising maximizing simplicity of the dynamic plan within a user-defined bound of suboptimality.

12. The method of claim 10, further comprising retaining and using the calculated cost information for future dynamic plan generation.

13. The method of claim 10, the cost of the tuned dynamic plan is bound by:

X<

=Y+(A−

B)

where X represents the cost of the tuned dynamic plan, Y represents the cost of the dynamic plan prior to tuning, A represents the cost of a child subplan within the dynamic plan, and B represents the cost of a switch union subplan within the dynamic plan.

14. The method of claim 8, further comprising executing a parameterized query with the dynamic query execution plan.

15. The method of claim 8, further comprising extracting and optimizing for a sample of parameter values from a parameter space based on commonly used parameter values.

16. The method of claim 8, further comprising allowing a user to specify changes to the dynamic query execution plan.

17. The method of claim 8, further comprising minimizing a number of switch unions in the dynamic query execution plan for an established optimization level of the dynamic query execution plan, the number of switch unions is a function of the number of query execution plan options in the dynamic query execution plan.

18. A system that facilitates dynamic plan generation, comprising:

means for designating a representative sample of parameter values that represent an entire parameter space;

means for determining costs of plan options that correspond to the designated representative sample of parameter values, the plan options facilitate query execution; and

means for creating a dynamic plan that embeds at least two plan options based on the determined costs of plan options.

19. The system of claim 18, further comprising:

means for generating the dynamic plan within a transformational optimizer.

20. The system of claim 18, further comprising:

means for changing the dynamic plan in response to a need for simplicity over optimality.