# US 6,732,085 B1 · Method and system for sample size determination for database optimizers

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 6,732,085 B1
- Document ID: US6732085B1
- Status: Granted
- Kind: B1
- Application number: 09/872,565
- Filed: 2001-05-31
- Granted: 2004-05-04
- Earliest claimed: 2001-05-31
- Assignees: Oracle International Corporation
- Inventors: Ari W. Mozes
- Web page: https://patentgrep.com/patent/US6732085B1

## CPC

- G06F 16/2462: {Approximate or statistical queries}
- Y10S 707/99932: Access augmentation or optimizing
- Y10S 707/99933: Query processing, i.e. searching
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## 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.

## Claims

### Claim 1

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 (depends on 1)

The method of claim 1 in which the first statistic comprises the number of rows in a database table.

### Claim 3 (depends on 1)

The method of claim 1 in which the first statistic comprises average column length.

### Claim 4 (depends on 1)

The method of claim 1 in which the first statistic comprises maximum value.

### Claim 5 (depends on 1)

The method of claim 1 in which the first statistic comprises minimum value.

### Claim 6 (depends on 1)

The method of claim 1 in which the sample size is expressed as a sampling fraction of the population.

### Claim 7 (depends on 6)

The method of claim 6 in which the sampling fraction is independently evaluated against each individual row in a database column or table.

### Claim 8 (depends on 1)

The method claim 1 further comprising the step of generating the first statistic based upon the data samples.

### Claim 9 (depends on 1)

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 10 (depends on 1)

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 11 (depends on 1)

The method of claim 1 in which the data samples are stored in a separate database object.

### Claim 12 (depends on 11)

The method of claim 11 in which a re-scan is performed against the separate database object.

### Claim 13 (depends on 1)

The method of claim 1 in which the first statistic comprises a histogram.

### Claim 14 (depends on 1)

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 15 (depends on 1)

The method of claim 1 in which the first statistic comprises a number of distinct values.

### Claim 16 (depends on 15)

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 17 (depends on 1)

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 18

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 19 (depends on 18)

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 20 (depends on 19)

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 21 (depends on 18)

The method of claim 18, wherein (b) comprises determining whether the sample size includes at least 919 rows.

### Claim 22 (depends on 18)

The method of claim 18, wherein (b) comprises determining whether the statistic can be extrapolated to the data population as a whole.

### Claim 23 (depends on 18)

The method of claim 18, wherein (b) comprises comparing a threshold value against the sample size.

### Claim 24 (depends on 18)

The method of claim 18, wherein the sample size is expressed as a sampling fraction of the data population.

### Claim 25 (depends on 24)

The method of claim 24, wherein the sample fraction is independently evaluated against each individual row in a database column or table.

### Claim 26 (depends on 18)

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 27

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 28 (depends on 27)

The computer program product of claim 27 in which the first statistic comprises the number of rows in a database table.

### Claim 29 (depends on 27)

The computer program product of claim 27 in which the first statistic comprises average column length.

### Claim 30 (depends on 27)

The computer program product of claim 27 in which the first statistic comprises maximum value.

### Claim 31 (depends on 27)

The computer program product of claim 27 in which the first statistic comprises minimum value.

### Claim 32 (depends on 27)

The computer program product of claim 27 in which the sample size is expressed as a sampling fraction of the population.

### Claim 33 (depends on 27)

The computer program product of claim 27, wherein said process further comprises generating the first statistic based upon the data samples.

### Claim 34 (depends on 27)

The computer program product of claim 27 in which the first statistic comprises a number of distinct values.

### Claim 35 (depends on 27)

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 36 (depends on 27)

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 37 (depends on 27)

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 38 (depends on 27)

The computer program product of claim 27 in which the first statistic comprises a histogram.

### Claim 39 (depends on 34)

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 40

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 41 (depends on 40)

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 42 (depends on 41)

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 43 (depends on 40)

The computer program product of claim 40, wherein (b) comprises determining whether the sample size includes at least 919 rows.

### Claim 44 (depends on 40)

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 45 (depends on 40)

The computer program product of claim 40, wherein (b) comprises comparing a threshold value against the sample size.

### Claim 46 (depends on 40)

The computer program product of claim 40, wherein the sample size is expressed as a sampling fraction of the data population.

### Claim 47 (depends on 46)

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 48 (depends on 40)

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 49

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 50 (depends on 49)

The system of claim 49 in which the first statistic comprises the number of rows in a database table.

### Claim 51 (depends on 49)

The system of claim 49 in which the first statistic comprises average column length.

### Claim 52 (depends on 49)

The system of claim 49 in which the first statistic comprises maximum value.

### Claim 53 (depends on 49)

The system of claim 49 in which the first statistic comprises minimum value.

### Claim 54 (depends on 49)

The system of claim 49 in which the sample size is expressed as a sampling fraction of the population.

### Claim 55 (depends on 49)

The system of claim 49 further comprising means for generating the first statistic based upon the data samples.

### Claim 56 (depends on 49)

The system of claim 49 in which the first statistic comprises a number of distinct values.

### Claim 57 (depends on 49)

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 58 (depends on 49)

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 59 (depends on 49)

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 60 (depends on 56)

The system of claim 56 in which the first statistic comprises a histogram.

### Claim 61 (depends on 56)

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 62

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 63 (depends on 62)

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 64 (depends on 63)

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 65 (depends on 62)

The system of claim 62, wherein (b) comprises means for determining whether the sample size includes at least 919 rows.

### Claim 66 (depends on 62)

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 67 (depends on 62)

The system of claim 62, wherein (b) comprises means for comparing a threshold value against the sample size.

### Claim 68 (depends on 62)

The system of claim 62, wherein the sample size is expressed as a sampling fraction of the data population.

### Claim 69 (depends on 68)

The system of claim 68, wherein the sample fraction is independently evaluated against each individual row in a database column or table.

### Claim 70 (depends on 62)

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.
