Equi-joins between split tables
A join operation between split data tables includes providing reduction data from first partitions to each partition among second partitions. The reduction data serves to identify actual values in one of the second partitions that also occur in one of the first partitions. Global IDs are assigned. Translation lists including the global IDs are sent to the first partitions. Each first partition and each second partition create globalized lists which can then be combined to generate respective first and second compiled lists. The join operation can then be conducted on the first and second compiled lists.
1. A method for a join operation between a first data table and a second data table based on a first attribute of the first data table and a second attribute of the second data table, the method comprising:
a computer processor in a first computer system generating reduction data for a first data partition, the first computer system being one among a plurality of first computer systems, the first data partition being one among a plurality of first data partitions that constitute the first data table and are distributed among the plurality of first computer systems, the reduction data comprising value IDs representative of actual values of the first attribute in the first data partition;
the computer processor sending the reduction data to a plurality of second computer systems which store a plurality of second data partitions that constitute the second data table;
the computer processor receiving a plurality of mappings from the plurality of second computer systems, each second computer system having value IDs from reduction data received from the plurality of first computer systems, each value ID being associated with a corresponding global ID that is common among the plurality of second computer systems, wherein a mapping in a given second computer system comprises a plurality of data pairs of a value ID and an associated global ID, wherein value IDs in the mapping are representative of actual values of the second attribute in the second data partition of the given second computer system; and
the computer processor generating a first globalized list comprising data pairs of a document ID from the first data partition paired with a global ID from one of the mappings received, wherein the value ID that is paired with the global ID represents an actual value of a first attribute of a data record in the first data partition identified by the document ID,
wherein a plurality of first globalized lists from one or more of the first computer systems are combined into a first compiled list,
wherein a plurality of second globalized lists from one or more of the second computer systems are combined into a second compiled list,
wherein the first and second compiled lists are joined based on global IDs in the first compiled list and the global IDs in the second compiled list.
2. The method of claim 1 wherein the value IDs in the reduction data for the first data partition are entries in a local dictionary stored in the first computer system.
3. The method of claim 1 further comprising the computer processor sending the globalized list to a recipient server, wherein the recipient server uses globalized lists received from the plurality of first computer systems to generate the first compiled list.
4. The method of claim 3 wherein the recipient server uses globalized lists received from the plurality of second computer systems to generate the second compiled list.
5. The method of claim 4 wherein the recipient server combines the first and second compiled lists based on the global IDs in the first compiled list and the global IDs in the second compiled list.
6. The method of claim 1 wherein each of the second globalized lists is generated using reduction data from each of the first data partitions.
7. A non-transitory computer readable storage medium having stored thereon computer executable program code, which when executed, will cause a computer processor in a first computer system to perform steps for a join operation between a first data table and a second data table based on a first attribute of the first data table and a second attribute of the second data table, the steps including:
generating reduction data for a first data partition, the first computer system being one among a plurality of first computer systems, the first data partition being one among a plurality of first data partitions that constitute the first data table and are distributed among the plurality of first computer systems, the reduction data comprising value IDs representative of actual values of the first attribute in the first data partition;
sending the reduction data to a plurality of second computer systems which store a plurality of second data partitions that constitute the second data table;
receiving a plurality of mappings from the plurality of second computer systems, each second computer system having value IDs from reduction data received from the plurality of first computer systems, each value ID being associated with a corresponding global ID that is common among the plurality of second computer systems, wherein a mapping in a given second computer system comprises a plurality of data pairs of a value ID and an associated global ID, wherein value IDs in the mapping are representative of actual values of the second attribute in the second data partition of the given second computer system; and
generating a first globalized list comprising data pairs of a document ID from the first data partition paired with a global ID from one of the mappings received, wherein the value ID that is paired with the global ID represents an actual value of a first attribute of a data record in the first data partition identified by the document ID,
wherein a plurality of first globalized lists from one or more of the first computer systems are combined into a first compiled list,
wherein a plurality of second globalized lists from one or more of the second computer systems are combined into a second compiled list,
wherein the first and second compiled lists are joined based on global IDs in the first compiled list and the global IDs in the second compiled list.
8. The non-transitory computer readable storage medium of claim 7 wherein the value IDs in the reduction data for the first data partition are entries in a local dictionary stored in the first computer system.
9. The non-transitory computer readable storage medium of claim 7 wherein the computer executable program code, which when executed, will further cause the computer processor to send the globalized list to a recipient server, wherein the recipient server uses globalized lists received from the plurality of first computer systems to generate the first compiled list.
10. The non-transitory computer readable storage medium of claim 9 wherein the recipient server uses globalized lists received from the plurality of second computer systems to generate the second compiled list.
11. The non-transitory computer readable storage medium of claim 10 wherein the recipient server combines the first and second compiled lists based on the global IDs in the first compiled list and the global IDs in the second compiled list.
12. The non-transitory computer readable storage medium of claim 7 wherein each of the second globalized lists is generated using reduction data from each of the first data partitions.
13. A first computer system comprising:
a computer processor;
a memory; and
executable program code stored in the memory to perform a join operation between a first data table and a second data table based on a first attribute of the first data table and a second attribute of the second data table, wherein the first data table is split into a plurality of first data partitions and the second data table is split into a plurality of second data partitions,
the memory storing one of the first data partitions,
the executable program code, which when executed by the computer processor, will cause the computer processor to:
generate reduction data for a first data partition, the first computer system being one among a plurality of first computer systems, the plurality of first data partitions being distributed among the plurality of first computer systems, the reduction data comprising value IDs representative of actual values of the first attribute in the first data partition;
send the reduction data to a plurality of second computer systems which store the plurality of second data partitions that constitute the second data table;
receive a plurality of mappings from the plurality of second computer systems, each second computer system having value IDs from reduction data received from the plurality of first computer systems, each value ID being associated with a corresponding global ID that is common among the plurality of second computer systems, wherein a mapping in a given second computer system comprises a plurality of data pairs of a value ID and an associated global ID, wherein value IDs in the mapping are representative of actual values of the second attribute in the second data partition of the given second computer system; and
generate a first globalized list comprising data pairs of a document ID from the first data partition paired with a global ID from one of the mappings received, wherein the value ID that is paired with the global ID represents an actual value of a first attribute of a data record in the first data partition identified by the document ID,
wherein a plurality of first globalized lists from one or more of the first computer systems are combined into a first compiled list,
wherein a plurality of second globalized lists from one or more of the second computer systems are combined into a second compiled list,
wherein the first and second compiled lists are joined based on global IDs in the first compiled list and the global IDs in the second compiled list.
14. The system of claim 13 wherein the value IDs in the reduction data for the first data partition are entries in a local dictionary stored in the first computer system.
15. The system of claim 13 wherein the computer executable program code, which when executed, will further cause the computer processor to send the globalized list to a recipient server, wherein the recipient server uses globalized lists received from the plurality of first computer systems to generate the first compiled list.
16. The system of claim 15 wherein the recipient server uses globalized lists received from the plurality of second computer systems to generate the second compiled list.
17. The non system of claim 16 wherein the recipient server combines the first and second compiled lists based on the global IDs in the first compiled list and the global IDs in the second compiled list.
18. The system of claim 13 wherein each of the second globalized lists is generated using reduction data from each of the first data partitions.