Unique value calculation in partitioned table

Patent metadata

Field	Value
Publication number	US-9697273-B2
Application number	US-201414453401-A
Country	US
Kind code	B2
Filing date	Aug 6, 2014
Priority date	Dec 23, 2011
Publication date	Jul 4, 2017
Grant date	Jul 4, 2017

Abstract

An estimation algorithm can generate a uniqueness metric representative of data in a database table column that is split across a plurality of data partitions. The column can be classified as categorical if the uniqueness metric is below a threshold and as non-categorical if the uniqueness metric is above the threshold. A first estimation factor can be assigned to the column if the column is classified as categorical or a larger second estimation factor can be assigned if the column is non-categorical. A cost estimate for system resources required to perform a database operation on the database table can be calculated. The cost estimate can include an estimated total number of distinct values in the column across all of the plurality of data partitions determined using the assigned first estimation factor or second estimation factor and a number of rows in the table as inputs to an estimation function.

First claim

What is claimed is:

1. A computer program product comprising a non-transitory machine-readable medium storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:
applying an estimation algorithm by the at least one programmable processor, the estimation algorithm accessing a dictionary of at least one data partition of a plurality of data partitions containing data of a column of a database table to generate a uniqueness metric representative of the data in the column;
assigning, by the at least one programmable processor, a first estimation factor to a column of a database table when the uniqueness metric is above a threshold value and assigning a second estimation factor to the column when the uniqueness metric is not above the threshold value, the second estimation factor being larger than the first estimation factor;
calculating, by the at least one programmable processor, a cost estimate for system resources required to perform a database operation on the database table, the cost estimate comprising an estimated total number of distinct values in the column across all of the plurality of data partitions determined using the assigned first estimation factor or second estimation factor and a number of rows in the table as inputs to an estimation function; and
performing, by the at least one programmable processor, the database operation involving at least one of the column and other columns of the database table in an optimal order, the performing comprising applying an operation plan developed using the cost estimate.

2. A computer program product as in claim 1 , wherein the operations further comprise displaying the cost estimate via a display device associated with a computing system or device, sending an electronic message containing the cost estimate to a user or to another machine, and/or generating a report that includes the cost estimate.

3. A computer program product as in claim 1 , wherein the database operation comprises a join.

4. A computer program product as in claim 1 , wherein the estimation algorithm comprises:
selecting one data partition of the plurality of data partitions;
querying a dictionary of the selected data partition for a total number of unique values in the column in the selected data partition, the dictionary comprising a listing of unique values of the column in the selected data partition;
calculating a ratio of the total number of unique values to a number of rows of the column contained in the selected data partition;
assuming that the ratio is representative of a distribution of unique values in all other data partitions of the plurality of data partitions; and
returning the calculated ratio as the uniqueness metric.

5. A computer program product as in claim 1 , wherein the estimation algorithm comprises:
querying a dictionary on each of two or more data partitions of the plurality of data partitions, the dictionary comprising a listing of unique values of the column in each of the two or more data partitions, the querying comprising requesting a random sample comprising a preset number of the unique values in the column on each of the two or more data partitions;
comparing the random samples returned from the dictionary on each of the two or more data partitions; and
returning the uniqueness metric as a degree of dissimilarity between the random samples.

6. A computer program product as in claim 1 , wherein the estimation algorithm comprises:
requesting that a dictionary from each of one or more selected data partitions of the plurality of data partitions return a respective Bloom filter of a same, specific size, each dictionary comprising a listing of unique values of the column in its respective data partitions; and
returning the uniqueness metric based on a degree to which the returned Bloom filter from the one or more selected data partitions is filled.

7. A system comprising:
at least one programmable processor; and
a machine-readable medium storing instructions that, when executed by the at least one processor, cause the at least one programmable processor to perform operations comprising:
applying an estimation algorithm by the at least one programmable processor, the estimation algorithm accessing a dictionary of at least one data partition of a plurality of data partitions containing data of a column of a database table to generate a uniqueness metric representative of the data in the column;
assigning, by the at least one programmable processor, a first estimation factor to a column of a database table when the uniqueness metric is above a threshold value and assigning a second estimation factor to the column when the uniqueness metric is not above the threshold value, the second estimation factor being larger than the first estimation factor;
calculating, by the at least one programmable processor, a cost estimate for system resources required to perform a database operation on the database table, the cost estimate comprising an estimated total number of distinct values in the column across all of the plurality of data partitions determined using the assigned first estimation factor or second estimation factor and a number of rows in the table as inputs to an estimation function; and
performing, by the at least one programmable processor, the database operation involving at least one of the column and other columns of the database table in an optimal order, the performing comprising applying an operation plan developed using the cost estimate.

8. A system as in claim 7 , wherein the operations further comprise displaying the cost estimate via a display device associated with a computing system or device, sending an electronic message containing the cost estimate to a user or to another machine, and/or generating a report that includes the cost estimate.

9. A system as in claim 7 , wherein the database operation comprises a join.

10. A system as in claim 7 , wherein the estimation algorithm comprises:
selecting one data partition of the plurality of data partitions;
querying a dictionary of the selected data partition for a total number of unique values in the column in the selected data partition, the dictionary comprising a listing of unique values of the column in the selected data partition;
calculating a ratio of the total number of unique values to a number of rows of the column contained in the selected data partition;
assuming that the ratio is representative of a distribution of unique values in all other data partitions of the plurality of data partitions; and
returning the calculated ratio as the uniqueness metric.

11. A system as in claim 7 , wherein the estimation algorithm comprises:
querying a dictionary on each of two or more data partitions of the plurality of data partitions, the dictionary comprising a listing of unique values of the column in each of the two or more data partitions, the querying comprising requesting a random sample comprising a preset number of the unique values in the column on each of the two or more data partitions;
comparing the random samples returned from the dictionary on each of the two or more data partitions; and
returning the uniqueness metric as a degree of dissimilarity between the random samples.

12. A system as in claim 7 , wherein the estimation algorithm comprises:
requesting that a dictionary from each of one or more selected data partitions of the plurality of data partitions return a respective Bloom filter of a same, specific size, each dictionary comprising a listing of unique values of the column in its respective data partitions; and
r

Assignees

• Fricke Lars
• Hwang Sangyong
• Sap Se

Inventors

• Fricke Lars
• Hwang Sangyong

Classifications

• G06F17/30657

  Physics · mapped topic

• G06F17/30545

  Physics · mapped topic

• G06F17/30864

  Physics · mapped topic

• G06F17/30595 Primary

  Physics · mapped topic

• G06F17/30445

  Physics · mapped topic