Optimizing parameterized queries in a relational database management system

• US 8,032,522 B2
• Filed: 08/25/2006
• Issued: 10/04/2011
• Est. Priority Date: 08/25/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhou, Jingren, Larson, Per-Ake, Goldstein, Jonathan D.
• Primary Examiner(s): Betit; Jacob F
• Assistant Examiner(s): Truong; Dennis
• Application Number:
  US11/467,377
• Publication Number:
  US 20080052266A1
• Time in Patent Office: 1,866 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/713, 707/718, 707/719, 707999001-999005
• US Class Current: 707/718
• 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 for generating a dynamic plan comprising:

a processor;

and memory in communication with the processor, the memory comprising;

a parameter distribution component that receives a parameterized query and selects a representative sample of parameter values based on parameter values employed by users to execute queries 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 employed by users to execute queries, the plan options set forth execution of queries; and

a plan generation component that;

(i) generates the dynamic plan, the dynamic plan generated by incorporating at least two plan options as a function of the calculated costs of plan options corresponding to the selected representative sample of parameter values employed by users to execute queries, the at least two plan options comprising a first plan invoked for relatively higher parameter values and a second plan invoked for relatively lower parameter values, (ii) adjusts the dynamic plan based on a balance of optimality and simplicity, and (iii) maximizes simplicity of the dynamic plan while staying within a predetermined bound of suboptimality.

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 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.

4. The system of claim 1, further comprising:

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

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

extracting and optimizing for a sample of parameter values from a parameter space based on commonly used parameter values employed by users to execute queries;

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

generating a dynamic query execution plan that integrates at least two query execution plan options based on the calculated costs of plan options corresponding to the selected representative sample of parameter values employed by users to execute queries;

tuning the dynamic plan as a function of query execution optimization and simplicity of plan structure, wherein 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 prior to tuning, and B represents the cost of a switch union subplan within the dynamic plan prior to tuning; and

executing a parameterized query with the dynamic query execution plan.

6. The method of claim 5, 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.

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

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

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

10. The method of claim 5, 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.