US 8,510,280 B2 · System, method, and computer-readable medium for dynamic detection and management of data skew in parallel join operations

Abstract

A system, method, and computer-readable medium for dynamic detection and management of data skew in parallel join operations are provided. Rows allocated to processing modules involved in a join operation are redistributed among the processing modules by a hash redistribution of the join attributes. Receipt by a processing module of an excessive number of redistributed rows having a skewed value on the join attribute is detected by a processing module which notifies other processing modules of the skewed value. Processing modules then terminate redistribution of rows having a join attribute value matching the skewed value and either store such rows locally or duplicate the rows. The processing module that has received an excessive number of redistributed rows removes rows having a skewed value of the join attribute from a redistribution spool allocated thereto and duplicates the rows to each of the processing modules. The join operation is completed by performing a local join at each processing module and merging the results of the local join operations.

Claims26

Dependent claims

A method of performing a parallel join operation in a parallel processing system, comprising:

distributing a respective set of rows of a first table and a second table involved in a join operation to each of a plurality of processing modules, wherein the join operation comprises a join on a first column of the first table and a second column of the second table;
allocating a respective first spool and a respective second spool to each of the plurality of processing modules;
hashing at least a portion of the respective set of rows of the first table on the first column and at least a portion of the respective set of rows of the second table on the second column by each of the plurality of processing modules;
redistributing, by each of the plurality of processing modules, at least a portion of the rows of the respective distributed set of rows of the first table and the second table distributed thereto based on a hash value of one of the first column and the second column to one of the plurality of processing modules;
thereafter, detecting, by a first processing module of the plurality of processing modules, a skewed value of the first column;
and
transmitting a notification, by the first processing module, to each of the plurality of processing modules of the skewed value of the first column after the detecting by the first processing module.

4 more elements

A non-transient computer-readable medium including computer-executable instructions for execution by a processing system, the computer-executable instructions for performing a parallel join operation in a parallel processing system, the computer-executable instructions, when executed, cause the processing system to:

distribute a respective set of rows of a first table and a second table involved in a join operation to each of a plurality of processing modules, wherein the join operation comprises a join on a first column of the first table and a second column of the second table;
allocate a respective first spool and a respective second spool to each of the plurality of processing modules;
hash at least a portion of the respective set of rows of the first table on the first column and at least a portion of the respective set of rows of the second table on the second column by each of the plurality of processing modules;
redistribute, by each of the plurality of processing modules, at least a portion of the rows of the distributed respective set of rows of the first table and the second table distributed thereto based on a hash value of one of the first column and the second column to one of the plurality of processing modules;
thereafter, detect, by a first processing module of the plurality of processing modules, a skewed value of the first column;
and
transmit a notification, by the first processing module, to each of the plurality of processing modules of the skewed value of the first column after the detecting by the first processing module.

4 more elements

A database management system, comprising:

a plurality of processing modules;
at least one storage device to which respective sets of rows of a first table and a second table involved in a join operation are allocated to each of the plurality of processing modules, wherein the join operation comprises a join on a first column of the first table and a second column of the second table;
and at least one memory device that stores a respective first spool and a respective second spool allocated to each of the plurality of processing modules, wherein each of the plurality of processing modules hashes at least a portion of the respective set of rows of the first table on the first column and at least a portion of the respective set of rows of the second table on the second column, redistributes at least a portion of the rows of the distributed respective set of rows of the first table and the second table distributed thereto based on a hash value of one of the first column and the second column to one of the plurality of processing modules, and wherein after the redistributing a first processing module of the plurality of processing modules detects a skewed value of the first column and transmits a notification to each of the plurality of processing modules of the skewed value of the first column after the detecting by the first processing module.

Dependencies are inferred from the claim text.

System, method, and computer-readable medium for dynamic detection and management of data skew in parallel join operations

Life of this patent

System, method, and computer-readable medium for dynamic detection and management of data skew in parallel join operations

Life of this patent

Abstract

Claims26