US6363371B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Identifying essential statistics for query optimization for databases
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1999-06-29
•
Granted: 2002-03-26
•
Expires: 2019-06-29
Abstract
Abstract An essential statistics identification utility tool attempts to reduce or minimize the overhead associated with statistics by identifying from an initial set of statistics a set of essential statistics that provide a query optimizer with the ability to choose among query execution plans with minimized loss in accuracy as compared to using the initial set of statistics. The set of essential statistics is identified as a subset of the initial set of statistics that is equivalent to the initial set of statistics with respect to each query of a workload. The subset of statistics is equivalent to the initial set of statistics 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 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. The subset of statistics may be identified such that any proper subset of the subset of statistics is not equivalent to the initial set of statistics with respect to each query. The subset of statistics may also be identified such that an update cost or size for the subset of statistics is minimized.
Inventors
- 👤 Surajit Chaudhuri
- 👤 Vivek Narasayya
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 09:01
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/99932
Claims Analysis
Total Claims: 66
Claim 1
Independent Claim
134 words
A method for identifying statistics for use in executing one or more queries against a database, the method comprising the steps of: (a) identifying an initial set of statistics; and (b) 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: (i) 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 (ii) 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 2
Independent Claim
134 words
A method for identifying statistics for use in executing one or more queries against a database, the method comprising the steps of: (a) identifying an initial set of statistics; and (b) 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: (i) 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 (ii) 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 3
Dependent Claim
44 words
The method of claim 1 , wherein the identifying step (b) comprises the step of identifying the subset of statistics such that any proper subset of the subset of statistics is not equivalent to the initial set of statistics with respect to each query.
Claim 4
Dependent Claim
31 words
The method of claim 1 , wherein the predetermined amount is a predetermined percentage of the cost estimate to execute that query against the database using the initial set of statistics.
Claim 5
Dependent Claim
12 words
The method of claim 1 , wherein the predetermined amount is zero.
Claim 6
Dependent Claim
34 words
The method of claim 1 , wherein the identifying step (b) comprises the step of identifying the subset of statistics such that an update cost or size for the subset of statistics is minimized.
Claim 7
Dependent Claim
48 words
The method of claim 1 , wherein the identifying step (b) comprises the step of identifying the subset of statistics by removing statistics from the initial set of statistics if the remaining subset of statistics is equivalent to the initial set of statistics with respect to each query.
Claim 8
Dependent Claim
58 words
The method of claim 6 , comprising the step of identifying the one or more queries from a workload of queries as the one or more queries that have estimated execution costs greater than any other query of the workload and that account for at least a predetermined percentage of a total estimated execution cost for the workload.
Claim 9
Dependent Claim
77 words
The method of claim 7 , further comprising the steps of: (c) identifying each query of the workload such that the subset of statistics is not equivalent to the initial set of statistics with respect to that query, and (d) identifying another subset of statistics by removing statistics from the initial set of statistics if the remaining subset of statistics is equivalent to the initial set of statistics with respect to each query identified in step (c).
Claim 10
Dependent Claim
155 words
The method of claim 6 , comprising the steps of: for each statistic of the initial set of statistics, identifying from a workload of queries a respective set of queries such that that statistic is potentially relevant to each query in the respective query set and such that each query in the respective query set has estimated execution costs greater than any other potentially relevant query of the workload; for each statistic of the initial set of statistics, determining whether the initial set of statistics without that statistic is equivalent to the initial set of statistics with respect to each query in the respective query set, and, if not, including that statistic in a first subset of statistics; and identifying the one or more queries from the workload as each query of the workload such that the first subset of statistics is not equivalent to the initial set of statistics with respect to that query.
Claim 11
Dependent Claim
65 words
The method of claim 1 , wherein the identifying step (b) comprises the steps of: (i) identifying a subset of the initial set of statistics, (ii) determining whether the subset of statistics identified in step (b)(i) is equivalent to the initial set of statistics with respect to each query, and (iii) repeating steps (b)(i) and (b)(ii) for other subsets of the initial set of statistics.
Claim 12
Dependent Claim
27 words
The method of claim 10 , wherein the identifying step (b)(i) identifies subsets of the initial set of statistics in increasing order of update cost or size.
Claim 13
Dependent Claim
42 words
The method of claim 10 , wherein the repeating step (b)(iii) comprises the step of repeating steps (b)(i) and (b)(ii) until the subset of statistics identified in step (b)(i) is equivalent to the initial set of statistics with respect to each query.
Claim 14
Dependent Claim
92 words
The method of claim 1 , wherein the identifying step (b) comprises the steps of: (i) identifying a seed subset of the initial set of statistics, (ii) adding a subset of the remaining subset of the initial set of statistics to the seed subset to produce a current subset of statistics, (iii) determining whether the current subset of statistics is equivalent to the initial set of statistics with respect to each query, and (iv) repeating steps (b)(ii) and (b)(iii) for other subsets of the remaining subset of the initial set of statistics.
Claim 15
Dependent Claim
56 words
The method of claim 13 , wherein the identifying step (b)(i) comprises the steps of determining whether the initial set of statistics without any one statistic of the initial set of statistics is equivalent to the initial set of statistics with respect to each query, and, if not, including the one statistic in the seed subset.
Claim 16
Dependent Claim
31 words
The method of claim 13 , wherein the adding step (b)(ii) identifies subsets of the remaining subset of the initial set of statistics in increasing order of update cost or size.
Claim 17
Dependent Claim
39 words
The method of claim 13 , wherein the repeating step (b)(iv) comprises the step of repeating steps (b)(ii) and (b)(iii) until the current subset of statistics is equivalent to the initial set of statistics with respect to each query.
Claim 18
Dependent Claim
81 words
The method of claim 1 , wherein the identifying step (b) comprises the steps of: (i) partitioning statistics of the initial set of statistics into partitions such that each partition comprises statistics on a respective table of one of the one or more queries, (ii) identifying a subset of each partition such that the combined partition subsets are equivalent to the initial set of statistics with respect to the one query, and (iii) repeating steps (b)(i) and (b)(ii) for each query.
Claim 19
Dependent Claim
32 words
The method of claim 17 , wherein the identifying step (b)(ii) comprises the step of identifying each partition subset such that an update cost or size for each partition subset is minimized.
Claim 20
Dependent Claim
99 words
The method of claim 1 , wherein the identifying step (b) comprises the steps of: (i) identifying a seed subset of the initial set of statistics, (ii) partitioning statistics of the remaining subset of the initial set of statistics into partitions such that each partition comprises statistics on a respective table of one of the one or more queries, (iii) identifying a subset of each partition such that the combined partition subsets and seed subset are equivalent to the initial set of statistics with respect to the one query, and (iv) repeating steps (b)(ii) and (b)(iii) for each query.
Claim 21
Dependent Claim
56 words
The method of claim 19 , wherein the identifying step (b)(i) comprises the steps of determining whether the initial set of statistics without any one statistic of the initial set of statistics is equivalent to the initial set of statistics with respect to each query, and, if not, including the one statistic in the seed subset.
Claim 22
Dependent Claim
32 words
The method of claim 19 , wherein the identifying step (b)(iii) comprises the step of identifying each partition subset such that an update cost or size for each partition subset is minimized.
Claim 23
Dependent Claim
141 words
A computer readable medium having computer-executable instructions for identifying statistics for use in executing one or more queries against a database, the computer-executable instructions for performing the steps of; (a) identifying an initial set of statistics; and (b) 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: (i) 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 (ii) 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
141 words
A computer readable medium having computer-executable instructions for identifying statistics for use in executing one or more queries against a database, the computer-executable instructions for performing the steps of; (a) identifying an initial set of statistics; and (b) 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: (i) 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 (ii) 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
46 words
The computer readable medium of claim 22 , wherein the identifying step (b) comprises the step of identifying the subset of statistics such that any proper subset of the subset of statistics is not equivalent to the initial set of statistics with respect to each query.
Claim 26
Dependent Claim
33 words
The computer readable medium of claim 22 , wherein the predetermined amount is a predetermined percentage of the cost estimate to execute that query against the database using the initial set of statistics.
Claim 27
Dependent Claim
14 words
The computer readable medium of claim 22 , wherein the predetermined amount is zero.
Claim 28
Dependent Claim
36 words
The computer readable medium of claim 22 , wherein the identifying step (b) comprises the step of identifying the subset of statistics such that an update cost or size for the subset of statistics is minimized.
Claim 29
Dependent Claim
50 words
The computer readable medium of claim 22 , wherein the identifying step (b) comprises the step of identifying the subset of statistics by removing statistics from the initial set of statistics if the remaining subset of statistics is equivalent to the initial set of statistics with respect to each query.
Claim 30
Dependent Claim
60 words
The computer readable medium of claim 27 , comprising the step of identifying the one or more queries from a workload of queries as the one or more queries that have estimated execution costs greater than any other query of the workload and that account for at least a predetermined percentage of a total estimated execution cost for the workload.
Claim 31
Dependent Claim
79 words
The computer readable medium of claim 28 , further comprising the steps of: (c) identifying each query of the workload such that the subset of statistics is not equivalent to the initial set of statistics with respect to that query, and (d) identifying another subset of statistics by removing statistics from the initial set of statistics if the remaining subset of statistics is equivalent to the initial set of statistics with respect to each query identified in step (c).
Claim 32
Dependent Claim
157 words
The computer readable medium of claim 27 , comprising the steps of: for each statistic of the initial set of statistics, identifying from a workload of queries a respective set of queries such that that statistic is potentially relevant to each query in the respective query set and such that each query in the respective query set has estimated execution costs greater than any other potentially relevant query of the workload; for each statistic of the initial set of statistics, determining whether the initial set of statistics without that statistic is equivalent to the initial set of statistics with respect to each query in the respective query set, and, if not, including that statistic in a first subset of statistics; and identifying the one or more queries from the workload as each query of the workload such that the first subset of statistics is not equivalent to the initial set of statistics with respect to that query.
Claim 33
Dependent Claim
67 words
The computer readable medium of claim 22 , wherein the identifying step (b) comprises the steps of: (i) identifying a subset of the initial set of statistics, (ii) determining whether the subset of statistics identified in step (b)(i) is equivalent to the initial set of statistics with respect to each query, and (iii) repeating steps (b)(i) and (b)(ii) for other subsets of the initial set of statistics.
Claim 34
Dependent Claim
29 words
The computer readable medium of claim 31 , wherein the identifying step (b)(i) identifies subsets of the initial set of statistics in increasing order of update cost or size.
Claim 35
Dependent Claim
44 words
The computer readable medium of claim 31 , wherein the repeating step (b)(iii) comprises the step of repeating steps (b)(i) and (b)(ii) until the subset of statistics identified in step (b)(i) is equivalent to the initial set of statistics with respect to each query.
Claim 36
Dependent Claim
94 words
The computer readable medium of claim 22 , wherein the identifying step (b) comprises the steps of: (i) identifying a seed subset of the initial set of statistics, (ii) adding a subset of the remaining subset of the initial set of statistics to the seed subset to produce a current subset of statistics, (iii) determining whether the current subset of statistics is equivalent to the initial set of statistics with respect to each query, and (iv) repeating steps (b)(ii) and (b)(iii) for other subsets of the remaining subset of the initial set of statistics.
Claim 37
Dependent Claim
58 words
The computer readable medium of claim 34 , wherein the identifying step (b)(i) comprises the steps of determining whether the initial set of statistics without any one statistic of the initial set of statistics is equivalent to the initial set of statistics with respect to each query, and, if not, including the one statistic in the seed subset.
Claim 38
Dependent Claim
33 words
The computer readable medium of claim 34 , wherein the adding step (b)(ii) identifies subsets of the remaining subset of the initial set of statistics in increasing order of update cost or size.
Claim 39
Dependent Claim
41 words
The computer readable medium of claim 34 , wherein the repeating step (b)(iv) comprises the step of repeating steps (b)(ii) and (b)(iii) until the current subset of statistics is equivalent to the initial set of statistics with respect to each query.
Claim 40
Dependent Claim
83 words
The computer readable medium of claim 22 , wherein the identifying step (b) comprises the steps of: (i) partitioning statistics of the initial set of statistics into partitions such that each partition comprises statistics on a respective table of one of the one or more queries, (ii) identifying a subset of each partition such that the combined partition subsets are equivalent to the initial set of statistics with respect to the one query, and (iii) repeating steps (b)(i) and (b)(ii) for each query.
Claim 41
Dependent Claim
34 words
The computer readable medium of claim 38 , wherein the identifying step (b)(ii) comprises the step of identifying each partition subset such that an update cost or size for each partition subset is minimized.
Claim 42
Dependent Claim
101 words
The computer readable medium of claim 22 , wherein the identifying step (b) comprises the steps of: (i) identifying a seed subset of the initial set of statistics, (ii) partitioning statistics of the remaining subset of the initial set of statistics into partitions such that each partition comprises statistics on a respective table of one of the one or more queries, (iii) identifying a subset of each partition such that the combined partition subsets and seed subset are equivalent to the initial set of statistics with respect to the one query, and (iv) repeating steps (b)(ii) and (b)(iii) for each query.
Claim 43
Dependent Claim
58 words
The computer readable medium of claim 40 , wherein the identifying step (b)(i) comprises the steps of determining whether the initial set of statistics without any one statistic of the initial set of statistics is equivalent to the initial set of statistics with respect to each query, and, if not, including the one statistic in the seed subset.
Claim 44
Dependent Claim
34 words
The computer readable medium of claim 40 , wherein the identifying step (b)(iii) comprises the step of identifying each partition subset such that an update cost or size for each partition subset is minimized.
Claim 45
Dependent Claim
137 words
A database system for identifying statistics for use in executing one or more queries against a database, the database system comprising: (a) means for identifying an initial set of statistics; and (b) means for 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: (i) 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 (ii) 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 46
Dependent Claim
137 words
A database system for identifying statistics for use in executing one or more queries against a database, the database system comprising: (a) means for identifying an initial set of statistics; and (b) means for 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: (i) 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 (ii) 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 47
Dependent Claim
44 words
The database system of claim 43 , wherein the identifying means (b) comprises means for identifying the subset of statistics such that any proper subset of the subset of statistics is not equivalent to the initial set of statistics with respect to each query.
Claim 48
Dependent Claim
32 words
The database system of claim 43 , wherein the predetermined amount is a predetermined percentage of the cost estimate to execute that query against the database using the initial set of statistics.
Claim 49
Dependent Claim
13 words
The database system of claim 43 , wherein the predetermined amount is zero.
Claim 50
Dependent Claim
34 words
The database system of claim 43 , wherein the identifying means (b) comprises means for identifying the subset of statistics such that an update cost or size for the subset of statistics is minimized.
Claim 51
Dependent Claim
48 words
The database system of claim 43 , wherein the identifying means (b) comprises means for identifying the subset of statistics by removing statistics from the initial set of statistics if the remaining subset of statistics is equivalent to the initial set of statistics with respect to each query.
Claim 52
Dependent Claim
58 words
The database system of claim 48 , comprising means for identifying the one or more queries from a workload of queries as the one or more queries that have estimated execution costs greater than any other query of the workload and that account for at least a predetermined percentage of a total estimated execution cost for the workload.
Claim 53
Dependent Claim
81 words
The database system of claim 49 , further comprising: (c) means for identifying each query of the workload such that the subset of statistics is not equivalent to the initial set of statistics with respect to that query, and (d) means for identifying another subset of statistics by removing statistics from the initial set of statistics if the remaining subset of statistics is equivalent to the initial set of statistics with respect to each query identified by the identifying means (c).
Claim 54
Dependent Claim
159 words
The database system of claim 48 , comprising: means for identifying from a workload of queries a respective set of queries for each statistic of the initial set of statistics such that that statistic is potentially relevant to each query in the respective query set and such that each query in the respective query set has estimated execution costs greater than any other potentially relevant query of the workload; means for determining for each statistic of the initial set of statistics whether the initial set of statistics without that statistic is equivalent to the initial set of statistics with respect to each query in the respective query set, and, if not, including that statistic in a first subset of statistics; and means for identifying the one or more queries from the workload as each query of the workload such that the first subset of statistics is not equivalent to the initial set of statistics with respect to that query.
Claim 55
Dependent Claim
56 words
The database system of claim 43 , wherein the identifying means (b) comprises: (i) means for identifying one or more subsets of the initial set of statistics, and (ii) means for determining whether each subset of statistics identified by the identifying means (b)(i) is equivalent to the initial set of statistics with respect to each query.
Claim 56
Dependent Claim
28 words
The database system of claim 52 , wherein the identifying means (b)(i) identifies subsets of the initial set of statistics in increasing order of update cost or size.
Claim 57
Dependent Claim
46 words
The database system of claim 52 , wherein the identifying means (b)(i) identifies subsets of the initial set of statistics until an identified subset of the initial set of statistics is determined to be equivalent to the initial set of statistics with respect to each query.
Claim 58
Dependent Claim
83 words
The database system of claim 43 , wherein the identifying means (b) comprises: (i) means for identifying a seed subset of the initial set of statistics, (ii) means for adding each of one or more subsets of the remaining subset of the initial set of statistics to the seed subset to produce one or more current subset of statistics, and (iii) means for determining whether each current subset of statistics is equivalent to the initial set of statistics with respect to each query.
Claim 59
Dependent Claim
56 words
The database system of claim 55 , wherein the identifying means (b)(i) comprises means for determining whether the initial set of statistics without any one statistic of the initial set of statistics is equivalent to the initial set of statistics with respect to each query, and, if not, including the one statistic in the seed subset.
Claim 60
Dependent Claim
32 words
The database system of claim 55 , wherein the adding means (b)(ii) identifies subsets of the remaining subset of the initial set of statistics in increasing order of update cost or size.
Claim 61
Dependent Claim
58 words
The database system of claim 55 , wherein the adding means (b)(ii) adds a subset of the remaining subset of the initial set of statistics to the seed subset to produce a current subset of statistics until a current subset of statistics is determined to be equivalent to the initial set of statistics with respect to each query.
Claim 62
Dependent Claim
74 words
The database system of claim 43 , wherein the identifying means (b) comprises: (i) means for partitioning statistics of the initial set of statistics into partitions such that each partition comprises statistics on a respective table of one of the one or more queries, and (ii) means for identifying a subset of each partition such that the combined partition subsets are equivalent to the initial set of statistics with respect to the one query.
Claim 63
Dependent Claim
32 words
The database system of claim 59 , wherein the identifying means (b)(ii) comprises means for identifying each partition subset such that an update cost or size for each partition subset is minimized.
Claim 64
Dependent Claim
94 words
The database system of claim 43 , wherein the identifying means (b) comprises: (i) means for identifying a seed subset of the initial set of statistics, (ii) means for partitioning statistics of the remaining subset of the initial set of statistics into partitions such that each partition comprises statistics on a respective table of one of the one or more queries, and (iii) means for identifying a subset of each partition such that the combined partition subsets and seed subset are equivalent to the initial set of statistics with respect to the one query.
Claim 65
Dependent Claim
56 words
The database system of claim 61 , wherein the identifying means (b)(i) comprises means for determining whether the initial set of statistics without any one statistic of the initial set of statistics is equivalent to the initial set of statistics with respect to each query, and, if not, including the one statistic in the seed subset.
Claim 66
Dependent Claim
32 words
The database system of claim 61 , wherein the identifying means (b)(iii) comprises means for identifying each partition subset such that an update cost or size for each partition subset is minimized.
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-25 | 2005-09-24 | 2006-03-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-03-25 | 2009-09-24 | 2010-03-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-03-25 | 2013-09-24 | 2014-03-26 | $7700.00 | Window Closed / Lapsed |