Auto-parameterization of database queries

• US 6,356,887 B1
• Filed: 06/28/1999
• Issued: 03/12/2002
• Est. Priority Date: 06/28/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Smith, Samuel H., Peeper, Craig C., Carlin, Peter A., Berenson, Harold R., Graefe, Goetz, Galindo-Legaria, Cesar A., Ellis, Nigel R., Kalhan, Ajay
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/340,596
• Time in Patent Office: 988 Days
• Field of Search: 707/2, 707/3, 707/4, 707/5-6, 707/7, 717/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24524 Access plan code generation and invalidation; Reuse of access plans
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

An auto-parameterization process transforms a database query into a parameterized basic query form by replacing any constant values in the query with parameters. The auto-parameterization process attempts to generate a safe execution plan from the basic query form if there is currently no such plan available. A safe execution plan is defined as an execution plan that is optimal over a range of values for the parameters. If a safe execution plan can be generated, it is passed for execution, along with the constant values that were present in the query. If a safe execution plan cannot be generated, the auto-parameterization process passes a specific execution plan for execution. The safe execution plan is cached either at the time it is created or at the time it is executed. The cache is searched each time a parameterized basic query plan is generated by the auto-parameterization process. The auto-parameterization process also evaluates the query before creating the corresponding parameterized basic query form to determine if it is likely that a safe execution plan can be generated for the query.

Claims

1. A computerized method for automatically parameterizng a database query comprising:

creating a basic query form by an auto-parameterization system for the query by replacing any constant values with parameters;

attempting to create a safe execution plan for the basic query form if no safe execution plan by an auto-parameterization system currently exists; and

passing the safe execution plan and the constant values by an auto-parameterization system onto execution if the safe execution plan exists.

2. The method of claim 1, further comprising:

determining if the query is likely to have a safe execution plan; and

creating the basic query form if the query is determined to likely to have a safe execution plan.

3. The method of claim 1, wherein determining if the query is likely to have a safe execution plan comprises:

performing syntax analysis on the query.

4. The method of claim 1, comprising:

creating a unique name for the basic query form; and

storing the safe execution plan in a cache under the unique name.

5. The method of claim 4, wherein the safe execution plan is stored in the cache when it is created.

6. The method of claim 4, wherein the safe execution plan is stored in the cache when it is executed.

7. The method of claim 4, wherein the unique name is based on elements in the basic query form.

8. The method of claim 4, further comprising:

determining if a current safe execution plan exists by searching the cache using the unique name for the basic query form.

9. The method of claim 4, further comprising:

searching the cache using the unique name for the basic query form before executing the safe execution plan; and

creating a specific execution plan if the safe execution plan does not exist in the cache.

10. The method of claim 4, further comprising:

removing the safe execution plan from the cache when it is no longer optimal over a range of values for the parameters.

11. The method of claim 4, further comprising:

removing the safe execution plan from the cache when an age indicator associated with the safe execution plan satisfied pre-determined criteria.

12. The method of claim 1, wherein attempting to create the safe execution plan comprises:

generating an optimal execution plan for the basic query form;

analyzing the optimal execution plan against a range of values for the parameters; and

designating the optimal execution plan as the safe execution plan if the evaluation shows it is optimal over the range of values.

13. The method of claim 12, wherein the range of values is based on the constant values in the query.

14. The method of claim 1, wherein the execution plan comprises:

a query plan; and

an execution context.

15. The method of claim 1, wherein the elements are performed in the order recited.

16. The method of claim 1, further comprising passing a specific execution plan onto execution if the safe execution plan does not exist.

17. A computer-readable medium having computer-executable modules stored thereon, the modules comprising:

a syntax analysis module that determines if query is likely to generate a safe execution plan;

an auto-parameterization driver module that creates a parameterized basic query form from the query and further passes any safe execution plan generated from the parameterized basic query form onto an execution module; and

a safety analysis module that evaluates whether the execution plan generated from the parameterized basic query form is safe.

18. The computer-readable medium of claim 17, further comprising:

a parser module that parses the query into a query tree, submits the query tree to the syntax analysis module for analysis, and further submits the query tree to an optimizer module if the query is not likely to generate a safe execution plan.

19. The computer-readable medium of claim 17, further comprising:

a parser module that parses the query into a query tree, submits the query tree to the syntax analysis module for analysis, and further submits the query tree to a normalizer module if the query is not likely to generate a safe execution plan.

20. The computer-readable medium of claim 19, wherein the normalizer module normalizes the query tree and submits the normalized query tree to the syntax analysis module for analysis, and further submits the query tree to an optimizer module if the query is not likely to generate a safe execution plan.

21. The computer-readable medium of claim 17, further comprising;

an optimizer module that generates the execution plan from the parameterized basic query form.

22. The computer-readable medium of claim 21, wherein the optimizer module generates a specific execution plan for the query if the safety analysis module evaluates the execution plan generated from the parameterized basic query form as unsafe, and wherein the auto-parameterization driver module submits the specific execution plan to the execution module.

23. The computer-readable medium of claim 17, wherein the safety analysis module evaluates the execution plan as safe if the execution plan is optimal over a range of parameter values.

24. The computer-readable medium of claim 17, wherein the auto-parameterization driver module stores any safe execution plan generated from the parameterized basic query form in a cache and searches the cache for the safe execution plan each time it creates the same parameterized basic query form.

25. The computer-readable medium of claim 24, further comprising an execution module that searches the cache for the safe execution plan when it receives the safe execution plan from the auto-parameterization driver module, and further causes a specific execution plan for the query to be generated when the safe execution plan is not found in the cache.

26. The computer-readable medium of claim 17, further comprising an execution module that stores the safe execution plan in a cache when the plan is executed and wherein the auto-parameterization driver searches the cache for the safe execution plan each time it creates the same parameterized basic query form.

27. A computerized system comprising:

a processing unit;

a system memory coupled to the processing unit through a system bus;

a computer-readable medium coupled to the processing unit through a system bus; and

an auto-parameterization sub-system executed from the computer-readable medium by the processing unit, wherein the auto-parameterization subsystem causes the processing unit to generate a parameterized basic query form from a query, to generate an execution plan from the parameterized basic query form, to evaluate the execution plan for safety, and to submit the execution plan for execution if it is evaluated as safe.

28. The computerized system of claim 27, wherein the auto-parameterization subsystem further causes the processing unit to store the execution plan in the system memory if it is evaluated as safe, and to search the system memory for the execution each time the processing unit generates the parameterized basic query form.

29. The computerized system of claim 28, wherein the auto-parameterized subsystem causes the processing unit to remove the execution plan from the system memory under certain conditions.

30. The computerized system of claim 29, wherein the certain conditions are selected from the group consisting of:

alteration to a schema structure accessed by the query;

modification of statistics used to generate the execution plan; and

satisfaction of pre-determined criteria by an age indicator associated with the execution plan.