Patent US3955769A successfully refreshed from Google Patents.
Patent CH409087A successfully refreshed from Google Patents.
Patent US6356887B1 successfully refreshed from Google Patents.
US6356887B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Auto-parameterization of database queries
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1999-06-28
•
Granted: 2002-03-12
•
Expires: 2019-06-28
Abstract
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.
Inventors
- 👤 Harold R. Berenson
- 👤 Peter A. Carlin
- 👤 Nigel R. Ellis
- 👤 Cesar A. Galindo-Legaria
- 👤 Goetz Graefe
- 👤 Ajay Kalhan
- 👤 Craig C. Peeper
- 👤 Samuel H. Smith
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 18:02
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2452; G06F16/24524; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
74 words
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.
Claim 2
Dependent Claim
74 words
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.
Claim 3
Dependent Claim
39 words
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.
Claim 4
Dependent Claim
26 words
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.
Claim 5
Dependent Claim
29 words
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.
Claim 6
Dependent Claim
20 words
The method of claim 4 , wherein the safe execution plan is stored in the cache when it is created.
Claim 7
Dependent Claim
20 words
The method of claim 4 , wherein the safe execution plan is stored in the cache when it is executed.
Claim 8
Dependent Claim
19 words
The method of claim 4 , wherein the unique name is based on elements in the basic query form.
Claim 9
Dependent Claim
29 words
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.
Claim 10
Dependent Claim
43 words
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.
Claim 11
Dependent Claim
30 words
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.
Claim 12
Dependent Claim
29 words
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.
Claim 13
Dependent Claim
61 words
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.
Claim 14
Dependent Claim
20 words
The method of claim 12 , wherein the range of values is based on the constant values in the query.
Claim 15
Dependent Claim
18 words
The method of claim 1 , wherein the execution plan comprises: a query plan; and an execution context.
Claim 16
Dependent Claim
15 words
The method of claim 1 , wherein the elements are performed in the order recited.
Claim 17
Dependent Claim
23 words
The method of claim 1 , further comprising passing a specific execution plan onto execution if the safe execution plan does not exist.
Claim 18
Dependent Claim
79 words
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.
Claim 19
Dependent Claim
79 words
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.
Claim 20
Dependent Claim
53 words
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.
Claim 21
Dependent Claim
53 words
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.
Claim 22
Dependent Claim
50 words
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.
Claim 23
Dependent Claim
23 words
The computer-readable medium of claim 17 , further comprising; an optimizer module that generates the execution plan from the parameterized basic query form.
Claim 24
Dependent Claim
52 words
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.
Claim 25
Dependent Claim
30 words
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.
Claim 26
Dependent Claim
46 words
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.
Claim 27
Dependent Claim
57 words
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.
Claim 28
Dependent Claim
49 words
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.
Claim 29
Dependent Claim
94 words
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.
Claim 30
Dependent Claim
94 words
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.
Claim 31
Dependent Claim
51 words
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.
Claim 32
Dependent Claim
27 words
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.
Claim 33
Dependent Claim
50 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-03-11 | 2005-09-10 | 2006-03-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-03-11 | 2009-09-10 | 2010-03-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-03-11 | 2013-09-10 | 2014-03-12 | $7700.00 | Window Closed / Lapsed |