Patent US6529901B1 successfully refreshed from Google Patents.
US6529901B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Automating statistics management for query optimizers
Assignee: Microsoft Technology Licensing LLC
•
Filing: 2000-02-25
•
Granted: 2003-03-04
•
Expires: 2020-02-25
Abstract
Abstract In a database system, a method for determining a set of essential statistics. A set of potentially relevant, but unconstructed, statistics for a user query comprising a plurality of operators is compiled. A first value is assigned to the unconstructed statistics and a first projected query cost is computed for the query wherein the unconstructed statistics have the first value. A second value is assigned to the unconstructed statistics and a second projected query cost is computed for the query wherein the unconstructed statistics have the second value. The first and second projected query costs are compared and the determination of essential statistics is discontinued if the first and second projected query costs are equivalent. If the first and second projected query costs are not equivalent, an unconstructed statistic is selected to build and process is repeated until the first and second projected query costs are equivalent or all the unconstructed potentially relevant statistics have been constructed. Statistics which do not sufficiently impact a query plan may be added to a drop list for elimination.
Inventors
- 👤 Surajit Chaudhuri
- 👤 Vivek Narasayya
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 08:47
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2458; G06F16/2462; G06F16/2453; G06F16/24534; G06F16/24542; G06F16/24545; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99941; Y10S707/99943
Claims Analysis
Total Claims: 84
Claim 1
Independent Claim
90 words
In a database system, a method for determining a set of statistics with respect to a query workload comprising the steps of: a) compiling a set of potentially relevant statistics with respect to a query; b) calculating a plurality of projected query plans by assigning a variety of predetermined selectivity values to at least one of the potentially relevant statistics, developing an execution plan for each of the selectivity value assignments and evaluating its cost; and c) determining a set of statistics based on the plurality of projected query plans.
Claim 2
Dependent Claim
90 words
In a database system, a method for determining a set of statistics with respect to a query workload comprising the steps of: a) compiling a set of potentially relevant statistics with respect to a query; b) calculating a plurality of projected query plans by assigning a variety of predetermined selectivity values to at least one of the potentially relevant statistics, developing an execution plan for each of the selectivity value assignments and evaluating its cost; and c) determining a set of statistics based on the plurality of projected query plans.
Claim 3
Dependent Claim
40 words
The method of claim 1 wherein the step of calculating a plurality of plans comprises the step of associating a cost with the plan and the step of determining a set of statistics is performed based on the associated cost.
Claim 4
Dependent Claim
49 words
The method of claim 1 wherein the step of calculating a plurality of projected query plans is performed by assigning at least two distinct selectivity values between x and 1-x to at least one of the potentially relevant statistics where x is a relatively small number less than 1.0.
Claim 5
Dependent Claim
45 words
The method of claim 1 wherein the step of determining a set of statistics is performed by comparing the plurality of projected query plans and determining statistics whose value has a sufficiently small impact on the value of the projected query plans to be non-essential.
Claim 6
Dependent Claim
19 words
The method of claim 1 further comprising the step of storing statistics determined to be non-essential for later evaluation.
Claim 7
Dependent Claim
18 words
The method of claim 5 wherein the stored non-essential statistics are stored until an elimination criterion is met.
Claim 8
Dependent Claim
14 words
The method of claim 6 wherein the elimination criterion is a maximum maintenance cost.
Claim 9
Dependent Claim
159 words
In a database system, a method for evaluating the utility of at least one candidate statistic in the estimation of the selectivity of a query, comprising the steps of: a) generating a first execution plan based on an existing set of database statistics; b) assigning a first selectivity value to the at least one candidate statistic; c) determining a first projected query plan by executing the execution plan with the at least one candidate statistic having the first selectivity value; d) assigning a second selectivity value to the at least one candidate statistic; e) determining a second projected query plan by executing the execution plan with the at least one candidate statistic having the second selectivity value; f) comparing the first projected query plan to the second projected query plan; and g) assigning a degree of utility to the at least one candidate statistic based on the results of the comparison between the first and second projected query plans.
Claim 10
Dependent Claim
159 words
In a database system, a method for evaluating the utility of at least one candidate statistic in the estimation of the selectivity of a query, comprising the steps of: a) generating a first execution plan based on an existing set of database statistics; b) assigning a first selectivity value to the at least one candidate statistic; c) determining a first projected query plan by executing the execution plan with the at least one candidate statistic having the first selectivity value; d) assigning a second selectivity value to the at least one candidate statistic; e) determining a second projected query plan by executing the execution plan with the at least one candidate statistic having the second selectivity value; f) comparing the first projected query plan to the second projected query plan; and g) assigning a degree of utility to the at least one candidate statistic based on the results of the comparison between the first and second projected query plans.
Claim 11
Dependent Claim
49 words
The method of claim 8 wherein the steps of determining a first and second projected query plan comprise the step of assigning an associated cost to each plan and the step of comparing the first and second plans comprises comparing the associated costs of the first and second plans.
Claim 12
Dependent Claim
31 words
The method of claim 8 further comprising the step of adding candidate statistics having more than a predetermined degree of utility to a set of statistics maintained by the database system.
Claim 13
Dependent Claim
31 words
The method of claim 8 further comprising the step of removing candidate statistics having less than a predetermined degree of utility from a set of statistics maintained by the database system.
Claim 14
Dependent Claim
34 words
The method of claim 8 wherein a low degree of utility is assigned to the at least one candidate statistics if the first projected query plan and the second projected query plan are equivalent.
Claim 15
Dependent Claim
35 words
The method of claim 8 wherein a high degree of utility is assigned to the at least one candidate statistic if the first projected query plan and the second projected query plan are not equivalent.
Claim 16
Dependent Claim
86 words
The method of claim 8 further comprising the steps of: a) adding a statistic having a requisite degree of utility to the existing set of database statistics to form an updated set of statistics; b) generating a second execution plan based on the updated set of database statistics; c) comparing the first execution plan to the second execution plan; and d) adding the statistic having the requisite degree of utility to set of statistics to be dropped if the first and second execution plans are equivalent.
Claim 17
Dependent Claim
25 words
The method of claim 14 wherein statistics within the set of statistics to be dropped are maintained until a predetermined elimination criterion has been met.
Claim 18
Dependent Claim
15 words
The method of claim 15 wherein the elimination criteria is a maximum cost of maintenance.
Claim 19
Dependent Claim
195 words
In a database system, a method for determining a set of statistics with respect to a query workload comprising the steps of: a) compiling a set of potentially relevant statistics for a user query comprising a plurality of operators; b) determining which potentially relevant statistics have not yet been constructed by the database system; c) assigning a first selectivity value to the unconstructed statistics; d) computing a first projected query plan for the query wherein the unconstructed statistics have the first value; e) assigning a second selectivity value to the unconstructed statistics; f) computing a second projected query plan for the query wherein the unconstructed statistics have the second value; g) comparing the first and second projected query plans; h) discontinuing the determination of a set of statistics if the first and second projected query plans are equivalent; i) selecting an unconstructed statistic to build if the first and second projected query plans are not equivalent; j) building the unconstructed statistic selected in step (i); and k) repeating steps (b) through (j) until the first and projected query plans are equivalent or all the unconstructed potentially relevant statistics compiled in step (a) have been constructed.
Claim 20
Dependent Claim
195 words
In a database system, a method for determining a set of statistics with respect to a query workload comprising the steps of: a) compiling a set of potentially relevant statistics for a user query comprising a plurality of operators; b) determining which potentially relevant statistics have not yet been constructed by the database system; c) assigning a first selectivity value to the unconstructed statistics; d) computing a first projected query plan for the query wherein the unconstructed statistics have the first value; e) assigning a second selectivity value to the unconstructed statistics; f) computing a second projected query plan for the query wherein the unconstructed statistics have the second value; g) comparing the first and second projected query plans; h) discontinuing the determination of a set of statistics if the first and second projected query plans are equivalent; i) selecting an unconstructed statistic to build if the first and second projected query plans are not equivalent; j) building the unconstructed statistic selected in step (i); and k) repeating steps (b) through (j) until the first and projected query plans are equivalent or all the unconstructed potentially relevant statistics compiled in step (a) have been constructed.
Claim 21
Dependent Claim
35 words
The method of claim 17 wherein the step of selecting an unconstructed statistic to build is performed by selecting an unconstructed statistic that is relevant for at least one relatively expensive operator in the query.
Claim 22
Dependent Claim
40 words
The method of claim 17 wherein the steps of computing first and second projected query plan comprise associating a cost with each plan and the steps (h), (i), and (k) are performed based on the costs associated with each plan.
Claim 23
Dependent Claim
217 words
In a database system, a method for providing automated database statistics management for creating and maintaining a set of essential statistics with respect to a query workload comprising the steps of: a) creating an initial set of statistics by i) compiling a set of potentially relevant statistics with respect to a query; ii) calculating a plurality of projected query plans by assigning a variety of predetermined selectivity values to at least one of the potentially relevant statistics, developing an execution plan for each of the selectivity value assignments and evaluating its cost; and iii) determining a set of statistics based on the plurality of projected query plans; b) eliminating any non-essential statistics by i) identifying a subset of the initial set of statistics equivalent to the initial set of statistics with respect to each query, wherein the subset of statistics is equivalent to the initial set of statistics: A) if an execution plan for each query using the subset of statistics is the same as an execution plan for that query using the initial set of statistics, and/or B) if a cost estimate to execute each query against the database using the subset of statistics is within a predetermined amount of a cost estimate to execute that query against the database using the initial set of statistics.
Claim 24
Dependent Claim
217 words
In a database system, a method for providing automated database statistics management for creating and maintaining a set of essential statistics with respect to a query workload comprising the steps of: a) creating an initial set of statistics by i) compiling a set of potentially relevant statistics with respect to a query; ii) calculating a plurality of projected query plans by assigning a variety of predetermined selectivity values to at least one of the potentially relevant statistics, developing an execution plan for each of the selectivity value assignments and evaluating its cost; and iii) determining a set of statistics based on the plurality of projected query plans; b) eliminating any non-essential statistics by i) identifying a subset of the initial set of statistics equivalent to the initial set of statistics with respect to each query, wherein the subset of statistics is equivalent to the initial set of statistics: A) if an execution plan for each query using the subset of statistics is the same as an execution plan for that query using the initial set of statistics, and/or B) if a cost estimate to execute each query against the database using the subset of statistics is within a predetermined amount of a cost estimate to execute that query against the database using the initial set of statistics.
Claim 25
Dependent Claim
20 words
The method of claim 20 wherein step (a) is performed in real time after each query in the query workload.
Claim 26
Dependent Claim
28 words
The method of claim 20 wherein the query workload comprises a plurality of previously executed queries and steps (a) and (b) are performed off-line on the query workload.
Claim 27
Dependent Claim
40 words
The method of claim 20 wherein step of creating an initial set of statistics is performed by assigning a probability of creation to a statistic based on the proportional amount of the query workload to which it is potentially relevant.
Claim 28
Dependent Claim
37 words
The method claim 20 wherein the step of calculating a plurality of projected query plans comprises associating a cost with each plan and the set of statistics is determined based on the cost associated with each plan.
Claim 29
Dependent Claim
91 words
A computer readable medium having computer-executable instructions for determining a set of statistics with respect to a query workload comprising the steps of: a) compiling a set of potentially relevant statistics with respect to a query, b) calculating a plurality of projected query plans by assigning a variety of predetermined selectivity values to at least one of the potentially relevant statistics, developing an execution plan for each of the selectivity value assignments and evaluating its cost; and c) determning a set of statistics based on the plurality of projected query plans.
Claim 30
Dependent Claim
91 words
A computer readable medium having computer-executable instructions for determining a set of statistics with respect to a query workload comprising the steps of: a) compiling a set of potentially relevant statistics with respect to a query, b) calculating a plurality of projected query plans by assigning a variety of predetermined selectivity values to at least one of the potentially relevant statistics, developing an execution plan for each of the selectivity value assignments and evaluating its cost; and c) determning a set of statistics based on the plurality of projected query plans.
Claim 31
Dependent Claim
42 words
The computer readable medium of claim 25 wherein the step of calculating a plurality of plans comprises the step of associating a cost to the plan and the step of determining a set of statistics is performed based on the associated cost.
Claim 32
Dependent Claim
50 words
The computer readable medium of claim 25 wherein the step of calculating a plurality of projected query plans is performed by assigning at least two distinct values between x and 1-x where x is a relatively small number less than 1.0 to at least one of the potentially relevant statistics.
Claim 33
Dependent Claim
47 words
The computer readable medium of claim 25 wherein the step of determining a set of statistics is performed by comparing the plurality of projected query plans and determining statistics whose value have a sufficiently small impact on the value of the projected query plans to be non-essential.
Claim 34
Dependent Claim
21 words
The computer readable medium of claim 25 further comprising the step of storing statistics determined to be non-essential for later evaluation.
Claim 35
Dependent Claim
20 words
The computer readable medium of claim 29 wherein the stored non-essential statistics are stored until an elimination criterion is met.
Claim 36
Dependent Claim
16 words
The computer readable medium of claim 30 wherein the elimination criterion is a maximum maintenance cost.
Claim 37
Dependent Claim
158 words
A computer readable medium having computer-executable instructions for evaluating the utility of at least one candidate statistic in the estimation of the selectivity of a query, comprising the steps of: a) generating a first execution plan including the at least one candidate; b) assigning a first selectivity value to the at least one candidate statistic; c) determining a first projected query plan by executing the execution plan with the at least one candidate statistic having the first selectivity value; d) assigning a second selectivity value to the at least one candidate statistic; e) determining a second projected query plan by executing the execution plan with the at least one candidate statistic having the second selectivity value; f) comparing the first projected query plan to the second projected query plan; and g) assigning a degree of utility to the at least one candidate statistic based on the results of the comparison between the first and second projected query plans.
Claim 38
Dependent Claim
158 words
A computer readable medium having computer-executable instructions for evaluating the utility of at least one candidate statistic in the estimation of the selectivity of a query, comprising the steps of: a) generating a first execution plan including the at least one candidate; b) assigning a first selectivity value to the at least one candidate statistic; c) determining a first projected query plan by executing the execution plan with the at least one candidate statistic having the first selectivity value; d) assigning a second selectivity value to the at least one candidate statistic; e) determining a second projected query plan by executing the execution plan with the at least one candidate statistic having the second selectivity value; f) comparing the first projected query plan to the second projected query plan; and g) assigning a degree of utility to the at least one candidate statistic based on the results of the comparison between the first and second projected query plans.
Claim 39
Dependent Claim
51 words
The computer readable medium of claim 32 wherein the steps of determining a first and second projected query plan comprise the step of assigning an associated cost to each plan and the step of comparing the first and second plans comprises comparing the associated costs of the first and second plans.
Claim 40
Dependent Claim
33 words
The computer readable medium of claim 32 further comprising the step of adding candidate statistics having more than a predetermined degree of utility to a set of statistics maintained by the database system.
Claim 41
Dependent Claim
33 words
The computer readable medium of claim 32 further comprising the step of removing candidate statistics having less than a predetermined degree of utility from a set of statistics maintained by the database system.
Claim 42
Dependent Claim
36 words
The computer readable medium of claim 32 wherein a low degree of utility is assigned to the at least one candidate statistics if the first projected query plan and the second projected query plan are equivalent.
Claim 43
Dependent Claim
37 words
The computer readable medium of claim 32 wherein a high degree of utility is assigned to the at least one candidate statistic if the first projected query plan and the second projected query plan are not equivalent.
Claim 44
Dependent Claim
88 words
The computer readable medium of claim 32 further comprising the steps of: a) adding a statistic having a requisite degree of utility to the existing set of database statistics to form an updated set of statistics; b) generating a second execution plan based on the updated set of database statistics; c) comparing the first execution plan to the second execution plan; and d) adding the statistic having the requisite degree of utility to set of statistics to be dropped if the first and second execution plans are equivalent.
Claim 45
Dependent Claim
27 words
The computer readable medium of claim 34 wherein statistics within the set of statistics to be dropped are maintained until a predetermined elimination criterion has been met.
Claim 46
Dependent Claim
17 words
The computer readable medium of claim 39 wherein the elimination criteria is a maximum cost of maintenance.
Claim 47
Dependent Claim
201 words
A computer readable medium having computer-executable instructions for determining a set of statistics with respect to a query workload comprising the steps of: a) compiling a set of potentially relevant statistics for a user query comprising a plurality of operators; b) determining which potentially relevant statistics have not yet been constructed by the database system; c) assigning a first selectivity value to the unconstructed statistics; d) computing a first projected query plan for the query wherein the unconstructed statistics have the first value; e) assigning a second selectivity value to the unconstructed statistics; f) computing a second projected query plan for the query wherein the unconstructed statistics have the second value; g) comparing the first and second projected query plans; h) discontinuing the determination of a set of statistics if the first and second projected query plans are equivalent; i) selecting an unconstructed statistic to build if the first and second projected query plans are not equivalent; j) building the unconstructed statistic selected in step (i); and k) repeating steps (b) through (j) until the first and projected query plans are similar to within the threshold amount or all the unconstructed potentially relevant statistics compiled in step (a) have been constructed.
Claim 48
Dependent Claim
201 words
A computer readable medium having computer-executable instructions for determining a set of statistics with respect to a query workload comprising the steps of: a) compiling a set of potentially relevant statistics for a user query comprising a plurality of operators; b) determining which potentially relevant statistics have not yet been constructed by the database system; c) assigning a first selectivity value to the unconstructed statistics; d) computing a first projected query plan for the query wherein the unconstructed statistics have the first value; e) assigning a second selectivity value to the unconstructed statistics; f) computing a second projected query plan for the query wherein the unconstructed statistics have the second value; g) comparing the first and second projected query plans; h) discontinuing the determination of a set of statistics if the first and second projected query plans are equivalent; i) selecting an unconstructed statistic to build if the first and second projected query plans are not equivalent; j) building the unconstructed statistic selected in step (i); and k) repeating steps (b) through (j) until the first and projected query plans are similar to within the threshold amount or all the unconstructed potentially relevant statistics compiled in step (a) have been constructed.
Claim 49
Dependent Claim
37 words
The computer readable medium of claim 41 wherein the step of selecting an unconstructed statistic to build is performed by selecting an unconstructed statistic that is relevant for at least one relatively expensive operator in the query.
Claim 50
Dependent Claim
42 words
The computer readable medium of claim 41 wherein the steps of computing first and second projected query plan comprise associating a cost with each plan and the steps (h), (i), and (k) are performed based on the costs associated with each plan.
Claim 51
Dependent Claim
218 words
A computer readable medium having computer-executable instructions for providing automated database statistics management for creating and maintaining a set of essential statistics with respect to a query workload comprising the steps of: a) creating an initial set of statistics by i) compiling a set of potentially relevant statistics with respect to a query; ii) calculating a plurality of projected query plans by assigning a variety of selectivity values to at least one of the potentially relevant statistics, developing an execution plan for each of the selectivity value assignments and evaluating its cost; and iii) determining a set of statistics based on the plurality of projected query plans; and b) eliminating any non-essential statistics by i) identifying a subset of the initial set of statistics equivalent to the initial set of statistics with respect to each query, wherein the subset of statistics is equivalent to the initial set of statistics: A) if an execution plan for each query using the subset of statistics is the same as an execution plan for that query using the initial set of statistics, and/or B) if a cost estimate to execute each query against the database using the subset of statistics is within a predetermined amount of a cost estimate to execute that query against the database using the initial set of statistics.
Claim 52
Dependent Claim
218 words
A computer readable medium having computer-executable instructions for providing automated database statistics management for creating and maintaining a set of essential statistics with respect to a query workload comprising the steps of: a) creating an initial set of statistics by i) compiling a set of potentially relevant statistics with respect to a query; ii) calculating a plurality of projected query plans by assigning a variety of selectivity values to at least one of the potentially relevant statistics, developing an execution plan for each of the selectivity value assignments and evaluating its cost; and iii) determining a set of statistics based on the plurality of projected query plans; and b) eliminating any non-essential statistics by i) identifying a subset of the initial set of statistics equivalent to the initial set of statistics with respect to each query, wherein the subset of statistics is equivalent to the initial set of statistics: A) if an execution plan for each query using the subset of statistics is the same as an execution plan for that query using the initial set of statistics, and/or B) if a cost estimate to execute each query against the database using the subset of statistics is within a predetermined amount of a cost estimate to execute that query against the database using the initial set of statistics.
Claim 53
Dependent Claim
22 words
The computer readable medium of claim 44 wherein step (a) is performed in real time after each query in the query workload.
Claim 54
Dependent Claim
30 words
The computer readable medium of claim 44 wherein the query workload comprises a plurality of previously executed queries and steps (a) and (b) are performed off-line on the query workload.
Claim 55
Dependent Claim
42 words
The computer readable medium of claim 44 wherein step of creating an initial set of statistics is performed by assigning a probability of creation to a statistic based on the proportional amount of the query workload to which it is potentially relevant.
Claim 56
Dependent Claim
40 words
The computer readable medium of claim 44 wherein the step of calculating a plurality of projected query plans comprises associating a cost with each plan and the set of statistics is determined based on the cost associated with each plan.
Claim 57
Dependent Claim
93 words
In a database system, an apparatus for determining a set of statistics with respect to a query workload comprising: a) means for compiling a set of potentially relevant statistics with respect to a query; b) means for calculating a plurality of projected query plans by assigning a variety of predetermined selectivity values to at least one of the potentially relevant statistics, developing an execution plan for each of the selectivity value assignments and evaluating its cost; and c) means for determining a set of statistics based on the plurality of projected query plans.
Claim 58
Dependent Claim
93 words
In a database system, an apparatus for determining a set of statistics with respect to a query workload comprising: a) means for compiling a set of potentially relevant statistics with respect to a query; b) means for calculating a plurality of projected query plans by assigning a variety of predetermined selectivity values to at least one of the potentially relevant statistics, developing an execution plan for each of the selectivity value assignments and evaluating its cost; and c) means for determining a set of statistics based on the plurality of projected query plans.
Claim 59
Dependent Claim
40 words
The apparatus of claim 49 wherein the means for calculating a plurality of plans comprises a means for associating a cost to the plan and the means for determining a set of statistics bases the determination on the associated cost.
Claim 60
Dependent Claim
44 words
The apparatus of claim 49 wherein the means for calculating a plurality of projected query costs assigns at least distinct values between x and 1-x where x is a relatively small number less than 1.0 to at least one of the potentially relevant statistics.
Claim 61
Dependent Claim
41 words
The apparatus of claim 49 wherein the means for determining a set of statistics compares the plurality of projected query plans and determines statistics whose value has a sufficiently small impact on the value of projected query plans to be non-essential.
Claim 62
Dependent Claim
18 words
The apparatus of claim 49 further comprising means for storing statistics determined to be non-essential for later evaluation.
Claim 63
Dependent Claim
22 words
The apparatus of claim 53 wherein the means for storing non-essential statistics stores the non-essential statistics until an elimination criterion is met.
Claim 64
Dependent Claim
14 words
The apparatus of claim 54 wherein the elimination criterion is a maximum maintenance cost.
Claim 65
Dependent Claim
166 words
In a database system, an apparatus for evaluating the utility of at least one candidate statistic in the estimation of the selectivity of a query, comprising: a) means for generating an execution based on an existing set of database statistics; b) means for assigning a first selectivity value to the at least one candidate statistic; c) means for determining a first projected query plan by executing the estimation plan with the at least one candidate statistic having the first value; d) means for assigning a second selectivity value to the at least one candidate statistic; e) means for determining a second projected query plan by executing the estimation plan with the at least one candidate statistic having the second selectivity value; f) means for comparing the first projected query plan to the second projected query plan; and g) means for assigning a degree of utility to the at least one candidate statistic based on the results of the comparison between the first and projected query plans.
Claim 66
Dependent Claim
166 words
In a database system, an apparatus for evaluating the utility of at least one candidate statistic in the estimation of the selectivity of a query, comprising: a) means for generating an execution based on an existing set of database statistics; b) means for assigning a first selectivity value to the at least one candidate statistic; c) means for determining a first projected query plan by executing the estimation plan with the at least one candidate statistic having the first value; d) means for assigning a second selectivity value to the at least one candidate statistic; e) means for determining a second projected query plan by executing the estimation plan with the at least one candidate statistic having the second selectivity value; f) means for comparing the first projected query plan to the second projected query plan; and g) means for assigning a degree of utility to the at least one candidate statistic based on the results of the comparison between the first and projected query plans.
Claim 67
Dependent Claim
45 words
The apparatus of claim 56 wherein the means for determining the first and second projected query plans assigns an associated cost to each plan and the means for comparing the first and second query plans compares the associated costs of the first and second plans.
Claim 68
Dependent Claim
30 words
The apparatus of claim 56 further comprising means for adding candidate statistics having more than a predetermined degree of utility to a set of statistics maintained by the database system.
Claim 69
Dependent Claim
30 words
The apparatus of claim 56 further comprising means for removing candidate statistics having less than a predetermined degree of utility from a set of statistics maintained by the database system.
Claim 70
Dependent Claim
34 words
The apparatus of claim 56 wherein a low degree of utility is assigned to the at least one candidate statistics if the first projected query plan and the second projected query plan are equivalent.
Claim 71
Dependent Claim
35 words
The apparatus of claim 56 wherein a high degree of utility is assigned to the at least one candidate statistic if the first projected query plan and the second projected query plan are not equivalent.
Claim 72
Dependent Claim
91 words
The apparatus of claim 56 further comprising: a) means for adding a statistic having a requisite degree of utility to the existing set of database statistics to form an updated set of statistics; b) means for generating a second execution plan based on the updated set of database statistics; c) means for comparing the first execution plan to the second execution plan; and d) means for adding the statistic having the requisite degree of utility to set of statistics to be dropped if the first and second execution plans are equivalent.
Claim 73
Dependent Claim
24 words
The apparatus of claim 62 wherein within the set of statistics to be dropped are maintained until a predetermined elimination criterion has been met.
Claim 74
Dependent Claim
15 words
The method of claim 63 wherein the elimination criteria is a maximum cost of maintenance.
Claim 75
Dependent Claim
217 words
In a database system, an apparatus for determining a set of statistics with respect to a query workload comprising: a) means for compiling a set of potentially relevant statistics for a user query comprising a plurality of operators; b) means for determining which potentially relevant statistics have not yet been constructed by the database system; c) means for assigning a first selectivity value to the unconstructed statistics; d) means for computing a first projected query plan for the query wherein the unconstructed statistics have the first selectivity value; e) means for assigning a second selectivity value to the unconstructed statistics; f) means for computing a second projected query plan for the query wherein the unconstructed statistics have the second selectivity value; g) means for comparing the first and second projected query plans; h) means for discontinuing the determination of a set of statistics if the first and second projected query plans are equivalent; i) means for selecting an unconstructed statistic to build if the first and second projected query plans are not equivalent; j) means for building the unconstructed statistic selected in step (i); and k) means for repeating steps (b) through (j) until the first and second projected query plans are equivalent or all the unconstructed potentially relevant statistics compiled in step (a) have been constructed.
Claim 76
Dependent Claim
217 words
In a database system, an apparatus for determining a set of statistics with respect to a query workload comprising: a) means for compiling a set of potentially relevant statistics for a user query comprising a plurality of operators; b) means for determining which potentially relevant statistics have not yet been constructed by the database system; c) means for assigning a first selectivity value to the unconstructed statistics; d) means for computing a first projected query plan for the query wherein the unconstructed statistics have the first selectivity value; e) means for assigning a second selectivity value to the unconstructed statistics; f) means for computing a second projected query plan for the query wherein the unconstructed statistics have the second selectivity value; g) means for comparing the first and second projected query plans; h) means for discontinuing the determination of a set of statistics if the first and second projected query plans are equivalent; i) means for selecting an unconstructed statistic to build if the first and second projected query plans are not equivalent; j) means for building the unconstructed statistic selected in step (i); and k) means for repeating steps (b) through (j) until the first and second projected query plans are equivalent or all the unconstructed potentially relevant statistics compiled in step (a) have been constructed.
Claim 77
Dependent Claim
32 words
The apparatus of claim 65 wherein the means for selecting an unconstructed statistic to build selects an unconstructed statistic that is relevant for at least one relatively expensive operator in the query.
Claim 78
Dependent Claim
34 words
The apparatus of claim 65 wherein the means for computing first and second projected query plans associates a cost with each plan and the means of (h), (i), and (k) use the associated costs.
Claim 79
Dependent Claim
224 words
In a database system, an apparatus for providing automated database statistics management for creating and maintaining a set of essential statistics with respect to a query workload comprising: a) means for creating an initial set of statistics by i) means for compiling a set of potentially relevant statistics with respect to a query; ii) means for calculating a plurality of projected query plans by assigning a variety of selectivity values to at least one of the potentially relevant statistics, developing an execution plan for each of the selectivity value assignments and evaluating its cost; and iii) means for determining a set of statistics based on the plurality of projected query plans; and b) means for eliminating any non-essential statistics by i) identifying a subset of the initial set of statistics equivalent to the initial set of statistics with respect to each query, wherein the subset of statistics is equivalent to the initial set of statistics: A) if an execution plan for each query using the subset of statistics is the same as an execution plan for that query using the initial set of statistics, and/or B) if a cost estimate to execute each query against the database using the subset of statistics is within a predetermined amount of a cost estimate to execute that query against the database using the initial set of statistics.
Claim 80
Dependent Claim
224 words
In a database system, an apparatus for providing automated database statistics management for creating and maintaining a set of essential statistics with respect to a query workload comprising: a) means for creating an initial set of statistics by i) means for compiling a set of potentially relevant statistics with respect to a query; ii) means for calculating a plurality of projected query plans by assigning a variety of selectivity values to at least one of the potentially relevant statistics, developing an execution plan for each of the selectivity value assignments and evaluating its cost; and iii) means for determining a set of statistics based on the plurality of projected query plans; and b) means for eliminating any non-essential statistics by i) identifying a subset of the initial set of statistics equivalent to the initial set of statistics with respect to each query, wherein the subset of statistics is equivalent to the initial set of statistics: A) if an execution plan for each query using the subset of statistics is the same as an execution plan for that query using the initial set of statistics, and/or B) if a cost estimate to execute each query against the database using the subset of statistics is within a predetermined amount of a cost estimate to execute that query against the database using the initial set of statistics.
Claim 81
Dependent Claim
27 words
The apparatus of claim 68 wherein the means for creating an initial set of statistics is activated in real time after each query in the query workload.
Claim 82
Dependent Claim
40 words
The apparatus of claim 68 wherein the query workload comprises a plurality of previously executed queries and the means for creating an initial set of statistics and the means for eliminating non-essential statistics are activated off-line on the query workload.
Claim 83
Dependent Claim
38 words
The apparatus of claim 68 wherein the means for creating an initial set of statistics assigns a probability of creation to a statistic based on the proportional amount of the query workload to which it is potentially relevant.
Claim 84
Dependent Claim
44 words
The apparatus of claim 68 wherein the means for calculating a plurality of projected query plans associates a cost with each plan and the means for determining a set of statistics uses the costs associated with each plan to determine the set of statistics.
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) | 2006-03-03 | 2006-09-02 | 2007-03-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-03-03 | 2010-09-02 | 2011-03-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-03-03 | 2014-09-02 | 2015-03-04 | $7700.00 | Window Closed / Lapsed |