Avoidance of intermediate data skew in a massive parallel processing environment

Patent metadata

Field	Value
Publication number	US-9569494-B2
Application number	US-201414312879-A
Country	US
Kind code	B2
Filing date	Jun 24, 2014
Priority date	Dec 31, 2013
Publication date	Feb 14, 2017
Grant date	Feb 14, 2017

Abstract

A computer-implemented method for minimizing join operation processing time within a database system based on estimated joined table spread of the database system has been provided. The computer-implemented method includes estimating value distribution of data in a joined table, wherein the joined table is a result of join operation between two instances of tables of a database system. The computer-implemented method further includes determining boundaries for partitioning at least one range of attributes of the estimated value distribution, wherein the boundaries for partitioning at least one range of attributes of the estimated value distribution corresponds to a same number of rows of the joined table. The computer-implemented method further includes determining at least one assignment of the determined partition of the at least one range of attributes to processing units of the database system.

First claim

What is claimed is:

1. A computer system for minimizing join operation processing time within a database system based on estimated joined table spread of the database system, the computer system comprising:
one or more processors, one or more computer-readable memories, one or more computer-readable tangible storage devices and program instructions which are stored on at least one of the one or more storage devices for execution by at least one of the one or more processors via at least one of the one or more memories, the program instructions comprising:
program instructions to estimate value distribution of data in a joined table, wherein the joined table is a result of a join operation between two instances of tables of a database system and the estimated value distribution data is based on a count of number of rows with a particular value of the two instances of the tables of the join operation and calculation of a number of rows of the joined table;
program instructions to determine boundaries for partitioning at least one range of attributes of the estimated value distribution of data, wherein the boundaries for partitioning is based on a density function distribution of the joined table, and wherein the density distribution function represents a spread of data within a data column of the joined table, the joined table being a result of a join operation between two instances of tables of the database system;
program instructions to determine at least one assignment of the determined partition of the at least one range of attributes to processing units of the database system;
program instructions to provide parameterized functions that represent the estimated value distribution;
program instructions to determine the total number of rows in the join table;
program instructions to determine a set of estimates for the number of rows in the join table in a first set of consequent common attribute value ranges based on the parametrized functions;
program instructions to determine a parametrized function representing the value distribution of the common attribute in the join table by solving a first equation system involving definite integrals of over the first set of consequent attribute ranges and the set of estimates for numbers of rows; and
program instructions to determine a second set of consequent common attribute value ranges by solving a second equation system involving definite integrals of over the second set of consequent common attribute value ranges, each definite integral equalling the total number of rows in the join table divided by the number of processing nodes.

2. The computer system according to claim 1 , wherein the estimated value distribution data is a density function based on values of columns of the joined table of the database system.

3. The computer system according to claim 2 , further includes program instructions to split the joined table, into at least one partitioning range of attributes of the estimated value distribution data.

4. The computer system according to claim 1 , wherein the assignment of the determined partition of the at least one range of attributes is based on defined hash functions of data distribution within the processing units.

5. The computer system according to claim 4 , wherein the defined hash functions are adaptive to map value of columns within the processing units.

6. The computer system according to claim 5 , wherein the defined hash functions decreases intermediate processing impact of query execution time of the processing units of a database system.

7. A computer program product for minimizing join operation processing time within a database system based on estimated joined table spread of the database system, the computer program product comprising:
one or more computer-readable tangible storage devices and program instructions stored on at least one of the one or more storage devices, the program instructions comprising:
program instructions to estimate value distribution of data in a joined table, wherein the joined table is a result of a join operation between two instances of tables of a database system and the estimated value distribution data is based on a count of number of rows with particular value of the two instances of the tables of the join operation and calculation of number of rows of the joined table;
program instructions to determine boundaries for partitioning at least one range of attributes of the estimated value distribution of data, wherein the boundaries for partitioning is based on a density function distribution of the joined table, and wherein the density distribution function represents a spread of data within a data column of the joined table, the joined table being a result of a join operation between two instances of tables of the database system;
program instructions to determine at least one assignment of the determined partition of the at least one range of attributes to processing units of the database system;
program instructions to provide parameterized functions that represent the estimated value distribution;
program instructions to determine the total number of rows in the join table;
program instructions to determine a set of estimates for the number of rows in the join table in a first set of consequent common attribute value ranges based on the parametrized functions;
program instructions to determine a parametrized function representing the value distribution of the common attribute in the join table by solving a first equation system involving definite integrals of over the first set of consequent attribute ranges and the set of estimates for numbers of rows; and
program instructions to determine a second set of consequent common attribute value ranges by solving a second equation system involving definite integrals of over the second set of consequent common attribute value ranges, each definite integral equalling the total number of rows in the join table divided by the number of processing nodes.

8. The computer program product according to claim 7 , wherein the estimated value distribution data is a density function based on values of columns of the joined table of the database system.

9. The computer program product according to claim 8 , further includes program instructions to split the joined table, into at least one partitioning range of attributes of the estimated value distribution data.

10. The computer program product according to claim 7 , wherein the assignment of the determined partition of the at least one range of attributes is based on defined hash functions of data distribution within the processing units.

11. The computer program product according to claim 10 , wherein the defined hash functions are adaptive to map value of columns within the processing units.

Assignees

• IBM

Inventors

• Gaza Lukasz
• Gruszecki Artur M
• Kazalski Tomasz
• Milka Grzegorz S
• Skibski Konrad K
• Stradomski Tomasz

Classifications

• G06F16/24544 Primary

  Join order optimisation · CPC title

• G06F16/2255

  Hash tables · CPC title

• G06F16/2456

  Join operations · CPC title

• G06F16/24561

  Intermediate data storage techniques for performance improvement · CPC title

• G06F16/24545

  Selectivity estimation or determination · CPC title