Hash-value-based single-pass data store statistics collection

1. A data store system comprising:

an array of persistent storage devices configured to store a plurality of data stare tables;

a processor in communication with the array of persistent storage devices, the processor configured to:

select a column of a data store table for statistics collection;

for each column value in the selected column, generate a hash value based on a hash function;

select a first domain of hash values and a second domain of hash values, wherein the second domain is a subset of the first domain;

determine a frequency value for each generated hash value within the first domain;

generate a unique identifier for each hash value that is within the second domain;

determine at least one statistic on the selected column based on the frequency values and the unique identifiers; and

store the at least one statistic for use in a query plan.

2. The data store system of claim 1 , wherein the frequency values and unique identifiers are maintained in a first buffer, wherein the processor is further configured to:

determine that the first buffer is full during generation of the hash values;

reduce a size of the first domain; and

remove all frequency values and corresponding unique identifiers for each associated hash value that is outside of the reduced first domain.

3. The system of claim 2 , wherein the second domain is reduced by a common factor with the first domain when the first domain becomes equal to or smaller than the second domain.

4. The system of claim 2 , wherein the at least one statistic is a number of unique values for the selected column, wherein the number of unique values is based on a total number of hash values contained in the first buffer, a number of unique hash value and unique identifier pairs, initial number of hash values in the first domain, and a number of hash values of the first domain after a hash value has been generated for column value in the selected column.

5. The system of claim 1 , wherein the at least one statistic is high mode frequency of the selected column, and wherein the processor is further configured to:

maintain a first buffer, wherein the first buffer includes a plurality of non-overlapping hash value range groups that span an initial hash value domain; and

determine the high mode frequency based on contents of the second buffer.

6. The system of claim 1 , wherein the at least one statistic is high mode frequency of the selected column, and wherein the processor is further configured to:

maintain a first buffer, wherein the first buffer includes predetermined number of frequency values of generated hash values; and

determine the high mode frequency based on the contents of the second buffer and the number of unique values.

7. The system of claim 1 , wherein each unique identifier associated with a respective hash value is based on a column value corresponding to the respective hash value.

8. A method comprising:

selecting a column of a data store table for statistics collection;

for each column value in the selected column, generating a hash value based on a hash function;

selecting a first domain of hash values and a second domain of hash values, wherein the second domain is a subset of the first domain;

determining a frequency value for each generated hash value within the first domain;

generating a unique identifier for each hash value that is within the second domain;

determining at least one statistic on the selected column based on the frequency values and the unique identifiers; and

storing the at least one statistic for query planning.

9. The method of 8 , further comprising:

maintaining a first buffer to contain the frequency values and unique identifiers;

determining that the first buffer is full during generation of the hash values;

reducing a size of the first domain; and

removing all frequency values and corresponding unique identifiers for each associated hash value that is outside of the reduced first domain.

10. The method claim 9 , further comprising reducing the second domain by a common factor with the first domain when the first domain becomes equal to or smaller than the second domain.

11. The method of claim 9 , wherein determining the at least one statistic comprises determining a number of unique values for the selected column, wherein the number of unique values is based on a total number of hash values contained in the first buffer, a number of unique hash value and unique identifier pairs, initial number of hash values in the first domain, and a number of hash values of the first domain after a hash value has been generated for column value in the selected column.

12. The method claim 8 , wherein determining the at least one statistic comprises determining high mode frequency for the selected column, the method further comprising:

maintaining a first buffer, wherein the first buffer includes a plurality of non-overlapping hash value range groups that span an initial hash value domain; and

determining the high mode frequency based on contents of the second buffer.

13. The method claim 8 , wherein determining the at least one statistic comprises determining high mode frequency for the selected column, the method further comprising:

maintaining a first buffer, wherein the first buffer includes predetermined number of frequency values of generated hash values; and

determining the high mode frequency based on the contents of the second buffer and the number of unique values.

14. The method of claim 8 , wherein generating a unique identifier for each hash value comprises generating a unique identifier associated with a respective hash value based on a column value corresponding to the respective hash value.

15. A computer-readable medium encoded with a plurality of

instructions executable by a processor, the plurality of instructions comprising:

instructions to select a column of a data store table for statistics collection;

instructions to generate, for each column value in the selected column, a hash value based on a hash function;

instructions to select a first domain of hash values and a second domain of hash values, wherein the second domain is a subset of the first domain;

instructions to determine a frequency value for each generated hash value within the first domain;

instructions to generate a unique identifier for each hash value that is within the second domain;

instructions to determine at least one statistic on the selected column based on the frequency values and the unique identifiers; and

instructions to store the at least one statistic for query planning.

16. The computer-readable medium of claim 15 , wherein the plurality of instructions further comprises:

instructions to maintain a first buffer to contain the frequency values and unique identifiers;

instructions to determine that the first buffer is full during generation of the of the has values;

instructions to reduce a size of the first domain; and

instructions to remove all frequency values and corresponding unique identifiers for each associated hash value that is outside of the reduced first domain.

17. The computer-readable medium of claim 16 , wherein the plurality of instructions further comprises instructions to reduce the second domain by a common factor with the first domain when the first domain becomes equal to or smaller than the second domain.

18. The computer-readable medium of claim 16 , wherein the instructions to determine the at least one statistic comprise instructions to determine a number of unique values for the selected column based on a total number of hash values contained in the first buffer, a number of unique hash value and unique identifier pairs, initial number of hash values in the first domain, and a number of hash values of the first domain after a hash value has been generated for column value in the selected column.

19. The computer-readable medium of claim 15 , wherein the instructions to determine the at least one statistic comprise instructions to determine high mode frequency for the selected column, and wherein the plurality of instructions further comprised:

instructions to maintain a first buffer, wherein the first buffer includes a plurality of non-overlapping hash value range groups that span an initial hash value domain; and

instructions to determine the high mode frequency based on contents of the second buffer.

20. The computer-readable medium of claim 15 , wherein the instructions to determine the at least one statistic comprise instructions to determine high mode frequency for the selected column, and wherein the plurality of instructions further comprised:

instructions to maintain a first buffer, wherein the first buffer includes predetermined number of frequency values of generated hash values; and

instructions to determine the high mode frequency based on the contents of the second buffer and the number of unique values.