Online hash based optimizer statistics gathering in a database

Patent metadata

Field	Value
Publication number	US-9529849-B2
Application number	US-201314145759-A
Country	US
Kind code	B2
Filing date	Dec 31, 2013
Priority date	Dec 31, 2013
Publication date	Dec 27, 2016
Grant date	Dec 27, 2016

Abstract

Disclosed herein are system, method, and computer program product embodiments for generating a histogram used to optimize a query plan. An embodiment operates by initializing a first thread and a second thread, such that the first thread processes a first section of a column and the second thread processes a second section of the column, concurrently with the first thread. The first thread generates a first hash table and the second thread generates a second hash table. The first and second hash tables represent data distribution stored in the respective first and second sections of the column. The first and second tables are merged into a histogram that represents data distribution in the column.

First claim

What is claimed is:

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 i

Assignees

• Seputis Edwin
• Sybase Inc

Inventors

• Seputis Edwin

Classifications

• G06F16/24545 Primary

  Selectivity estimation or determination · CPC title

• G06F16/24539

  using cached or materialised query results · CPC title

• G06F17/30457

  Physics · mapped topic

• G06F17/30469 Primary

  Physics · mapped topic