Generating histograms of population data by scaling from sample data
Histograms formed based on samples of a population, such as histograms created from random page-level samples of a data store, are intelligently scaled to histograms estimating distribution of the entire population of the data store. As an optional optimization, where a threshold number of duplicate samples are observed during page-level sampling, the number of distinct values in the overall population data is presumed to be the number of distinct values in the sample data. Also, during estimation of distinct values of an overall population, a “Chao” estimator can optionally be utilized as a lower bound of the estimate. The resulting estimate is then used when scaling, which can take domain knowledge of the data being scaled into account in order to prevent scaled estimates from exceeding the limits of the domain. Also, a “sum of the parts” mathematical relationship can be taken into account during scaling that the sum of the scaled distinct values for each bin of an estimate histogram should total an estimate for the total distinct values of the entire population.
1. A computer-implemented method comprising:
employing a processor to facilitate execution of computer-executable instructions that, when executed, cause operations to be performed, comprising:
determining an estimate of a number of distinct values in a population data set from a sample data set taken from the population data set; and
setting a Chao estimator as a lower bound for the estimate of the number of distinct values in the population data set, the Chao estimator being a function of the estimated number of distinct values in the population data set, a number of distinct values in the sample data set, and a number of values that appear a selected number of times in the sample data set, the selected number of times being greater than one,
the determining including:
determining whether a number of duplicates in the sample data is greater than a first threshold amount;
determining that the estimate of the number of distinct values in the population data set is equal to the number of distinct values in the sample data set when it is determined that the number of duplicates in the sample data is greater than the first threshold amount;
determining whether a number of duplicates in the sample data is less than a second threshold amount;
determining the estimate of the number of the distinct values in the population data set by linearly scaling the number of duplicates in the sample data when it is determined that the number of duplicates in the sample data is less than the second threshold amount; and
determining the estimate of the number of the distinct values in the population data set by non-linearly scaling the number of duplicates in the sample data when the number of duplicates in the sample data is more than the second threshold amount and less than the first threshold amount, and
the setting including resetting the estimate of the number of the distinct values in the population data set to the Chao estimator when the Chao estimator is greater than the estimate of the number of the distinct values in the population data set.
2. The computer-implemented method of claim 1 , further comprising scaling a histogram based on the sample data set to derive an estimate of a histogram representing the population data set.
3. The computer-implemented method of claim 2 , wherein the scaling comprises determining whether the sample data set includes at least a predetermined number of duplicate values relative to the population data set.
4. The computer-implemented method of claim 1 , further comprising calculating the Chao estimator according to the following equation:
D
=
d
+
f
1
2
2
f
2
,
D being representative of the estimate of the number of distinct values in the population data set, d represents the number of distinct values in the sample data set, f l represents a number of values that appear exactly once in the sample data set, and f 2 represents a number of values that appear exactly twice in the sample data set.
5. The computer-implemented method of claim 1 , further comprising:
determining a second estimated amount of a number of distinct values in a histogram bin for the population data set; and
resetting the second estimated amount to a histogram bin threshold value if the second estimated amount is greater than the histogram bin threshold value.
6. The computer-implemented method of claim 5 , wherein resetting the second estimated amount includes determining an excess amount by which the second estimated amount is greater than the histogram bin threshold value, and redistributing the excess amount to one or more other estimated amounts of the respective number of distinct values in one or more other histogram bins for the population data set, redistributing causing the sum of the second estimated amount and the one or more other estimated amounts to equal the estimate of the number of distinct values in the population data set.
7. The computer-implemented method of claim 6 , wherein redistributing includes redistributing the excess amount equally amongst the one or more other estimated amounts.
8. A computer-implemented database system, comprising:
a processor;
a server object configured to:
determine an estimate of a number of distinct values in a population data set from a sample data set taken from the population data set;
set a Chao estimator as a lower bound for the estimate of distinct values in the population data set, the Chao estimator being a function of the estimate of the number of distinct values in the population data set, a number of distinct values in a sample data set, and a number of values that appear a selected number of times in the sample data set, the selected number of times being greater than one;
determine whether a number of duplicates in the sample data is greater than a first threshold amount; and
determine that the estimate of the number of distinct values in the population data set is equal to the number of distinct values in the sample data set when it is determined that the number of duplicates in the sample data is greater than the first threshold amount;
determine whether a number of duplicates in the sample data is less than a second threshold amount;
determine the estimate of the number of the distinct values in the population data set by linearly scaling the number of duplicates in the sample data when it is determined that the number of duplicates in the sample data is less than the second threshold amount;
determine the estimate of the number of the distinct values in the population data set by non-linearly scaling the number of duplicates in the sample data when the number of duplicates in the sample data is more than the second threshold amount and less than the first threshold amount; and
reset the estimate of the number of the distinct values in the population data set to the Chao estimator when the Chao estimator is greater than the estimate of the number of the distinct values in the population data set; and
a computer-readable storage medium storing instructions that, when executed by the processor, cause the processor to implement the server object.
9. The computer-implemented database system of claim 8 , wherein the server object is further configured to scale a histogram based on the sample data set to derive an estimate of a histogram representing the population data set.
10. The computer-implemented database system of claim 9 , wherein the scaling comprises determining whether the sample data set includes at least a predetermined number of duplicate values relative to the population data set.
11. The computer-implemented database system of claim 8 , wherein the server object is further configured to calculate the Chao estimator according to the following equation:
D
=
d
+
f
1
2
2
f
2
,
D being representative of the estimate of the number of distinct values in the population data set, d represents the number of distinct values in the sample data set, f l represents a number of values that appear exactly once in the sample data set, and f 2 represents a number of values that appear exactly twice in the sample data set.
12. The computer-implemented database system of claim 8 , wherein the server object is a structured query language server.
13. The computer-implemented database system of claim 8 , further comprising a data store having the population data set.
14. A computer-readable storage media, the computer-readable media not being a signal per se, storing computer-executable instructions that, when executed by at least one processor, cause operations to be performed, comprising:
determining an estimate of a number of distinct values in a population data set from a sample data set taken from the population data set; and
setting a Chao estimator as a lower bound for the estimate of the number of distinct values in the population data set, the Chao estimator being a function of the estimated number of distinct values in the population data set, a number of distinct values in the sample data set, and a number of values that appear a selected number of times in the sample data set, the selected number of times being greater than one,
the determining including:
determining whether a number of duplicates in the sample data is greater than a first threshold amount;
determining that the estimate of the number of distinct values in the population data set is equal to the number of distinct values in the sample data set when it is determined that the number of duplicates in the sample data is greater than the first threshold amount;
determining whether a number of duplicates in the sample data is less than a second threshold amount;
determining the estimate of the number of the distinct values in the population data set by linearly scaling the number of duplicates in the sample data when it is determined that the number of duplicates in the sample data is less than the second threshold amount; and
determining the estimate of the number of the distinct values in the population data set by non-linearly scaling the number of duplicates in the sample data when the number of duplicates in the sample data is more than the second threshold amount and less than the first threshold amount, and
the setting including resetting the estimate of the number of the distinct values in the population data set to the Chao estimator when the Chao estimator is greater than the estimate of the number of the distinct values in the population data set.
15. The computer-readable storage media of claim 14 , the operations further comprising scaling a histogram based on the sample data set to derive an estimate of a histogram representing the population data set.
16. The computer-readable storage media of claim 15 , wherein the scaling comprises determining whether the sample data set includes at least a predetermined number of duplicate values relative to the population data set.
17. The computer-readable storage media of claim 14 , the operations further comprising calculating the Chao estimator according to the following equation:
D
=
d
+
f
1
2
2
f
2
,
D being representative of the estimate of the number of distinct values in the population data set, d represents the number of distinct values in the sample data set, f 1 represents a number of values that appear exactly once in the sample data set, and f 2 represents a number of values that appear exactly twice in the sample data set.
18. The computer-readable storage media of claim 14 , the operations further comprising:
determining a second estimated amount of a number of distinct values in a histogram bin for the population data set; and
resetting the second estimated amount to a histogram bin threshold value if the second estimated amount is greater than the histogram bin threshold value.
19. The computer-readable storage media of claim 18 , wherein resetting the second estimated amount includes determining an excess amount by which the second estimated amount is greater than the histogram bin threshold value, and redistributing the excess amount to one or more other estimated amounts of the respective number of distinct values in one or more other histogram bins for the population data set, redistributing causing the sum of the second estimated amount and the one or more other estimated amounts to equal the estimate of the number of distinct values in the population data set.
20. The computer-readable storage media of claim 19 , wherein redistributing includes redistributing the excess amount equally amongst the one or more other estimated amounts.