Patent ID: 7685193

Claim:
A method of distributing across a plurality of P processing nodes a database join operation between a first table having a total of M1 rows and a second table having a total of M2 rows, wherein M1 and M2 are integers, wherein said join operation involves forming K combinations of rows from the first and second tables, where K is formed from the integer multiplication of M1 and M2 such that K=M1×M2, wherein said join operation comprises a join condition other than an equi-join, the method comprising: allocating across the plurality of processing nodes the K combinations of rows from the first and second tables, wherein each node stores a subset of said M1 rows from the first table and a subset of said M2 rows from the second table, such that each of said M1 rows is stored on more than one but less than P nodes and each of said M2 rows is stored on more than one but less than P nodes, and wherein each of said K combinations is present on one of said nodes; performing for each processing node the join operation in respect of all combinations of rows from the subsets of rows allocated to that processing node; and collating results across all the processing nodes to complete the join operation, wherein the processing nodes are logically configured in a rectangular grid, and the M1 rows from the first table are allocated in accordance with a lateral distribution, such that all the processing nodes in a row of the grid are allocated the same subset of rows from the first table, and wherein the M2 rows from the second table are allocated in accordance with a lateral distribution orthogonal to the first table, such that all the processing nodes in a column of the grid are allocated the same subset of rows from the second table.