Histogram generation on multiple dimensions

• US 9,678,999 B1
• Filed: 12/31/2014
• Issued: 06/13/2017
• Est. Priority Date: 12/31/2014
• Status: Active Grant

• Current Assignee: Teradata Corporation
• Original Assignee: Teradata US, Inc. (Teradata Corporation)
• Inventors: Gibas, Michael A., To, Hien T.
• Primary Examiner(s): Thai, Hanh
• Application Number:
  US14/588,109
• Time in Patent Office: 895 Days
• Field of Search: 707706, 707752, 707803, 382168, 382171
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination

Abstract

Based on a request, a processor may identify a multi-dimensional dataset stored in the at least one of a plurality of data tables and identify each dimension of the multi-dimensional dataset. For each respective identified dimension, the processor may sort the identified dataset on values of the respective identified dimension, partition the sorted dataset into a predetermined number of intervals associated with the respective identified dimension, determine a number of rows for each interval and select a lower boundary value and an upper boundary value for each interval. The upper boundary value may be the highest value in each interval. The lower boundary value for an interval having lowest sorted values may be the lowest value in the interval or the upper boundary value of an interval having immediately preceding partitioned values. The processor may further store the boundary values and rows for each interval of each identified dimension as the histogram. A method and computer-readable medium are also disclosed.

Claims

1. A data store system comprising:

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

a processor in communication with the persistent storage devices, the processor configured to;

receive a request to generate a multi-dimensional histogram on at least one of the plurality of data tables;

identify a multi-dimensional dataset stored in the at least one of the plurality of data tables;

identify each dimension of the multi-dimensional dataset;

for each respective identified dimension;

sort the identified multi-dimensional dataset on values of the respective identified dimension;

for each respective identified dimension;

partition the sorted dataset into a predetermined number of intervals associated with the respective identified dimension;

determine a number of rows for each interval; and

select a lower boundary value and an upper boundary value for each interval, wherein the upper boundary value is the highest value in each interval, wherein the lower boundary value for an interval having lowest sorted values is the lowest value in the interval, and the lower boundary value for each other interval is the upper boundary value of an interval having immediately preceding partitioned values;

store the lower boundary values, upper boundary values, and number of rows for each interval of each identified dimension as the histogram;

receive a query on the at least one of the plurality of data tables; and

generate a query response based on the histogram.

2. The data store system of claim 1, wherein the processor is further configured to partition the sorted dataset into a predetermined number of intervals associated with the respective identified dimension, wherein the dataset is partitioned into equal-height intervals.

3. The database system of claim 1, wherein the processor is further configured to:

for each respective other identified dimension after a first identified dimension;

determine a predetermined number of intervals associated with the respective other identified dimension;

sort each interval generated on a dimension immediately prior to the respective other identified dimension based on values of the respective other dimension;

for each interval of the dimension immediately prior, generate an interval group, wherein each interval group comprises a number of intervals, wherein the number is the predetermined number of intervals associated with the respective other dimension;

for each interval group, determine a number of rows in each interval and select a lower boundary value and an upper boundary value for each interval of the respective interval group, wherein the upper boundary value is the highest value in each interval of the respective interval group, wherein the lower boundary value for an interval having lowest sorted values is the lowest value in the interval of the respective interval group, and the lower boundary value for each other interval of the respective interval group is the upper boundary value of an interval of the respective interval group having immediately preceding partitioned values; and

store the lower boundary value, the upper boundary value, and the number of rows for each interval as the histogram.

4. The data store system of claim 1, wherein the processor is further executable to, for each dimension, select each interval in an order of values in each interval.

5. The data store system of claim 1, wherein the at least one of the plurality of data tables is a single data table.

6. The data store system of claim 1, wherein each interval contains at least one row.

12. The data store system of claim 1, wherein each interval contains at least one row.

7. A computer-implemented method comprising:

receiving a request to generate a multi-dimensional histogram on at least one of a plurality of data tables stored in an array of persistent storage devices;

retrieving the at least one of the plurality of data tables;

identifying a multi-dimensional dataset stored in the at least one of the plurality of data tables;

identifying each dimension of the multi-dimensional dataset;

for each respective identified dimension;

sorting the identified multi-dimensional dataset on values of the respective identified dimension;

partitioning the sorted dataset into a predetermined number of intervals associated with the respective identified dimension;

determining a number of rows for each interval; and

selecting a lower boundary value and an upper boundary value for each interval, wherein the upper boundary value is the highest value in each interval, wherein the lower boundary value for an interval having lowest sorted values is the lowest value in the interval, and the lower boundary value for each other interval is the upper boundary value of an interval having immediately preceding partitioned values;

storing the lower boundary values, upper boundary values, and number of rows for each interval of each identified dimension as the histogram;

receiving a query on the at least one of the plurality of data tables; and

generating a query response based on the histogram.

8. The computer-implemented method of claim 7, wherein partitioning the sorted dataset into a predetermined number of intervals associated with the respective identified dimension comprises partitioning the sorted dataset into a predetermined number of intervals associated with the respective identified dimension, wherein the dataset is partitioned into equal-height intervals.

9. The computer-implemented method of claim 7, further comprising:

for each respective other identified dimension after a first identified dimension;

determining a predetermined number of intervals associated with the respective other identified dimension;

sorting each interval generated on a dimension immediately prior to the respective other identified dimension based on values of the respective other dimension;

for each interval of the dimension immediately prior, generating an interval group, wherein each interval group comprises a number of intervals, wherein the number is the predetermined number of intervals associated with the respective other dimension;

for each interval group, determining a number of rows in each interval and selecting a lower boundary value and an upper boundary value for each interval of the respective interval group, wherein the upper boundary value is the highest value in each interval of the respective interval group, wherein the lower boundary value for an interval having lowest sorted values is the lowest value in the interval of the respective interval group, and the lower boundary value for each other interval of the respective interval group is the upper boundary value of an interval of the respective interval group having immediately preceding partitioned values; and

storing the lower boundary value, the upper boundary value, and the number of rows for each interval as the histogram.

10. The computer-implemented method of claim 7, further comprising, for each dimension, selecting each interval in an order of values in each interval.

11. The computer-implemented method of claim 7, wherein the at least one of the plurality of data tables is a single data table.

13. A non-transitory computer-readable medium encoded with a plurality of instruction executable by a processor, the plurality of instructions comprising:

instructions to receive a request to generate a multi-dimensional histogram on at least one of a plurality of data tables stored in an array of persistent storage devices;

instructions to retrieve the at least of the plurality of data tables;

instructions to identify a multi-dimensional dataset stored in the at least one of the plurality of data tables;

instructions to identify each dimension of the multi-dimensional dataset;

for each respective identified dimension;

instructions to sort the identified multi-dimensional dataset on values of the respective identified dimension;

instructions to partition the sorted dataset into a predetermined number of intervals associated with the respective identified dimension;

instructions to determine a number of rows for each interval; and

instructions to select a lower boundary value and an upper boundary value for each interval, wherein the upper boundary value is the highest value in each interval, wherein the lower boundary value for an interval having lowest sorted values is the lowest value in the interval, and the lower boundary value for each other interval is the upper boundary value of an interval having immediately preceding partitioned values;

instructions to store the lower boundary values, upper boundary values, and number of rows for each interval of each identified dimension as the histogram;

instructions to receive a query on the at least one of the plurality of data tables; and

instructions to generate a query response based on the histogram.

14. The non-transitory computer-readable medium of claim 13, wherein the plurality of instructions further comprises instructions to partition the sorted dataset into a predetermined number of intervals associated with the respective identified dimension, wherein the dataset is partitioned into equal-height intervals.

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

for each respective other identified dimension after a first identified dimension;

instructions to determine a predetermined number of intervals associated with the respective other identified dimension;

instructions to sort each interval generated on a dimension immediately prior to the respective other identified dimension based on values of the respective other dimension;

for each interval of the dimension immediately prior, generating an interval group, wherein each interval group comprises a number of intervals, wherein the number is the predetermined number of intervals associated with the respective other dimension;

for each interval group, instructions to determine a number of rows in each interval and to select a lower boundary value and an upper boundary value for each interval of the respective interval group, wherein the upper boundary value is the highest value in each interval of the respective interval group, wherein the lower boundary value for an interval having lowest sorted values is the lowest value in the interval of the respective interval group, and the lower boundary value for each other interval of the respective interval group is the upper boundary value of an interval of the respective interval group having immediately preceding partitioned values; and

instructions to store the lower boundary value, the upper boundary value, and the number of rows for each interval as the histogram.

16. The non-transitory computer-readable medium of claim 13, wherein the plurality of instructions further comprises for each dimension, instructions to select each interval in an order of values in each interval.

17. The non-transitory computer-readable medium of claim 13, wherein the at least one of the plurality of data tables is a single data table.