Method and system for partitioning data records for a join operation

A distributed computing system providing a distributed shared-nothing database environment, comprising:

• a plurality of computing instances connected over a network, at least some of which host data records of a left relation and a right relation of a database, wherein:
• the left relation comprises a plurality n of data tables {t1, t2, . . . tn}, each comprising a respective set of records and each being partitioned on a join key according to a respective table partitioning function {ft1, ft2, . . . ftn}, wherein the table partitions are hosted on respective ones of said computing instances;
• the right relation comprises a plurality of data records r to be partitioned on the join key;
• and
• said computing instances are programmed to co-operatively perform a method for partitioning the plurality of data records r for a join operation on the join key between said left relation and said right relation, comprising:
• a. sharing between the computing instances a set of equivalence classes {c1, c2, . . . cm}, each equivalence class comprising a plurality d of equivalence class partitions pc,i where 1≤i≤d and each equivalence class identifying a subset of the plurality n of data tables {t1, t2, . . . tn} which are partitioned according to equivalent partitioning functions;
• wherein two partitioning functions ft and fu of data tables t and u are equivalent if for each record r, ft(r) assigns the record to a table partition pt,i of table t with index i and fu(r) assigns the record to a table partition pu,j of table u with index j, where i=j and 1≤i,j≤d;
• whereby table partition pt,i of table t and table partition pu,j of table u are each mapped to an equivalence class partition pc,i of an equivalence class c ∈ {c1, c2, . . . cm} identifying tables t and u;
• b. for each record r of the right relation, and each tablet of the left relation in which the record r may appear, mapping the record to a respective equivalence class partition pc,i of the equivalence class c identifying the table t, and removing duplicate instances of records mapped to a given equivalence class partition pc,i, to produce a collection of unique tuples <r, pc,i>;
• c. identifying, for each equivalence class partition pc,i identified in one of the tuples <r, pc,i>, one or more associated computing instances hosting the equivalent table partition(s) pt,j of the left relation table(s) t identified in the equivalence class c;
• d. grouping the tuples <r, pc,i;
• > by their associated computing instance(s);
• and
• e. sending, to each associated computing instance, the records with which the computing instance is associated, wherein each record is accompanied by an identifier of the or each equivalence class partition to which it has been mapped.

A computer program product comprising instructions for execution by one or more computing instances of a distributed computing system providing a distributed shared-nothing database environment, in which:

• a plurality of said computing instances are connected over a network, at least some of which host data records of a left relation and a right relation of a database, wherein:
• the left relation comprises a plurality n of data tables {t1, t2, . . . tn}, each comprising a respective set of records and each being partitioned on a join key according to a respective table partitioning function {ft1, ft2, . . . ftn}, wherein the table partitions are hosted on respective ones of said computing instances;
• and
• the right relation comprises a plurality of data records r to be partitioned on the join key;
• wherein said instructions when executed by one or more of said computing instances cause said computing instances to co-operatively perform a method for partitioning the plurality of data records r for a join operation on the join key between said left relation and said right relation, comprising:
• a. sharing between the computing instances a set of equivalence classes {c1, c2, . . . cm}, each equivalence class comprising a plurality d of equivalence class partitions pc,i where 1≤i≤d and each equivalence class identifying a subset of the plurality n of data tables {t1, t2 . . . tn} which are partitioned according to equivalent partitioning functions;
• wherein two partitioning functions ft and fu of data tables t and u are equivalent if for each record r, ft(r) assigns the record to a table partition pt,i of table t with index i and fu(r) assigns the record to a table partition pu,i of table u with index j, where i=j and 1≤i,j≤d;
• whereby table partition pt,i of table t and table partition pu,i of table u are each mapped to an equivalence class partition p;
• of an equivalence class c=∈{c1, c2, . . . cm)} identifying tables t and u;
• b. for each record r of the right relation, and each tablet of the left relation in which the record r may appear, mapping the record to a respective equivalence class partition pc,i of the equivalence class c identifying the table t, and removing duplicate instances of records mapped to a given equivalence class partition pc,i to produce a collection of unique tuples <r, pc,i>;
• c. identifying, for each equivalence class partition pc,i identified in one of the tuples <r, pc,i>, one or more associated computing instances hosting the equivalent table partition(s) pt,i of the left relation table(s) t identified in the equivalence class c;
• d. grouping the tuples <r, pc,i> by their associated computing instance(s);
• and
• e. sending, to each associated computing instance, the records with which the computing instance is associated, wherein each record is accompanied by an identifier of the or each equivalence class partition to which it has been mapped.