Patent US5870752A successfully refreshed from Google Patents.
US5870752A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Incremental maintenance of an approximate histogram in a database system
Assignee: Alcatel Lucent SAS
•
Filing: 1997-08-21
•
Granted: 1999-02-09
•
Expires: 2017-08-21
Abstract
Abstract Techniques for maintaining an approximate histogram of a relation in a database, in the presence of updates to the relation. The histogram includes a number of subsets, or "buckets," each representing at least one possible value of an attribute of the relation. Each of the subsets has a count associated therewith indicative of the frequency of occurrence of the corresponding value of the attribute. After an update to the relation, the counts associated with the subsets are compared to a threshold. If the count associated with a given subset exceeds the threshold, the given subset is separated at its median into two separate subsets. After the separation operation, the two subsets with the lowest counts are combined such that a constant number of subsets are maintained in the histogram, if the total combined count of the subsets does not exceed the threshold. If no two subsets have a total combined count which does not exceed the threshold, the histogram is recomputed from a random sample of the relation. The invention substantially reduces the number of times the histogram must be recomputed from the random sample, and is particularly well-suited for use with approximate equi-depth and compressed histograms.
Inventors
- 👤 Phillip B. Gibbons
- 👤 Yossi Matias
- 👤 Viswanath Poosala
- 👤 Andrew Witkowski
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 08:10
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/23; G06F16/2358; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99942; Y10S707/99943; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
106 words
A method of maintaining a histogram for at least one attribute of a relation in a database, the histogram including a plurality of subsets each representing at least one possible value of the attribute, each of the subsets having a count associated therewith indicative of the frequency of occurrence of the corresponding value of the attribute, the method comprising the steps of: comparing the counts associated with the subsets to a threshold after an update to the relation; and separating a given one of the subsets into at least two separate subsets if the count associated with the given subset exceeds the threshold after the update.
Claim 2
Independent Claim
106 words
A method of maintaining a histogram for at least one attribute of a relation in a database, the histogram including a plurality of subsets each representing at least one possible value of the attribute, each of the subsets having a count associated therewith indicative of the frequency of occurrence of the corresponding value of the attribute, the method comprising the steps of: comparing the counts associated with the subsets to a threshold after an update to the relation; and separating a given one of the subsets into at least two separate subsets if the count associated with the given subset exceeds the threshold after the update.
Claim 3
Dependent Claim
52 words
The method of claim 1 further including the step of merging at least two of the subsets to form a single subset after the separating step, such that the histogram maintains a fixed number of subsets, if there are two subsets with a total combined count which does not exceed the threshold.
Claim 4
Dependent Claim
37 words
The method of claim 2 further including the step of recomputing the histogram from a random sample of the relation if there are not two subsets with a total combined count which does not exceed the threshold.
Claim 5
Dependent Claim
26 words
The method of claim 1 wherein the separating step includes separating the given subset into two separate subsets at an approximate median of the given subset.
Claim 6
Dependent Claim
13 words
The method of claim 1 wherein the histogram is an approximate equi-depth histogram.
Claim 7
Dependent Claim
13 words
The method of claim 1 wherein the histogram is an approximate compressed histogram.
Claim 8
Dependent Claim
40 words
The method of claim 1 wherein the threshold is computed as (2+γ)N/β, where β is the number of subsets, N is the number of values in the relation, and γ is a tunable performance parameter which is greater than -1.
Claim 9
Dependent Claim
14 words
The method of claim 6 wherein γ is selected between about 0.5 and 1.
Claim 10
Dependent Claim
23 words
The method of claim 1 wherein the threshold is recomputed each time the histogram is recomputed from a random sample of the relation.
Claim 11
Dependent Claim
39 words
The method of claim 1 further including the step of comparing the counts of the subsets to a second threshold after an update to the relation, the second threshold representing a lower bound on the count of a subset.
Claim 12
Dependent Claim
44 words
The method of claim 10 wherein the second threshold is generated as N/(β(2+γ l )), where β is the number of subsets, N is the number of values in the relation, and γ l is a tunable performance parameter which is greater than -1.
Claim 13
Dependent Claim
24 words
The method of claim 10 wherein the second threshold is recomputed each time the histogram is recomputed from a random sample of the relation.
Claim 14
Dependent Claim
101 words
The method of claim 10 further including the steps of: merging a given subset having a count less than or equal to the second threshold with another subset adjacent to the given subset; separating the subset having the largest count such that the number of subsets is maintained at a fixed number after the merging step, if the count of the subset with the largest count is at least twice the second threshold; and recomputing the histogram from a sample of the relation if the count of the subset with the largest count is not at least twice the second threshold.
Claim 15
Independent Claim
123 words
An apparatus for use in maintaining a histogram for at least one attribute of a relation in a database, the apparatus comprising: a memory for storing the histogram, the histogram including a plurality of subsets each representing at least one possible value of the attribute, with each of the subsets having a count associated therewith indicative of the frequency of occurrence of the corresponding value of the attribute; and a processor coupled to the memory and operative to compare the counts associated with the subsets to a threshold after an update to the relation, and to separate a given one of the subsets into at least two separate subsets if the count associated with the given subset exceeds the threshold after the update.
Claim 16
Independent Claim
123 words
An apparatus for use in maintaining a histogram for at least one attribute of a relation in a database, the apparatus comprising: a memory for storing the histogram, the histogram including a plurality of subsets each representing at least one possible value of the attribute, with each of the subsets having a count associated therewith indicative of the frequency of occurrence of the corresponding value of the attribute; and a processor coupled to the memory and operative to compare the counts associated with the subsets to a threshold after an update to the relation, and to separate a given one of the subsets into at least two separate subsets if the count associated with the given subset exceeds the threshold after the update.
Claim 17
Dependent Claim
53 words
The apparatus of claim 14 wherein the processor is further operative to merge at least two of the subsets to form a single subset, such that the histogram maintains a fixed number of subsets after the separation, if there are two subsets with a total combined count which does not exceed the threshold.
Claim 18
Dependent Claim
39 words
The apparatus of claim 15 wherein the processor is further operative to recompute the histogram from a random sample of the relation if there are not two subsets with a total combined count which does not exceed the threshold.
Claim 19
Dependent Claim
28 words
The apparatus of claim 14 wherein the processor is further operative to separate the given subset into two separate subsets at an approximate median of the given subset.
Claim 20
Dependent Claim
13 words
The apparatus of claim 14 wherein the histogram is an approximate equi-depth histogram.
Claim 21
Dependent Claim
13 words
The apparatus of claim 14 wherein the histogram is an approximate compressed histogram.
Claim 22
Dependent Claim
45 words
The apparatus of claim 14 wherein the processor is further operative to compute the threshold as (2+γ)N/β, where β is the number of subsets, N is the number of values in the relation, and γ is a tunable performance parameter which is greater than -1.
Claim 23
Dependent Claim
14 words
The apparatus of claim 20 wherein γ is selected between about 0.5 and 1.
Claim 24
Dependent Claim
28 words
The apparatus of claim 14 wherein the processor is further operative to recompute the threshold each time the histogram is recomputed from a random sample of the relation.
Claim 25
Dependent Claim
41 words
The apparatus of claim 14 wherein the processor is further operative to compare the counts of the subsets to a second threshold after an update to the relation, the second threshold representing a lower bound on the count of a subset.
Claim 26
Dependent Claim
49 words
The apparatus of claim 23 wherein the processor is further operative to compute the second threshold as N/(β(2+γ l )), where β is the number of subsets, N is the number of values in the relation, and γ l is a tunable performance parameter which is greater than -1.
Claim 27
Dependent Claim
29 words
The apparatus of claim 23 wherein the processor is further operative to recompute the second threshold each time the histogram is recomputed from a random sample of the relation.
Claim 28
Dependent Claim
105 words
The apparatus of claim 23 wherein the processor is further operative to merge a given subset having a count less than or equal to the second threshold with another subset adjacent to the given subset, to separate the subset having the largest count such that the number of subsets is maintained at a fixed number after the merging step, if the count of the subset with the largest count is at least twice the second threshold, and to recompute the histogram from a sample of the relation if the count of the subset with the largest count is not at least twice the second threshold.
References Cited (Backward Citations)
US4956774A
Cited
US5630120A
Cited
US5692171A
Cited
US5675786A
Cited
US5542089A
Cited
US5689696A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-02-08 | 2002-08-10 | 2003-02-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-02-08 | 2006-08-10 | 2007-02-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-02-08 | 2010-08-10 | 2011-02-09 | $7700.00 | Window Closed / Lapsed |