Patent US6732085B1 successfully refreshed from Google Patents.
US6732085B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for sample size determination for database optimizers
Assignee: Oracle International Corp
•
Filing: 2001-05-31
•
Granted: 2004-05-04
•
Expires: 2021-05-31
Abstract
Abstract A system and method for determining an adequate sample size for statistics collection is disclosed. A mechanism for automatically determining an adequate sample size for both statistics and histograms is provided. The sample size determination is accomplished via an iterative approach where the process starts with a small sample, and for each attribute which may need more data, the sample size is increased while restricting the information collected to only those attributes that require the larger sample.
Inventors
- 👤 Ari W. Mozes
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 02:26
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2458; G06F16/2462; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933
Claims Analysis
Total Claims: 76
Claim 1
Independent Claim
122 words
A method for determining sample size for statistics collection in a database system, comprising: a. selecting a sample size to determine a first set of statistics for a data population, the first set of statistics comprising a first statistic; b. identifying data samples from the data population corresponding to the initial sample size; c. making a determination of adequacy for the data samples for the first statistic, wherein determination of adequacy comprises determining whether the sample size includes at least 919 rows; d. if the data samples are not adequate, then increasing the sample size and repeating steps b and c; and e. if the data samples are adequate, then storing the first statistic which was generated based upon the data samples.
Claim 2
Independent Claim
122 words
A method for determining sample size for statistics collection in a database system, comprising: a. selecting a sample size to determine a first set of statistics for a data population, the first set of statistics comprising a first statistic; b. identifying data samples from the data population corresponding to the initial sample size; c. making a determination of adequacy for the data samples for the first statistic, wherein determination of adequacy comprises determining whether the sample size includes at least 919 rows; d. if the data samples are not adequate, then increasing the sample size and repeating steps b and c; and e. if the data samples are adequate, then storing the first statistic which was generated based upon the data samples.
Claim 3
Dependent Claim
19 words
The method of claim 1 in which the first statistic comprises the number of rows in a database table.
Claim 4
Dependent Claim
14 words
The method of claim 1 in which the first statistic comprises average column length.
Claim 5
Dependent Claim
13 words
The method of claim 1 in which the first statistic comprises maximum value.
Claim 6
Dependent Claim
13 words
The method of claim 1 in which the first statistic comprises minimum value.
Claim 7
Dependent Claim
19 words
The method of claim 1 in which the sample size is expressed as a sampling fraction of the population.
Claim 8
Dependent Claim
23 words
The method of claim 6 in which the sampling fraction is independently evaluated against each individual row in a database column or table.
Claim 9
Dependent Claim
18 words
The method claim 1 further comprising the step of generating the first statistic based upon the data samples.
Claim 10
Dependent Claim
27 words
The method of claim 1 in which step c further comprises determining if generated statistics based upon the data samples can be scaled for the entire population.
Claim 11
Dependent Claim
24 words
The method of claim 1 in which step c further comprises comparing a threshold value against the number of rows in the data samples.
Claim 12
Dependent Claim
17 words
The method of claim 1 in which the data samples are stored in a separate database object.
Claim 13
Dependent Claim
16 words
The method of claim 11 in which a re-scan is performed against the separate database object.
Claim 14
Dependent Claim
13 words
The method of claim 1 in which the first statistic comprises a histogram.
Claim 15
Dependent Claim
26 words
The method of claim 1 in which the sample size is selected to attempt retrieval of at least 5500 rows of a database table or column.
Claim 16
Dependent Claim
16 words
The method of claim 1 in which the first statistic comprises a number of distinct values.
Claim 17
Dependent Claim
42 words
The method of claim 15 in which step c further comprises determining if the first statistic based upon the data samples can be scaled based upon evaluating the number of distinct values and the number of non-null values in the data samples.
Claim 18
Dependent Claim
58 words
The method of claim 1 in which the set of statistics further comprises a second statistic, in which the first statistic generated based upon the sample size is adequate but the second statistic generated based upon the sample size is inadequate and for which the sample size is increased to identify additional data samples for the second statistic.
Claim 19
Independent Claim
93 words
A method for determining sample size for statistics collection in a database system, the method comprising: (a) generating a statistic for a data population using a sample of data values from the data population, the sample of data values having a sample size; (b) determining whether the sample size is adequate for the statistic without obtaining an additional sample; (c) increasing the sample size and repeating (a) and (b) when the sample size is not adequate for the statistic; and (d) storing the statistic when the sample size is adequate for the statistic.
Claim 20
Independent Claim
93 words
A method for determining sample size for statistics collection in a database system, the method comprising: (a) generating a statistic for a data population using a sample of data values from the data population, the sample of data values having a sample size; (b) determining whether the sample size is adequate for the statistic without obtaining an additional sample; (c) increasing the sample size and repeating (a) and (b) when the sample size is not adequate for the statistic; and (d) storing the statistic when the sample size is adequate for the statistic.
Claim 21
Dependent Claim
25 words
The method of claim 18 , wherein the statistic comprises average column length, maximum value, minimum value, a histogram, or a number of distinct values.
Claim 22
Dependent Claim
24 words
The method of claim 19 , wherein (b) comprises evaluating the number of distinct values and the number of non-null values in the sample.
Claim 23
Dependent Claim
19 words
The method of claim 18 , wherein (b) comprises determining whether the sample size includes at least 919 rows.
Claim 24
Dependent Claim
23 words
The method of claim 18 , wherein (b) comprises determining whether the statistic can be extrapolated to the data population as a whole.
Claim 25
Dependent Claim
17 words
The method of claim 18 , wherein (b) comprises comparing a threshold value against the sample size.
Claim 26
Dependent Claim
20 words
The method of claim 18 , wherein the sample size is expressed as a sampling fraction of the data population.
Claim 27
Dependent Claim
23 words
The method of claim 24 , wherein the sample fraction is independently evaluated against each individual row in a database column or table.
Claim 28
Dependent Claim
78 words
The method of claim 18 , wherein the method further comprises: (e) generating another statistic for the data population using the sample of data values from the data population; (f) determining whether the sample size is adequate for the other statistic; (g) increasing the sample size and repeating (e) and (f) when the sample size is not adequate for the other statistic; and (h) storing the other statistic when the sample size is adequate for the other statistic.
Claim 29
Dependent Claim
149 words
A computer program product that includes a computer-readable medium comprising a sequence of instructions which, when executed by a processor, causes said processor to execute a process for determining sample size for statistics collection in a database system, said process comprising: a. selecting a sample size to determine a first set of statistics for a data population, the first set of statistics comprising a first statistic; b. identifying data samples from the data population corresponding to the initial sample size; c. making a determination of adequacy for the data samples for the first statistic, wherein determination of adequacy comprises determining whether the sample size includes at least 919 rows; d. if the data samples are not adequate, then increasing the sample size and repeating steps b and c; and e. if the data samples are adequate, then storing the first statistic which was generated based upon the data samples.
Claim 30
Dependent Claim
149 words
A computer program product that includes a computer-readable medium comprising a sequence of instructions which, when executed by a processor, causes said processor to execute a process for determining sample size for statistics collection in a database system, said process comprising: a. selecting a sample size to determine a first set of statistics for a data population, the first set of statistics comprising a first statistic; b. identifying data samples from the data population corresponding to the initial sample size; c. making a determination of adequacy for the data samples for the first statistic, wherein determination of adequacy comprises determining whether the sample size includes at least 919 rows; d. if the data samples are not adequate, then increasing the sample size and repeating steps b and c; and e. if the data samples are adequate, then storing the first statistic which was generated based upon the data samples.
Claim 31
Dependent Claim
21 words
The computer program product of claim 27 in which the first statistic comprises the number of rows in a database table.
Claim 32
Dependent Claim
16 words
The computer program product of claim 27 in which the first statistic comprises average column length.
Claim 33
Dependent Claim
15 words
The computer program product of claim 27 in which the first statistic comprises maximum value.
Claim 34
Dependent Claim
15 words
The computer program product of claim 27 in which the first statistic comprises minimum value.
Claim 35
Dependent Claim
21 words
The computer program product of claim 27 in which the sample size is expressed as a sampling fraction of the population.
Claim 36
Dependent Claim
22 words
The computer program product of claim 27 , wherein said process further comprises generating the first statistic based upon the data samples.
Claim 37
Dependent Claim
18 words
The computer program product of claim 27 in which the first statistic comprises a number of distinct values.
Claim 38
Dependent Claim
60 words
The computer program product of claim 27 in which the set of statistics further comprises a second statistic, in which the first statistic generated based upon the sample size is adequate but the second statistic generated based upon the sample size is inadequate and for which the sample size is increased to identify additional data samples for the second statistic.
Claim 39
Dependent Claim
29 words
The computer program product of claim 27 in which step c further comprises determining if generated statistics based upon the data samples can be scaled for the entire population.
Claim 40
Dependent Claim
26 words
The computer program product of claim 27 in which step c further comprises comparing a threshold value against the number of rows in the data samples.
Claim 41
Dependent Claim
15 words
The computer program product of claim 27 in which the first statistic comprises a histogram.
Claim 42
Dependent Claim
44 words
The computer program product of claim 34 in which step c further comprises determining if the first statistic based upon the data samples can be scaled based upon evaluating the number of distinct values and the number of non-null values in the data samples.
Claim 43
Dependent Claim
118 words
A computer program product that includes a computer-readable medium comprising a sequence of instructions which, when executed by a processor, causes the processor to execute a process for determining sample size for statistics collection in a database system, the process comprising: (a) generating a statistic for a data population using a sample of data values from the data population, the sample of data values having a sample size; (b) determining whether the sample size is adequate for the statistic without obtaining an additional sample; (c) increasing the sample size and repeating (a) and (b) when the sample size is not adequate for the statistic; and (d) storing the statistic when the sample size is adequate for the statistic.
Claim 44
Dependent Claim
118 words
A computer program product that includes a computer-readable medium comprising a sequence of instructions which, when executed by a processor, causes the processor to execute a process for determining sample size for statistics collection in a database system, the process comprising: (a) generating a statistic for a data population using a sample of data values from the data population, the sample of data values having a sample size; (b) determining whether the sample size is adequate for the statistic without obtaining an additional sample; (c) increasing the sample size and repeating (a) and (b) when the sample size is not adequate for the statistic; and (d) storing the statistic when the sample size is adequate for the statistic.
Claim 45
Dependent Claim
27 words
The computer program product of claim 40 , wherein the statistic comprises average column length, maximum value, minimum value, a histogram, or a number of distinct values.
Claim 46
Dependent Claim
26 words
The computer program product of claim 41 , wherein (b) comprises evaluating the number of distinct values and the number of non-null values in the sample.
Claim 47
Dependent Claim
21 words
The computer program product of claim 40 , wherein (b) comprises determining whether the sample size includes at least 919 rows.
Claim 48
Dependent Claim
25 words
The computer program product of claim 40 , wherein (b) comprises determining whether the statistic can be extrapolated to the data population as a whole.
Claim 49
Dependent Claim
19 words
The computer program product of claim 40 , wherein (b) comprises comparing a threshold value against the sample size.
Claim 50
Dependent Claim
22 words
The computer program product of claim 40 , wherein the sample size is expressed as a sampling fraction of the data population.
Claim 51
Dependent Claim
25 words
The computer program product of claim 46 , wherein the sample fraction is independently evaluated against each individual row in a database column or table.
Claim 52
Dependent Claim
80 words
The computer program product of claim 40 , wherein the process further comprises: (e) generating another statistic for the data population using the sample of data values from the data population; (f) determining whether the sample size is adequate for the other statistic; (g) increasing the sample size and repeating (e) and (f) when the sample size is not adequate for the other statistic; and (h) storing the other statistic when the sample size is adequate for the other statistic.
Claim 53
Independent Claim
132 words
A system for determining sample size for statistics collection in a database system, comprising: a. means for selecting a sample size to determine a first set of statistics for a data population, the first set of statistics comprising a first statistic; b. means for identifying data samples from the data population corresponding to the initial sample size; c. means for making a determination of adequacy for the data samples for the first statistic, wherein determination of adequacy comprises means for determining whether the sample size includes at least 919 rows; d. means for increasing the sample size and repeating steps b and c when the data samples are not adequate; and e. means for storing the first statistic which was generated based upon the data samples when the data samples are adequate.
Claim 54
Independent Claim
132 words
A system for determining sample size for statistics collection in a database system, comprising: a. means for selecting a sample size to determine a first set of statistics for a data population, the first set of statistics comprising a first statistic; b. means for identifying data samples from the data population corresponding to the initial sample size; c. means for making a determination of adequacy for the data samples for the first statistic, wherein determination of adequacy comprises means for determining whether the sample size includes at least 919 rows; d. means for increasing the sample size and repeating steps b and c when the data samples are not adequate; and e. means for storing the first statistic which was generated based upon the data samples when the data samples are adequate.
Claim 55
Dependent Claim
19 words
The system of claim 49 in which the first statistic comprises the number of rows in a database table.
Claim 56
Dependent Claim
14 words
The system of claim 49 in which the first statistic comprises average column length.
Claim 57
Dependent Claim
13 words
The system of claim 49 in which the first statistic comprises maximum value.
Claim 58
Dependent Claim
13 words
The system of claim 49 in which the first statistic comprises minimum value.
Claim 59
Dependent Claim
19 words
The system of claim 49 in which the sample size is expressed as a sampling fraction of the population.
Claim 60
Dependent Claim
18 words
The system of claim 49 further comprising means for generating the first statistic based upon the data samples.
Claim 61
Dependent Claim
16 words
The system of claim 49 in which the first statistic comprises a number of distinct values.
Claim 62
Dependent Claim
58 words
The system of claim 49 in which the set of statistics further comprises a second statistic, in which the first statistic generated based upon the sample size is adequate but the second statistic generated based upon the sample size is inadequate and for which the sample size is increased to identify additional data samples for the second statistic.
Claim 63
Dependent Claim
29 words
The system of claim 49 in which step c further comprises means for determining if generated statistics based upon the data samples can be scaled for the entire population.
Claim 64
Dependent Claim
26 words
The system of claim 49 in which step c further comprises means for comparing a threshold value against the number of rows in the data samples.
Claim 65
Dependent Claim
13 words
The system of claim 56 in which the first statistic comprises a histogram.
Claim 66
Dependent Claim
44 words
The system of claim 56 in which step c further comprises means for determining if the first statistic based upon the data samples can be scaled based upon evaluating the number of distinct values and the number of non-null values in the data samples.
Claim 67
Independent Claim
101 words
A system for determining sample size for statistics collection in a database system, the system comprising: (a) means for generating a statistic for a data population using a sample of data values from the data population, the sample of data values having a sample size; (b) means for determining whether the sample size is adequate for the statistic without obtaining an additional sample; (c) means for increasing the sample size and repeating (a) and (b) when the sample size is not adequate for the statistic; and (d) means for storing the statistic when the sample size is adequate for the statistic.
Claim 68
Independent Claim
101 words
A system for determining sample size for statistics collection in a database system, the system comprising: (a) means for generating a statistic for a data population using a sample of data values from the data population, the sample of data values having a sample size; (b) means for determining whether the sample size is adequate for the statistic without obtaining an additional sample; (c) means for increasing the sample size and repeating (a) and (b) when the sample size is not adequate for the statistic; and (d) means for storing the statistic when the sample size is adequate for the statistic.
Claim 69
Dependent Claim
25 words
The system of claim 62 , wherein the statistic comprises average column length, maximum value, minimum value, a histogram, or a number of distinct values.
Claim 70
Dependent Claim
26 words
The system of claim 63 , wherein (b) comprises means for evaluating the number of distinct values and the number of non-null values in the sample.
Claim 71
Dependent Claim
21 words
The system of claim 62 , wherein (b) comprises means for determining whether the sample size includes at least 919 rows.
Claim 72
Dependent Claim
25 words
The system of claim 62 , wherein (b) comprises mean for determining whether the statistic can be extrapolated to the data population as a whole.
Claim 73
Dependent Claim
19 words
The system of claim 62 , wherein (b) comprises means for comparing a threshold value against the sample size.
Claim 74
Dependent Claim
20 words
The system of claim 62 , wherein the sample size is expressed as a sampling fraction of the data population.
Claim 75
Dependent Claim
23 words
The system of claim 68 , wherein the sample fraction is independently evaluated against each individual row in a database column or table.
Claim 76
Dependent Claim
86 words
The system of claim 62 , wherein the system further comprises: (e) means for generating another statistic for the data population using the sample of data values from the data population; (f) means for determining whether the sample size is adequate for the other statistic; (g) means for increasing the sample size and repeating (e) and (f) when the sample size is not adequate for the other statistic; and (h) means for storing the other statistic when the sample size is adequate for the other statistic.
References Cited (Backward Citations)
US6272487B1
Cited
US6353826B1
Cited
US6278989B1
Cited
US6263345B1
Cited
US6438552B1
Cited
US6460045B1
Cited
US6529901B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-05-04 | 2007-11-03 | 2008-05-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-05-04 | 2011-11-03 | 2012-05-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-05-04 | 2015-11-03 | 2016-05-04 | $7700.00 | Window Closed / Lapsed |