Performing database joins in distributed data processing systems

Abstract

A computer-implemented method for efficiently performing a database join in a distributed data processing system comprising multiple computational nodes, the method comprising determining a first set of one or more columns of a first database table and a second set of one or more columns of a second database table on which the join is to be performed; estimating a size of the rows of the first table which have a particular combination of values in the first set of columns; computing a salt factor n based on the estimated size of rows and further based on a processing capacity of a computational node of the distributed data processing system; assigning one of n different salt values to each row of the first table having the particular combination of values in the first set of columns; for each row of the second table having the particular combination of values in the second set of columns into n rows, expanding the row into n row, and assigning to each expanded row a different one of the n salt values; and performing a join operation on the modified first and second tables, wherein the rows of the first and second tables have the same combination of values in the first and second sets of columns and the same salt value are joined on the same computational node.