US6460045B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Self-tuning histogram and database modeling
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1999-03-15
•
Granted: 2002-10-01
•
Expires: 2019-03-15
Abstract
Abstract Building histograms by using feedback information about the execution of query workload rather than by examining the data helps reduce the cost of building and maintaining histograms. A method of maintaining self-tuning histograms updates histograms based on feedback about the execution of a user query. A histogram may be initialized using an assumption of uniform distribution of data or by combining existing histograms. A histogram tuner accesses and estimated result in response to a user query generated by using the histogram. The histogram tuner calculates an estimation error based on the result of the user query and the estimated result. The frequencies of histogram buckets are refined based on the estimation error. The bucket bounds of the histogram are restructured based on the refined frequencies. The method may be performed on-line after a user query or off-line by accessing a workload log. By updating a histogram without accessing the database, the cost of building and maintaining histograms is significantly reduced.
Inventors
- 👤 Ashraf Aboulnaga
- 👤 Surajit Chaudhuri
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 03:55
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; Y10S707/99933; Y10S707/99934; Y10S707/99941; Y10S707/99943
Claims Analysis
Total Claims: 47
Claim 1
Independent Claim
96 words
In a database system, a method of maintaining a self-tuning histogram having a plurality of buckets defined by at least two bucket boundaries and a bucket frequency comprising: (a) identifying the histogram; (b) using the histogram to generate an estimated result size in response to a user query; (c) calculating an estimation error based on the estimated result size and the size of the result of the user query; (d) dividing the estimation error into one or more portions; (e) applying the portions to the bucket frequencies of one or buckets to modify the bucket frequencies.
Claim 2
Dependent Claim
96 words
In a database system, a method of maintaining a self-tuning histogram having a plurality of buckets defined by at least two bucket boundaries and a bucket frequency comprising: (a) identifying the histogram; (b) using the histogram to generate an estimated result size in response to a user query; (c) calculating an estimation error based on the estimated result size and the size of the result of the user query; (d) dividing the estimation error into one or more portions; (e) applying the portions to the bucket frequencies of one or buckets to modify the bucket frequencies.
Claim 3
Dependent Claim
35 words
The method of claim 1 wherein the step of applying the estimation error portions comprises applying the portions to the bucket frequencies of the one or more buckets in proportion to their relative bucket frequency.
Claim 4
Dependent Claim
31 words
The method of claim 1 wherein the step of applying the estimation error portions comprises applying the portions to the bucket frequencies of buckets used to generate the estimated result size.
Claim 5
Dependent Claim
16 words
The method of claim 1 wherein the step of identifying the histogram comprises initializing the histogram.
Claim 6
Dependent Claim
24 words
The method of claim 4 wherein the step of initializing the histogram comprises assigning substantially uniform bucket frequencies and bucket boundaries to the buckets.
Claim 7
Dependent Claim
19 words
The method of claim 4 wherein the step of initializing the histogram comprises combining a plurality of existing histograms.
Claim 8
Dependent Claim
11 words
The method of claim 1 wherein the self-tuning histogram is multi-dimensional.
Claim 9
Independent Claim
181 words
A method of building and maintaining a self-tuning histogram having a plurality of buckets each defined by at least two bucket boundaries and a bucket frequency comprising the steps of: a) initializing the histogram; b) using the histogram to generate an estimated result size in response to a user query; c) calculating an estimation error based on the size of the result of the user query and the estimated result size; d) modifying the frequency of the buckets by applying a damping factor to the estimation error, dividing the estimation error into one or more portions and applying the portions to the bucket frequencies of the buckets used to generate the estimation error in proportion to their relative bucket frequency; and e) redefining the bucket boundaries of one or more of the buckets by merging adjacent buckets having relatively similar frequencies into single buckets to free buckets, selecting buckets belonging to a set of buckets having the highest frequency to be split, and splitting the selected buckets into a plurality of buckets such that the total number of buckets remains constant.
Claim 10
Independent Claim
181 words
A method of building and maintaining a self-tuning histogram having a plurality of buckets each defined by at least two bucket boundaries and a bucket frequency comprising the steps of: a) initializing the histogram; b) using the histogram to generate an estimated result size in response to a user query; c) calculating an estimation error based on the size of the result of the user query and the estimated result size; d) modifying the frequency of the buckets by applying a damping factor to the estimation error, dividing the estimation error into one or more portions and applying the portions to the bucket frequencies of the buckets used to generate the estimation error in proportion to their relative bucket frequency; and e) redefining the bucket boundaries of one or more of the buckets by merging adjacent buckets having relatively similar frequencies into single buckets to free buckets, selecting buckets belonging to a set of buckets having the highest frequency to be split, and splitting the selected buckets into a plurality of buckets such that the total number of buckets remains constant.
Claim 11
Dependent Claim
43 words
The method of claim 8 wherein the step of merging buckets is performed by repeatedly scanning the histogram buckets and finding adjacent buckets having the minimum difference in frequencies and merging the buckets if the difference in frequencies is below a predetermined threshold.
Claim 12
Dependent Claim
11 words
The method of claim 8 wherein the self-tuning histogram is multi-dimensional.
Claim 13
Dependent Claim
21 words
The method of claim 8 wherein the step of initializing the histogram comprises assigning uniform frequencies and boundaries to the buckets.
Claim 14
Dependent Claim
19 words
The method of claim 8 wherein the step of initializing the histogram comprises combining a plurality of existing histograms.
Claim 15
Dependent Claim
24 words
The method of claim 8 wherein the step of modifying the frequency of the buckets is performed immediately following an execution of user query.
Claim 16
Dependent Claim
33 words
The method of claim 8 wherein the steps of generating an estimated result size and calculating an estimation error are performed by accessing a log of stored user queries and corresponding result sizes.
Claim 17
Dependent Claim
32 words
The method of claim 8 wherein the step of redefining the bucket boundaries comprises merging adjacent buckets when the total number of buckets reaches a predetermined limit on the number of buckets.
Claim 18
Dependent Claim
24 words
The method of claim 8 wherein the step of modifying the bucket frequencies is performed when a predetermined minimum estimation error has been observed.
Claim 19
Independent Claim
240 words
A method of building and maintaining an n dimensional self-tuning histogram having a plurality of buckets arranged in a grid, each bucket defined by at least four grid partitions and a bucket frequency, the histogram being defined by n scales, one scale for each dimension, and an n dimensional frequency matrix, each of the scales defining the partitions of the frequency matrix which divide the frequency matrix into a plurality of (n−1) dimensional slices of the frequency matrix comprising the steps of: a) initializing the histogram; b) using the histogram to generate an estimated result size in response to a user query; c) calculating an estimation error based on the size of the result of the user query and the estimated result size; d) modifying the frequency of the buckets in the frequency matrix by dividing the estimation error into one or more portions and applying the portions to the bucket frequencies of the buckets used to generate the estimation error in proportion to their relative bucket frequency; and e) changing the scales of the histogram in at least one dimension to redefine the grid partitions by merging adjacent slices of the frequency matrix having relatively similar frequencies to free buckets, selecting slices of the frequency matrix belonging to a set of slices having the highest marginal frequency to be split, and splitting the selected slices into a plurality of slices such that the total number of buckets remains constant.
Claim 20
Independent Claim
240 words
A method of building and maintaining an n dimensional self-tuning histogram having a plurality of buckets arranged in a grid, each bucket defined by at least four grid partitions and a bucket frequency, the histogram being defined by n scales, one scale for each dimension, and an n dimensional frequency matrix, each of the scales defining the partitions of the frequency matrix which divide the frequency matrix into a plurality of (n−1) dimensional slices of the frequency matrix comprising the steps of: a) initializing the histogram; b) using the histogram to generate an estimated result size in response to a user query; c) calculating an estimation error based on the size of the result of the user query and the estimated result size; d) modifying the frequency of the buckets in the frequency matrix by dividing the estimation error into one or more portions and applying the portions to the bucket frequencies of the buckets used to generate the estimation error in proportion to their relative bucket frequency; and e) changing the scales of the histogram in at least one dimension to redefine the grid partitions by merging adjacent slices of the frequency matrix having relatively similar frequencies to free buckets, selecting slices of the frequency matrix belonging to a set of slices having the highest marginal frequency to be split, and splitting the selected slices into a plurality of slices such that the total number of buckets remains constant.
Claim 21
Dependent Claim
22 words
The method of claim 17 wherein the step of initializing the histogram comprises assigning uniform frequencies and partitions to the frequency matrix.
Claim 22
Dependent Claim
18 words
The method of claim 17 wherein the step of initializing the histogram comprises combined a plurality existing histograms.
Claim 23
Dependent Claim
47 words
The method of claim 19 wherein the step of merging adjacent slices is performed by repeatedly scanning the histogram buckets and finding adjacent slices having the minimum difference in frequencies between corresponding buckets and merging the slices if the difference in frequencies is below a predetermined threshold.
Claim 24
Dependent Claim
17 words
The method of claim 19 wherein the steps are performed immediately following an execution of user query.
Claim 25
Dependent Claim
22 words
The method of claim 19 wherein the steps are performed by accessing a log of stored user queries and corresponding result sizes.
Claim 26
Dependent Claim
114 words
A computer-readable medium having computer executable instructions for performing steps for maintaining a self-tuning histogram in database wherein user queries are executed on the database to return query results, the method comprising: (a) identifying a self-tuning histogram having a plurality of buckets defined by at least two bucket boundaries and a bucket frequency; and (b) updating the histogram based on the results of an executed query against the database by using the histogram to generate an estimated result size in response to a user query, calculating an estimation error based on the size of the result of the user query and the estimated result size, and updating the histogram based on the estimation error.
Claim 27
Dependent Claim
114 words
A computer-readable medium having computer executable instructions for performing steps for maintaining a self-tuning histogram in database wherein user queries are executed on the database to return query results, the method comprising: (a) identifying a self-tuning histogram having a plurality of buckets defined by at least two bucket boundaries and a bucket frequency; and (b) updating the histogram based on the results of an executed query against the database by using the histogram to generate an estimated result size in response to a user query, calculating an estimation error based on the size of the result of the user query and the estimated result size, and updating the histogram based on the estimation error.
Claim 28
Dependent Claim
31 words
The computer readable medium of claim 23 wherein the step of updating the histogram comprises modifying the bucket frequency of one or more of the buckets based on the estimation error.
Claim 29
Dependent Claim
50 words
The computer readable medium of claim 24 wherein the step of modifying the bucket frequency of the one or more buckets comprises: I) dividing the estimation error into one or more portions; and II) applying the portions to the bucket frequencies of the buckets used to generate the estimated result.
Claim 30
Dependent Claim
50 words
The computer readable medium of claim 24 wherein the step of modifying the bucket frequency of the one or more buckets comprises: I) dividing the estimation error into one or more portions; and II) applying the portions to bucket frequencies of the buckets in proportion to their relative bucket frequency.
Claim 31
Dependent Claim
18 words
The computer readable medium of claim 23 wherein the step of identifying the histogram comprises initializing the histogram.
Claim 32
Dependent Claim
26 words
The computer readable medium of claim 27 wherein the step of initializing the histogram comprises assigning substantially uniform bucket frequencies and bucket boundaries to the buckets.
Claim 33
Dependent Claim
13 words
The computer readable medium of claim 23 wherein the self-tuning histogram is multi-dimensional.
Claim 34
Dependent Claim
23 words
The computer readable medium of claim 23 additionally including computer readable instructions for redefining one or more bucket boundaries based on bucket frequencies.
Claim 35
Dependent Claim
34 words
The computer readable medium of claim 30 wherein the step of redefining the one or more bucket boundaries comprises splitting one or more buckets that meet a split criteria into a plurality of buckets.
Claim 36
Dependent Claim
32 words
The computer readable medium of claim 31 wherein the step of redefining the one or more bucket boundaries comprises merging one or more sets of adjacent buckets that meet a merge criteria.
Claim 37
Dependent Claim
25 words
The computer readable medium of claim 32 wherein the merge criteria comprises having a bucket frequency relatively similar to the bucket frequency of adjacent buckets.
Claim 38
Dependent Claim
19 words
The computer readable medium of claim 32 wherein the step of merging buckets generates free buckets for splitting buckets.
Claim 39
Dependent Claim
29 words
The computer readable medium of claim 34 wherein the step of splitting buckets comprises allocating freed buckets to one or more buckets in proportion to their relative bucket frequency.
Claim 40
Dependent Claim
23 words
The computer readable medium of claim 31 wherein the split criteria comprises belonging to a set of buckets having the highest bucket frequencies.
Claim 41
Dependent Claim
28 words
The computer readable medium of claim 31 wherein the step of redefining one or more bucket boundaries is performed such that the total number of buckets remains constant.
Claim 42
Independent Claim
120 words
An apparatus for maintaining a self-tuning histogram in database wherein user queries are executed on the database to return query results, and wherein the histogram has a plurality of buckets defined by at least two bucket boundaries and a bucket frequency comprising: a) means for refining the bucket frequencies based on the results of an executed query against the database; b) means for redefining one or more of the bucket boundaries based on the bucket frequencies comprising means for calculating an estimation error based on the size of a result of a user query and an estimated result size estimated using the histogram; and wherein the means for refining refines the frequencies by distributing the estimation error amongst bucket frequencies.
Claim 43
Independent Claim
120 words
An apparatus for maintaining a self-tuning histogram in database wherein user queries are executed on the database to return query results, and wherein the histogram has a plurality of buckets defined by at least two bucket boundaries and a bucket frequency comprising: a) means for refining the bucket frequencies based on the results of an executed query against the database; b) means for redefining one or more of the bucket boundaries based on the bucket frequencies comprising means for calculating an estimation error based on the size of a result of a user query and an estimated result size estimated using the histogram; and wherein the means for refining refines the frequencies by distributing the estimation error amongst bucket frequencies.
Claim 44
Dependent Claim
51 words
The apparatus of claim 38 wherein the means for redefining the bucket boundaries comprises means for merging one or more sets of adjacent buckets having relatively similar bucket frequencies and means for splitting buckets belong to a set of buckets having a relatively high bucket frequency into a plurality of buckets.
Claim 45
Independent Claim
221 words
An apparatus for maintaining a self-tuning histogram in database wherein user queries are executed on the database to return query results, and wherein the histogram has a plurality of buckets defined by at least two bucket boundaries and a bucket frequency comprising: a) a memory device for storing a database comprising multiple data records; b) a computer having one or more processing units for executing a stored computer program, said computer including a rapid access memory store; and c) an interface for coupling the memory device for storing the database to the computer to allow records to be retrieved from the database; wherein d) the computer executing a stored program having software components including i) a component for providing a statistical model of the data distribution in the form of a self-tuning histogram having a plurality of buckets defined by at least two bucket boundaries and a bucket frequency; ii) a component for refining the bucket frequencies based on the results of an executed query against the database comprising a component for determining an estimation error based on the result size of a user query and an estimated result size as determined by the statistical model; and iii) a component for redefining at least one bucket boundary based on the bucket frequencies by applying the estimation error to the bucket frequencies.
Claim 46
Independent Claim
221 words
An apparatus for maintaining a self-tuning histogram in database wherein user queries are executed on the database to return query results, and wherein the histogram has a plurality of buckets defined by at least two bucket boundaries and a bucket frequency comprising: a) a memory device for storing a database comprising multiple data records; b) a computer having one or more processing units for executing a stored computer program, said computer including a rapid access memory store; and c) an interface for coupling the memory device for storing the database to the computer to allow records to be retrieved from the database; wherein d) the computer executing a stored program having software components including i) a component for providing a statistical model of the data distribution in the form of a self-tuning histogram having a plurality of buckets defined by at least two bucket boundaries and a bucket frequency; ii) a component for refining the bucket frequencies based on the results of an executed query against the database comprising a component for determining an estimation error based on the result size of a user query and an estimated result size as determined by the statistical model; and iii) a component for redefining at least one bucket boundary based on the bucket frequencies by applying the estimation error to the bucket frequencies.
Claim 47
Dependent Claim
55 words
The apparatus of claim 40 wherein the component for redefining the bucket boundaries further comprises a component for merging one or more sets of adjacent buckets that have similar bucket frequencies and a component for splitting one or more buckets belonging to a set of having relatively high bucket frequency into a plurality of buckets.
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-09-30 | 2006-04-01 | 2006-10-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-09-30 | 2010-04-01 | 2010-10-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-09-30 | 2014-04-01 | 2014-10-01 | $7700.00 | Window Closed / Lapsed |