Online hash based optimizer statistics gathering in a database

1. A computer-implemented method for generating a histogram, comprising:

initializing a first thread and a second thread, wherein the first thread processes a first section of a column in a database table and the second thread processes a second section of the column in the database table concurrently with the first thread;

generating, with a hash function, a first hash table using the first thread and a second hash table using the second thread, wherein the first hash table represents data distribution stored in the first section of the column using a key-value pair and the second hash table represents data distribution stored in the second section of the column using a respective key-value pair, and wherein an intermediate histogram that receives values from the first hash table is generated using the first thread when the first hash table exceeds a maximum allowable number of descriptors; and

merging the first hash table and the second hash table into a histogram, wherein the histogram represents data distribution in the column.

2. The method of claim 1 , further comprising:

normalizing the histogram into a normalized histogram; and

generating, using the normalized histogram, a query plan for a query.

3. The method of claim 1 , wherein the histogram comprises a cell range and a counter, wherein the cell range comprises a range of values in the column and the counter comprises a number of times the values in the range repeat in the column.

4. The method of claim 1 , wherein a cell range in the histogram is different from a cell range in the first hash table and a cell range in the second hash table.

5. The method of claim 1 ,

wherein the intermediate histogram is accessible to the second thread.

6. The method of claim 1 , wherein the generating further comprises:

determining, using the second thread, whether an available descriptor exists in the second hash table;

based on the determining, associating the available descriptor with a value; and

storing the available descriptor in the second hash table.

7. The method of claim 1 , wherein the generating further comprises:

determining, using the second thread, whether an available descriptor exists in the second hash table for a new value;

based on the determining, discarding an in-range descriptor in the second hash table, wherein the discarding merges a value and a counter associated with the in-range descriptor into an intermediate histogram; and

associating the in-range descriptor with the new value in an in-range stack of the second hash table.

8. The method of claim 1 , wherein the generating further comprises:

determining, using the second thread, whether an available descriptor exists in the second hash table for a new value;

based on the determining, discarding an in-range descriptor in the second hash table adjacent to an out-of-range stack, wherein the discarding merges a value and a counter associated with the in-range descriptor into an intermediate histogram; and

associating the in-range descriptor with the new value in the out-of-range stack of the second hash table.

9. The method of claim 1 , wherein the generating further comprises:

determining whether the second hash table comprises out-of-range descriptors;

determining whether a first intermediate histogram is a current intermediate histogram;

based on the determining whether the second hash table comprises out-of-range descriptors and whether the first intermediate histogram is the current intermediate histogram:

generating a second intermediate histogram; and

merging the second hash table into the second intermediate histogram.

10. The method of claim 1 , wherein the generating further comprises:

determining whether the second hash table comprises out-of-range descriptors;

determining whether an intermediate histogram is a current intermediate histogram;

based on the determining whether the second hash table comprises out-of-range descriptors and whether the intermediate histogram is the current intermediate histogram:

moving the out-of-range descriptors in the second hash table into the in-range descriptors in the second hash table using minimum and maximum values associated with the intermediate histogram.

11. The method of claim 1 , wherein the generating further comprises:

clearing the first hash table after the intermediate histogram receives values from the first hash table upon reaching a maximum capacity of the first hash table;

adding one or more values to the first hash table in a subsequent iteration of values from a column until one of: the first hash table reaches the maximum capacity or all the values from the column have been traversed;

clearing the first hash table into the intermediate histogram upon the maximum capacity being reached; and

merging the first hash table with the intermediate histogram upon the values from the column having been traversed.

12. The method of claim 1 , wherein the first hash table includes an entry for a unique value from a column, and a counter associated with each unique value indicating a number of times the unique value has been processed from the column.

13. A system, comprising:

a memory; and

at least one processor coupled to the memory and configured to:

initialize a first thread and a second thread, wherein the first thread processes a first section of a column in a database table and the second thread processes a second section of the column in the database table concurrently with the first thread;

generate, with a hash function, a first hash table using the first thread and a second hash table using the second thread, wherein the first hash table represents data distribution stored in the first section of the column using a key-value pair and the second hash table represents data distribution stored in the second section of the column using a respective key-value pair, and wherein an intermediate histogram that receives values from the first hash table is generated using the first thread when the first hash table exceeds a maximum allowable number of descriptors; and

merge the first hash table and the second hash table into a histogram, wherein the histogram represents data distribution in the column.

14. The system of claim 13 , wherein the at least one processor is configured to: normalize the histogram into a normalized histogram; and

generate, using the normalized histogram, a query plan for a query.

15. The system of claim 13 , wherein the histogram comprises a cell range and a counter, wherein the cell range comprises a range of values in the column and the counter comprises a number of times the values in the range repeat in the column.

16. The system of claim 13 , wherein a cell range in the histogram is different from a cell range in the first hash table and a cell range in the second hash table.

17. The system of claim 13 , wherein the at least one processor is further configured to:

determine, using the second thread, whether an available descriptor exists in the second hash table;

based on the determining, associate the available descriptor with a value; and

store the available descriptor in the second hash table.

18. The system of claim 13 , wherein the at least one processor is further configured to:

determine, using the second thread, whether an available descriptor exists in the second hash table for a new value;

based on the determining, discard an in-range descriptor in the second hash table, wherein the discarding merges a value and a counter associated with the in-range descriptor into an intermediate histogram; and

associate the value of the in-range descriptor with the new value in an in-range stack of the second hash table.

19. The system of claim 13 , wherein the at least one processor is further configured to:

determine, using the second thread, whether an available descriptor exists in the second hash table for a new value;

based on the determining, discard an in-range descriptor in the second hash table adjacent to an out-of-range stack, wherein the discarding merges a value and a counter associated with the in-range descriptor into an intermediate histogram; and

associate the in-range descriptor with the new value in the out-of-range stack of the second hash table.

20. The system of claim 13 , wherein the at least one processor is further configured to:

determine whether the second hash table comprises out-of-range descriptors;

determine whether a first intermediate histogram is a current intermediate histogram;

based on the determining whether the second hash table comprises out-of-range descriptors and whether the first intermediate histogram is the current intermediate histogram:

generate a second intermediate histogram; and

merge the second hash function into the second intermediate histogram.

21. The system of claim 13 , wherein the at least one processor is further configured to:

determine whether the second hash table comprises out-of-range descriptors;

determine whether an intermediate histogram is a current intermediate histogram; and

based on the determining whether the second hash table comprises out-of-range descriptors and whether the intermediate histogram is the current in histogram:

move the out-of-range descriptors in the second hash table into the in-range descriptors in the second hash table using the minimum and maximum values associated with the intermediate histogram.