Equi-joins between split tables

Abstract

A join operation between split data tables includes providing value IDs. For each of the value IDs, a unique global ID may be associated with the value ID when the actual value represented by the value ID occurs among actual values comprising the second attribute of the second partition. For each identified unique global ID, the identified unique global ID may be paired with a document ID of a data record contained in a second partition stored at the second server in which the actual value in the data record is represented by the value ID associated with the identified unique global ID.

Claims

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 server among a plurality of second servers receiving from a plurality of first servers a plurality of value IDs associated with a plurality of first partitions that comprise the first data table, the first partitions distributed among the first servers, the first servers different from the second servers; and for a given second partition among a plurality of second partitions that comprise the second data table, distributed among the plurality of second servers, performing at one of the second servers operations including: for each of the value IDs, identifying a unique global ID associated with the value ID when an actual value represented by the value ID occurs among actual values comprising the second attribute of the second partition; and for each identified unique global ID, pairing the identified unique global ID with a document ID of a data record contained in a second partition stored at the second server in which the actual value in the data record is represented by the value ID associated with the identified unique global ID, wherein a plurality of first globalized lists from one or more of the first partitions are combined into a first compiled list, wherein a plurality of second globalized lists from one or more of the second partitions 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 a globalized list from one of the first partitions comprises a document ID paired with a global ID from one of the second partitions.

3. The method of claim 2, wherein the document ID identifies a data record in the first partition in which the actual value of its first attribute is represented by the value ID associated with the global ID from one of the second partitions.

4. The method of claim 1, wherein each of the second partitions is associated with a pairing the associates value IDs with unique global IDs.

5. The method of claim 1, further comprising sending each of the second globalized lists to a recipient server, the recipient server generating the second combined list from the second globalized lists received.

6. The method of claim 1, wherein multiple occurrences of an actual value in a global list of a given partition are associated with the same global ID.

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 server among a plurality of second servers 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: receiving from a plurality of first servers a plurality of value IDs associated with a plurality of first partitions that comprise the first data table, the first partitions distributed among the first servers, the first servers different from the second servers; and for a given second partition among a plurality of second partitions that comprise the second data table, distributed among the plurality of second servers, performing operations including: for each of the value IDs, identifying a unique global ID associated with the value ID when an actual value represented by the value ID occurs among actual values comprising the second attribute of the second partition; and for each identified unique global ID, pairing the identified unique global ID with a document ID of a data record contained in a second partition stored at the second server in which the actual value in the data record is represented by the value ID associated with the identified unique global ID, wherein a plurality of first globalized lists from one or more of the first partitions are combined into a first compiled list, wherein a plurality of second globalized lists from one or more of the second partitions 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 a globalized list from one of the first partitions comprises a document ID paired with a global ID from one of the second partitions.

9. The non-transitory computer readable storage medium of claim 8, wherein the document ID identifies a data record in the first partition in which the actual value of its first attribute is represented by the value ID associated with the global ID from one of the second partitions.

10. The non-transitory computer readable storage medium of claim 7, wherein each of the second partitions is associated with a pairing the associates value IDs with unique global IDs.

11. The non-transitory computer readable storage medium of claim 7, further comprising sending each of the second globalized lists to a recipient server, the recipient server generating the second combined list from the second globalized lists received.

12. The non-transitory computer readable storage medium of claim 7, wherein multiple occurrences of an actual value in a global list of a given partition are associated with the same global ID.

13. A first server among a plurality of second servers, the first server 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, the executable program code, which when executed by the computer processor, will cause the computer processor to: receive from a plurality of first servers a plurality of value IDs associated with a plurality of first partitions that comprise the first data table, the first partitions distributed among the first servers, the first servers different from the second servers; and for a given second partition among a plurality of second partitions that comprise the second data table, distributed among Hall the plurality of second servers, perform operations including: for each of the value IDs, identifying a unique global ID associated with the value ID when an actual value represented by the value ID occurs among actual values comprising the second attribute of the second partition; and for each identified unique global ID, pairing the identified unique global ID with a document ID of a data record contained in a second partition stored at the second server in which the actual value in the data record is represented by the value ID associated with the identified unique global ID, wherein a plurality of first globalized lists from one or more of the first partitions are combined into a first compiled list, wherein a plurality of second globalized lists from one or more of the second partitions 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 a globalized list from one of the first partitions comprises a document ID paired with a global ID from one of the second partitions.

15. The system of claim 14, wherein the document ID identifies a data record in the first partition in which the actual value of its first attribute is represented by the value ID associated with the global ID from one of the second partitions.

16. The non system of claim 13, wherein each of the second partitions is associated with a pairing the associates value IDs with unique global IDs.

17. The system of claim 13, further comprising sending each of the second globalized lists to a recipient server, the recipient server generating the second combined list from the second globalized lists received.

18. The system of claim 13, wherein multiple occurrences of an actual value in a global list of a given partition are associated with the same global ID.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 represents a high level flow of data among database table partitions to conduct a join operation in accordance with principles of the present invention.

(2) FIG. 1A show a general example of some details in a partition.

(3) FIG. 2 illustrates a system diagram that can incorporate embodiments of the present invention.

(4) FIGS. 3 and 3A are process flows for processing among partitions in accordance with principles of the present invention.

(5) FIG. 4 illustrates an example of data tables to facilitate an explanation of aspects of embodiments of the present invention.

(6) FIG. 4A illustrates a join operation in a non-distributed configuration of the data tables of FIG. 4.

(7) FIGS. 5 and 5A illustrate the data tables of FIG. 4 in a split and distributed configuration.

(8) FIG. 6 illustrates some processing in each A partition.

(9) FIGS. 7 and 7A-7D illustrate data manipulations for a join operation in accordance with principles of the present invention, in one of the B partitions.

(10) FIGS. 8 and 8A-8E illustrate data manipulations for a join operation in accordance with principles of the present invention, in another of the B partitions.

(11) FIG. 9 compares the results of translation matrices from each B partition.

(12) FIGS. 10A and 10B illustrate generating value ID lists in accordance with embodiments of the present invention.

(13) FIGS. 11A-12B illustrate generating globalized lists.

(14) FIG. 13 shows a final step in the join operation of split data tables.

(15) FIGS. 14A-14C and 15 illustrate some basic principles and examples of data tables.

DETAILED DESCRIPTION

(16) In the following description, for purposes of explanation, numerous examples and specific details are set forth in order to provide a thorough understanding of the present invention. It will be evident, however, to one skilled in the art that the present invention as defined by the claims may include some or all of the features in these examples alone or in combination with other features described below, and may further include modifications and equivalents of the features and concepts described herein.

(17) Aspects of the present invention relate to performing a join operation between two distributed data tables. In particular, an equi-join operation may be performed between data tables that are split into multiple distributed partitions. FIG. 1 is a high level view of an illustrative embodiment of the present invention. Partitions A.sub.1-A.sub.n, constitute N partitions of a data table A and can be distributed among some number (<=N) of data severs. For example, suppose data table A having 1000 rows (records) of data is split into four distributed partitions; partition A.sub.1 might store a portion of the data table such as rows 1-200, partition A.sub.2 might store rows 201-477 of the data table, partition A.sub.3 might store rows 478-756, and partition A.sub.4 might store rows 757-1000. Partitions B.sub.1-B.sub.m similarly constitute M partitions of a split data table B that can be distributed among some number (<=M) of data servers. In accordance with embodiments, there are no restrictions relating to the distribution of partitions A.sub.1-A.sub.n and B.sub.1-B.sub.m among data servers (e.g., a data server may host partitions from data table A and from data table B), or to the number of data servers that are configured for hosting the partitions.

(18) Referring to FIG. 2 for a moment, a typical computer system configuration in accordance with embodiments of the present invention is shown. In embodiments, a plurality of servers 210, 215, and 231-235 may host or otherwise store and maintain distributed partitions for one or more split data tables. For example, partition A.sub.1 might be stored in server 210, partition A.sub.2 might be stored in server 231, partition B.sub.1 might be stored in server 234, and so on. For convenience, it is noted that the term “partition” can be used in several related contexts. The term “partition” may refer to the data that constitute a given portion of a data table, or to components of the storage system containing such data. The term “partition” may also refer generally to the server that is hosting the given portion of the data table, or to software employed to manipulate, maintain, and otherwise manage the data that constitute the given portion of the data table. It will be appreciated that the specific meaning of the term “partition” can be inferred from its usage and context.

(19) Communication networks can connect the servers 210, 215, and 231-235. For example, a local network 220 may connect servers 210, 215. A publicly accessed network (e.g., the Internet) 230 may connect server 231-235. The local network 220 may be connected to the publicly accessed network 230, allowing communication among the database servers 210, 215, and 231-235.

(20) Each server (e.g., 210) may include a data processor subsystem 201 that may comprise one or more data processing units. A memory subsystem 202 may comprise random access memory (usually volatile memory such as DRAM) and non-volatile memory such as FLASH memory, ROM, and so on. The memory subsystem 202 may store computer executable programs, which when executed can cause the data processing subsystem 201 to operate as a database system in accordance with aspects of the present invention disclosed herein. A storage subsystem 203 may comprise one or more mass storage devices such as hard disk drives and the like. The storage subsystem 203 may include remote storage systems; e.g., for data mirroring, remote backup and such. A network interface subsystem 204 can provide access to the local network 220 and provide users with access to the server 210. A system of buses 205 can interconnect the foregoing subsystems, providing control lines, data lines, and/or voltage supply lines to/from the various subsystems. The server 210 may include a suitable display(s) 212 and input devices 211 such as a keyboard and a mouse input device.

(21) FIGS. 1 and 3 represent a high level flow of an execution plan for performing a join operation of two data tables A and B that are split and distributed, in accordance with aspects of the present invention. The join operation is predicated on a join condition that specifies an attribute(s) common to the two data tables A and B, which will be referred to as the “specified attribute”. For example, consider an Inventory data table and a Sales data table; an attribute in the Inventory data table might be Stocked_Items and an attribute in the Sales data table might be Purchased_Items. A join operation between these two data tables might specify a join condition such as “Inventory.Stocked_hems=Sales.Purchased_Items”. The Stocked_Items attribute would be the “specified attribute” in the Inventory data table, and the Purchased_Items attribute would be the “specified attribute” in the Sales data table.

(22) In embodiments, the two data tables A and B may be split into respective partitions A.sub.1-A.sub.n and B.sub.1-B.sub.m. Referring for a moment to FIG. 1A, a generalized example of a data table partition is shown. The partition comprises n rows taken from a larger data table. Each row stored in the partition comprises m attributes. The partition may include one or more dictionaries, each corresponding to an attribute. For example, FIG. 1A shows that a dictionary is defined for attribute 1 and another dictionary is defined for attribute 2. The value IDs for attribute 1 and attribute 2, respectively, are stored in the partition rather than their associated actual values. As mentioned above, the dictionary(ies) in a given partition may be local to that partition. In other words, the value IDs stored in the dictionary(ies) of one partition may not correlate with the value IDs of dictionary(ies) of another partition, even though they may contain identical actual values.

(23) Turning to the execution plan illustrated in FIG. 3, a brief overview of processing a join operation involving split (partitioned) data tables will be given. Reference will be made to partitioned data tables A and B illustrated in FIG. 1.

(24) In a step 302, each partition A.sub.x among the partitions A.sub.1-A.sub.n generates reduction data 102 and sends a copy of the generated reduction data to each partition B.sub.1-B.sub.m. Accordingly, each partition B.sub.1-B.sub.m receives reduction data 102 from each partition A.sub.1-A.sub.n. In embodiments, the reduction data 102 for partition A.sub.x comprises value IDs associated with actual values of instances of the specified attribute that occur in the partition. The step 302 can be performed by each partition A.sub.x independently of the other partitions A.sub.1-A.sub.n; there is no need to synchronize or otherwise coordinate their activity. In other words, individual reduction data 102 from each partition A.sub.1-A.sub.n can be communicated to the partitions B.sub.1-B.sub.m in parallel fashion.

(25) In a step 304, each partition B.sub.x among the partitions B.sub.1-B.sub.m associates a global ID for each actual value of the specified attribute in the partition that also occurs in at least one of the partitions A.sub.1-A.sub.n. In embodiments, the reduction data 102 received from the partitions A.sub.1-A.sub.n can be used to perform this step. Multiple occurrences of a given actual value in the partition B.sub.x will be associated with the same global ID. In accordance with the present invention, occurrences of a given actual value among all the partitions of data table A and data table B can be associated with the same global ID. This aspect of the present invention will be discussed in more detail in connection with a specific example discussed below.

(26) In a step 306, each partition B.sub.x among the partitions B.sub.1-B.sub.m translates the value IDs that comprise the reduction data 102 from each partition A.sub.1-A.sub.n, producing a set of translated value IDs 104 for each partition A.sub.1-A.sub.n. Consider a partition A.sub.x, for example. Translated value IDs 104 for partition A.sub.x are generated from the value IDs that comprise the reduction data 102 received from that partition. In particular, each value ID in the reduction data 102 is first associated with an actual value stored in the partition A.sub.x. Next, if that actual value also occurs in the partition B.sub.x, then the value ID is “translated” by pairing it with the global ID that is associated with that actual value. This translation is attempted for each value ID in the reduction data 102 of partition A.sub.x. Accordingly, the translated value IDs 104 will comprise one or more values IDs that are paired with respective global IDs. Some value IDs in the reduction data 102 may be associated with actual values which do not occur in the partition B.sub.x and so no translation is made. The translated value IDs 104 are then sent to the partition A.sub.x (backward communication). This step is performed for each of the partitions A.sub.1-A.sub.x, and by each partition B.sub.1-B.sub.m. This aspect of the present invention will be discussed in more detail below.

(27) In a step 308, each partition B.sub.x among the partitions B.sub.1-B.sub.m generates a globalized list 106 that identifies one or more rows stored in the partition. Each row that is identified in the globalized list 106 contains an actual value of the specified attribute which also occurs in one of the partitions A.sub.1-A.sub.N (based on the reduction data 102 as explained above). In an embodiment, the globalized list 106 may include a 2-tuple (a data pair) comprising a Doc ID and a global ID. The Doc IDs in the 2-tuples of the globalized list 106 identify specific rows in the partition B.sub.x for which the actual values of the specified attribute also occur in one of the partitions A.sub.1-A.sub.n. The global IDs in the 2-tuples are associated with those actual values. As a side note, the term “Doc ID” will be used herein to refer to an identifier that identifies a particular row in a data table. This aspect of the present invention will be made more clear in the specific example discussed below.

(28) In embodiments, the globalized list 106 can be sent to a receiving (recipient) data server. For example, any data server 210, 215, 231-235 can be designated as the recipient data server. The recipient data server can be selected from among a population of candidate data servers in round-robin fashion, or selected randomly. In an embodiment, a particular data server can be designated as always being the recipient data server rather than employing a round robin selection process.

(29) In a step 310, each partition A.sub.x among the partitions A.sub.1-A.sub.n generates a globalized list 108 based on the translated value IDs 104 received from each of the partitions B.sub.1-B.sub.m. The globalized list 108 identifies one or more rows stored in the partition A.sub.x. In an embodiment, the globalized list 108 includes a 2-tuple (a data pair) for each identified row. Each 2-tuple in turn comprises a Doc ID and a global ID. The Doc IDs identify one or more rows of the partition A.sub.x. The global IDs are obtained from the translated value IDs 104 received from partitions B.sub.1-B.sub.m. In embodiments, the globalized list 108 identifies rows in partition A.sub.x for which actual values (represented by the global IDs) of the specified attribute also occur in one of the partitions B.sub.1-B.sub.m. This aspect of the present invention will be discussed in more detail below. The globalized list 108 can be sent to a recipient data server. In an embodiment, the recipient data server can be the same data server employed to receive globalized lists 106 from partitions B.sub.1-B.sub.m. In an embodiment, a different data server can be employed.

(30) In a step 312, when the recipient data server has received all of the globalized lists 106 from partitions B.sub.1-B.sub.m, a compiled B list 112 can be created. The compiled B list 112 comprises pairs of Doc IDs and global IDs, and identifies those rows among partitions B.sub.1-B.sub.m for which the actual values of the specified attribute also occur in at least one of the partitions A.sub.1-A.sub.n. Similarly, when the recipient data server has received all of the globalized lists 108 from partitions A.sub.1-A.sub.n, a compiled A list 114 can be created. The compiled A list 114 comprises pairs of Doc IDs and global IDs, and identifies those rows among partitions A.sub.1-A.sub.n for which the actual values of the specified attribute also occur in at least one of the partitions B.sub.1-B.sub.m.

(31) In a step 314, a join operation is performed between the compiled A list 114 and the compiled B list 112, where the join condition is based on the global ID attribute that is common to the compiled A list and the compiled B list. Since the global IDs are associated with actual values of the specified attribute, the join operation performed in this step is equivalent to the desired join operation between the specified attributes.

(32) Following will be a more detailed discussion of the foregoing processing steps shown in FIG. 3, explained in connection with a particular example to facilitate further understanding of aspects of the present invention. Consider first the case of a join operation for non-partitioned data tables.

(33) FIG. 4 shows two data tables, data table A 402 and data table B 404. Data table A specifies X attributes, where the first attribute is a Doc ID attribute and the second attribute is a Name attribute. Similarly, data table B specifies Y attributes also including a Doc ID attribute and a Name attribute. The Doc ID attribute identifies each row in a respective data table and so its actual values can be arbitrarily assigned so long as they serve to uniquely identify each row in that data table. Each data table A, B may have one or more dictionaries defined on their attributes in order to reduce data storage requirements.

(34) Suppose a join operation is performed on the data tables A and B, predicated on the Name attribute in data table A being equal to the Name attribute in data table B. An execution plan for the join operation may involve generating an index on the Name attribute for each data table A and B. For example, FIG. 4A shows Index A 414 and Index B 412, represented as tables comprising the Doc ID attribute and the Name attribute. The figure shows a result 422 of the join operation, which is a table comprising a Doc ID A attribute and a Doc ID B attribute. The Doc IDs identify respective rows in data tables A and B that have the same actual values in their Name attribute.

(35) Referring to FIGS. 5 and 5A, consider an example of the split configurations of the data tables A and B shown in FIG. 4. FIG. 5 shows data table A having been partitioned into partitions A.sub.1, A.sub.2 (502a, 502b) and data table B being partitioned into partitions B.sub.1, B.sub.2 (504a, 504b). FIG. 5A shows dictionaries 512a, 512, b, 514a, 514b for the Name attribute in each respective partition A.sub.1, A.sub.2, B.sub.1, and B.sub.2, one dictionary being defined for each partition. Each occurrence of an actual value of the Name attribute in a partition has an entry in its respective dictionary and is associated with a value ID. Note that the value IDs among the dictionaries are not related. For example, value ID 2 in dictionary A.sub.1 is associated with the actual value “Hugo”, while the same value ID in dictionary A.sub.2 is associated with the actual value “Herbert”. FIG. 5 shows the value IDs associated with the actual values of the Name attribute for each partition A.sub.1, A.sub.2, B.sub.1, and B.sub.2, obtained from the dictionaries of FIG. 5A. Though the value IDs in a given dictionary can be arbitrarily selected (so long as they uniquely identify an actual value and the actual value is uniquely identified by the value ID), embodiments of the present invention may adopt the convention that the value IDs be the ordinal positions in the dictionary of their corresponding actual values. Accordingly, the value IDs are consecutive, beginning with “1”.

(36) Consider now the join operation discussed above in connection with FIG. 4, namely a join operation of the split data tables A and B of FIG. 5 predicated on the Name attribute in data table A being equal to the Name attribute in data table B (the join condition). The execution plan shown in FIG. 3 for conducting a join operation in accordance with the present invention will now be explained in the context of the specific example illustrated in FIGS. 5 and 5A. For the discussion that follows, references to “actual value” will be understood to refer to actual values of the Name attribute (the specified attribute) in data table A or in data table B.

(37) Step 302—Generate and Send Reduction Data

(38) Referring to FIG. 6, each partition A.sub.1, A.sub.2 generates and sends respective reduction data 102a, 102b to partitions B.sub.1, B.sub.2. The reduction data 102a, 102b can be obtained from the local dictionary of the respective partition. For example, the reduction data 102a from partition A.sub.1 is communicated to each partition B.sub.1, B.sub.2. Likewise, the reduction data 102a from partition A.sub.2 is communicated to each partition B.sub.1, B.sub.2. In a particular embodiment, an index table 602 can be created in each partition A.sub.1, A.sub.2. Each index table 602 comprises the Doc ID attribute and the Name attribute obtained from the respective partition, and a value ID attribute obtained from the partition's local dictionary. A tuple list 604 comprising Doc IDs and initially populated with corresponding value IDs can be generated and stored in the respective partition. The significance of table 602 and list 604 will become clear later on.

(39) Step 304—Associate Global IDs

(40) Each partition B.sub.1, B.sub.2 associates a global ID for each actual value of the Name attribute in the partition that also occurs in at least one of the partitions A.sub.1, A.sub.2. Referring to FIGS. 3A, 7, and 7A-7D, consider first the processing in partition B.sub.1. Processing in partition B.sub.2 will be discussed in connection with FIGS. 8 and 8A-8D.

(41) In a step 322, various tables can be created and initialized in partition B.sub.1. In an embodiment, these tables are local to partition B.sub.1. FIG. 7 shows the reduction data 102a, 102b received in partition B.sub.1 from partitions A.sub.1, A.sub.2. In embodiments, the reduction data 102a, 102b may be incorporated into a translation matrix 702 local to partition B.sub.1. The value IDs in the reduction data 102a, 102b may be assembled into a VID-A column 712. A VID-B column 714 is initialized to “−1”; this column will be filled in with value IDs from the local dictionary of partition B.sub.1.

(42) The translation matrix 702 includes a global ID column 716 which is initialized with its corresponding ordinal position in the translation matrix. In general, any set of numbers can be used to initialize the global ID column 716 so long as each row has a unique number and the same set of numbers is used by each of the partitions B.sub.1, B.sub.2. Initially, the value IDs 1, 2, 3, and 4 from partition A.sub.1 are initially mapped to global IDs 1, 2, 3, and 4 (namely rows 1-4 of the translation matrix 702); and the value IDs 1, 2, 3, 4, and 5 from partition A.sub.2 are initially mapped to global IDs 5, 6, 7, 8, and 9 (rows 5-9 of the translation matrix).

(43) Additional tables are created and initialized. An A2B translation table is created for each partition A.sub.x, and initialized to “−1”. For example, partition A.sub.1 has a corresponding A2B translation table 704a and partition A.sub.2 has a corresponding A2B translation table 704b. The translation tables 704a, 704b serve to translate the value IDs from partitions A.sub.1 and A.sub.2 to corresponding value IDs in partition B.sub.1. Since the respective value IDs for A.sub.1, A.sub.2 are consecutive by convention, the value IDs correspond directly with the row indices in tables 704a, 704b. For example, the value ID “3” for partition A.sub.1 can be used to index into translation table 704a to obtain the translated value ID in partition B.sub.1. This use of the indices is illustrated in FIG. 7.

(44) A B2A translation table is created and initialized with “−2”. The partition B.sub.1 has a corresponding B2A translation table 706 which includes a corresponding column for each partition A.sub.x. The B2A translation table 706 serves to provide a translation of the value IDs in the local dictionary of partition B.sub.1 to corresponding value IDs in partitions A.sub.1, A.sub.2. Since the value IDs are consecutive, the row in table 706 for a given value ID can be accessed using the value ID itself as an index into the table.

(45) Continuing with FIG. 3A and referring now to FIGS. 7A-7C, the translation tables 704a, 704b, 706 can be filled in the following manner: Consider first FIG. 7A and partition A.sub.1. In a step 324a, the value IDs from the corresponding reduction data 102a are sent to and received by the server that hosts partition A.sub.1. For example, FIG. 7A shows the list of value IDs {1, 2, 3, 4} being sent to the server. The actual values corresponding to the list of value IDs are obtained from the local dictionary of partition A.sub.1 (see FIG. 5A) and are sent by and received from the server in a step 324b. For example, the list of actual values received is {Adam, Hugo, Markus, Werner}. In a step 324c, if an actual value received from partition A.sub.1 matches an entry in the local dictionary for partition B.sub.1, then the value ID from B.sub.1's local dictionary is copied to the corresponding entry in the A2B translation table 704a. As explained above, the A.sub.1 value IDs can be used to index into the table 704a. Conversely, in a step 324d, partition A.sub.1's value ID for that matching actual value is copied into the B2A translation table 706 indexed by the value ID from B.sub.1's local dictionary. FIG. 7A is annotated with steps 324a-324d to illustrate this process.

(46) Steps 324a-324d are performed 324 by each partition A.sub.x. For example, FIG. 7B shows steps 324a-324d performed for partition A.sub.2. Since each partition A.sub.x operates independently of each other, they can perform these steps at the same time. FIG. 7C shows the result after each of the partitions have completed steps 324a-324d.

(47) It can be appreciated from the foregoing that the “−1” values in the A2B translation tables 704a, 704b indicate that there is no translation of value IDs from the respective A.sub.1, A.sub.2, partitions to the B.sub.1 partition. Consider translation table 704a for partition A.sub.1, for example. The second entry corresponds to a value ID 2 in partition A.sub.1, which in turn corresponds to the value “Hugo”. Since the local dictionary for partition B.sub.1 does not have an entry for “Hugo”, the entry in table 704a remains unchanged, namely it is “−1”.

(48) It can be further appreciated that the “−2” values in the B2A translation table 706 indicates that the partition B.sub.1 has not yet received the corresponding value from the respective the A.sub.x partition. For example, consider the first entry in the A.sub.1 ID column of the table 706. This entry corresponds to the first entry in the local dictionary for partition B.sub.1, which contains the value “Achim”. Since the local dictionary for partition A.sub.1 (see FIG. 5A) does not include the value “Achim”, partition B.sub.1 did not receive such value from partition A.sub.1, and so the entry in table 706 remains unchanged, namely it is “−2”. Previously communicated values can be locally cached in the B2A translation table 706 for subsequent join operations, thus avoiding redundant communications. Thus, for subsequent join operations involving data table A, only those entries that have “−2” may need to be filled with actual values.

(49) Continuing with FIGS. 3A and 7D, in a step 326 the A2B translation tables 704a, 704b are mapped into their respective entries in the VID-B column 714 of the translation matrix 702. FIG. 7D shows the result of such mapping, the values are copied from the translation tables 704a, 704b into column 714. In this way, the global IDs in column 716 become associated with actual values via the value IDs in columns 712 and 714. For example, the value ID of 1 from partition A.sub.1 is associated with “Adam” and so the global ID “1” is associated with “Adam.” Similarly, global ID “5” is associated with “Eva.”

(50) For entries in the tables 704a, 704b which have no translation to corresponding value IDs in partition B.sub.1, the corresponding global IDs in column 716 are changed to “−1” to indicate this fact. Thus, for example, value IDs 2, 3, and 4 in partition A.sub.1 have no corresponding value IDs in partition B.sub.1, and so the global IDs in rows 2, 3, and 4 of the translation matrix 702 are set to “−1”. Similarly, value IDs 2, 3, and 4 in partition A.sub.2 have no corresponding value IDs in partition B.sub.1, and so the global IDs in rows 6, 7, and 8 of the translation matrix 702 are set to “−1”.

(51) In a step 328, any duplicate VID-B values in column 714 would be handled in the following manner: For each VID-B value in column 714 that occurs more than once, copy the global ID (column 716) associated with the first occurrence of that VID-B value into the global ID column of each duplicated VID-B value. However, the translation matrix 702 shown in FIG. 7D for partition B.sub.1 does not have any duplicated VID-B values. For example, the values 2, 3, and 4 each occurs only once in column 714, and so their corresponding global IDs remain unchanged, namely 1, 5, 9 respectively. This is not the case in partition B.sub.2, and the processing of step 328 is illustrated below for partition B.sub.2.

(52) Refer now to FIGS. 3A, 8, and 8A-8D for a brief discussion of the processing (step 304) of partition B.sub.2 in accordance with embodiments of the present invention. Thus, in a step 322, various tables local to partition B.sub.2 can be created and initialized in the partition. FIG. 8 shows the reduction data 102a, 102b received in partition B.sub.2 from partitions A.sub.1, A.sub.2. In embodiments, the reduction data 102a, 102b may be incorporated into a translation matrix 702 that is local to partition B.sub.2. The VID-A column 712, VID-B column 714, and global ID column 716 are initialized in the same manner as explained in FIG. 7 for partition B.sub.1. Likewise, the additional tables 704a, 704b, and 706 are initialized in the same manner as described in FIG. 7 for partition B.sub.1. The B2A translation table 706 for partition B.sub.1 in FIG. 7 contains four entries because B.sub.1's local dictionary has four items. However, since B.sub.2's local dictionary has five items, the B2A translation table 706 in FIG. 8 has five entries.

(53) Referring now to FIG. 8A, processing of steps 324a-324d between partition B.sub.2 and A.sub.1 is illustrated. The list of value IDs for partition A.sub.1 is sent to the server hosting the A.sub.1 partition (324a). The list of values corresponding to the value IDs is received from the server (324b). In step 324c, the received list of values {Adam, Hugo, Markus, Werner} is used to map the A.sub.1 value IDs to the B.sub.2 value IDs, thus filling in the A2B translation table 704a for A.sub.1. In step 324d, a similar mapping is made to map the B.sub.2 value IDs to the A.sub.1 value IDs, thus filling in the A.sub.1 ID column in the translation table 706 for partition B.sub.2.

(54) Referring to FIG. 8B, the processing of steps 324a-324d between partition B.sub.2 and A.sub.2 is illustrated. FIG. 8C show shows the result upon completion of loop 324. In step 326, the A2B translation tables 704a, 704b are mapped into their respective entries in the VID-B column 714 of the translation matrix 702. FIG. 8D shows the result of such mapping, the values are copied from the translation tables 704a, 704b into column 714.

(55) In step 328, duplicate VID-B values in column 714 of the translation matrix 702 for partition B.sub.2 are handled in the following manner: For each VID-B value in column 714 that occurs more than once, copy the global ID (column 716) associated with the first occurrence of that VID-B value into the global ID column of each duplicated VID-B value. Referring to FIG. 8E, The VID-B value of “3” appears twice. The first occurrence is associated with the global ID “2”. Accordingly, the global ID value “2” is copied into the global ID column of each duplicate occurrence of “3” in the VID-B column 714.

(56) This concludes the discussion of step 304 (FIG. 3) for partitions B.sub.1 and B.sub.2. FIG. 9 shows the translation matrices 702 that are stored in each partition B.sub.1, B.sub.2 at this point. A few observations are worth mentioning. Processing in accordance with embodiments of the present invention in partitions B.sub.1, B.sub.2 occurs independently of each other; there is no synchronization of their data or other communications. The resulting translation matrix 702 in a given partition contains global IDs that identify actual values (of the specified attribute in the join operation) in the given partition which also occur in at least one of the partitions A.sub.1, A.sub.2. Consider for example the value “Hugo” in FIG. 9. “Hugo” appears in partition B.sub.1 and in partition A.sub.1, so “Hugo” is assigned a global ID (in this case 3). On the other hand “Achim” in partition B.sub.1 does not appear in either partition A.sub.1 or A.sub.2. Accordingly, none of the translation tables 702 have a translation for “Achim”. The global IDs are unique among the translation tables 702 for a given actual value. For example, “Hugo” appears in partitions B.sub.1 and B.sub.2. The translation matrices 702 in each partition B.sub.1, B.sub.2 map “Hugo” to the same global ID, namely “2”.

(57) The discussion will now continue with an explanation of the remaining steps 306-312 of FIG. 3.

(58) Step 306—Send Translated Value IDs

(59) Each partition B.sub.1, B.sub.2 translates the value IDs that comprise the reduction data 102a, 102b from respective partitions A.sub.1, A.sub.2, producing a set of translated value IDs. Referring to FIG. 10A, the processing of this step in partition B.sub.1 is shown. In an embodiment, the translation matrix 702 for partition B.sub.1 can provide the contents of a translated value ID table 104a for partition A.sub.1 and a translated value ID table 104b for partition A.sub.2. As can be seen, the translated value ID table 104a comprises rows 1-4 from columns 712 and 716 of the translation matrix 702. Likewise, the translated value ID table 104b comprises rows 5-9 from columns 712 and 716 of the translation matrix 702. The tables 104a, 104b provide a translation of value IDs from partitions A.sub.1, A.sub.2 to the global IDs. In accordance with step 306, the tables 104a, 104b are communicated to and received by respective partitions A.sub.1, A.sub.2. The same process occurs in partition B.sub.2, and is illustrated in FIG. 10B. Accordingly, partition A.sub.1 will receive a translation value ID table 104a from partition B.sub.1 and from partition B.sub.2. Similarly, partition A.sub.2 will receive a translation value ID table 104b from partition B.sub.1 and from partition B.sub.2.

(60) Step 308—Generate Global B Lists

(61) Each partition B.sub.1, B.sub.2 generates a globalized list that identifies one or more rows stored in the partition. Each row that is identified in the globalized list contains an actual value of the specified attribute which also occurs in one of the partitions A.sub.1, A.sub.2. Referring to FIG. 11A, processing of this step in partition B.sub.1 is shown. In an embodiment, an index table 1102 can be created for partition B.sub.1, comprising the Doc ID attribute and the Name attribute obtained from the partition, and a value ID attribute obtained from B.sub.1's local dictionary.

(62) In an embodiment, for each row in the index table 1102: (1) if the value ID appears in column 714 of the translation matrix 702, then (2) copy the corresponding global ID from column 716 into a globalized list 106a for partition B.sub.1, and (3) copy the corresponding Doc ID from the index table for all instances of the value ID. For example, value ID 2 appears in column 714 of the translation matrix 702. Two instances of the value ID 2 appear in the index table 1102, and the corresponding Doc IDs are 2 and 4. Accordingly, 2 and 4 are recorded in the globalized list 106a. The global ID corresponding to value ID 2 is 1, and so 1 is recorded in the globalized list 106a next to Doc IDs 2 and 4. This is repeated for value IDs 3 and 4, which also appear in column 714 of the translation matrix 702. The completed globalized list 106a can then be communicated to a recipient server.

(63) Referring to FIG. 11B, the foregoing is repeated for partition B.sub.2: An index table 1102 is created from partition B.sub.2. A globalized list 106b is then generated based on the index table and on the translation matrix 702 developed in partition B.sub.2. The globalized list 106b is then communicated to the recipient server.

(64) Step 310—Generate Global A Lists

(65) Referring now to FIGS. 12A and 12B, each partition A.sub.1, A.sub.2 can generate a globalized list using the tupelist list and the translated value ID tables 104a received from the partitions B.sub.1, B.sub.2. Consider FIG. 12A for a discussion of processing in partition A.sub.1. It is noted that in accordance with the present invention, the value IDs in each translated value ID table 104a received from the partitions B.sub.1, B.sub.2 will map to the same global ID or to “−1”, meaning that no translation was made in the respective B partition. For example, value ID 1 maps to global ID 1 in the table 104a received from partition B.sub.1. Value ID 1 also maps to global ID 1 in the table 104a received from partition B.sub.2. However, value IDs 2, 3, and 4 in the table 104a received from partition B.sub.1 were not translated, so these value IDs map to “−1”. On the other hand, value IDs 2 and 3 in the table 104a received from partition B.sub.2 were (coincidentally) translated to global IDs 2 and 3, respectively. It is noted that the mapped pairs having global ID “−1” can be regarded as having non-matching values in the join operation (e.g. partition A.sub.1 value ID 4/Doc ID 4). Those rows would be eliminated in the case of an inner join.

(66) In an embodiment, using the tuple list 604 obtained (FIG. 6) for partition A.sub.1, then for each value ID in the tuple list: (1) if the value ID appears in one of the translated value ID tables 104a, then (2) copy the corresponding global ID from that table into a globalized list 108a for partition A.sub.1, and (3) copy the corresponding Doc ID from the tuple list for all instances of the value ID. The globalized list 108a is then communicated to the recipient server. This procedure is repeated in partition A.sub.2, with reference to FIG. 12B using the tuple list 604 generated for partition A.sub.2 and the translated value ID tables 104b received from partitions B.sub.1 and B.sub.2 to generate a globalized list 108b. The resulting globalized list 108b is then communicated to the recipient server.

(67) Step 312—Compile Combined Lists

(68) The recipient server will receive the globalized lists 106a, 106b from respective partitions B.sub.1, B.sub.2. A compiled B list 112 can be created by concatenating the two globalized lists 106a, 106b. This is illustrated in FIG. 13. The compiled B list 112 comprises pairs of Doc IDs and global IDs. The Doc ID identifies those rows among partitions B.sub.1 and B.sub.2 for which the actual values of the specified attribute (now identified by the global IDs) also occur in at least one of the partitions A.sub.1, A.sub.2. The figure also shows a compiled A list 114 for the A partitions, created by concatenating globalized lists 108a, 108b. The compiled A list 114 comprises pairs of Doc IDs and global IDs. The Doc ID identifies those rows among partitions A.sub.1 and A.sub.2 for which the actual values of the specified attribute (now identified by the global IDs) also occur in at least one of the partitions B.sub.1, B.sub.2.

(69) Step 314—Join the Compiled Lists

(70) Still referring to FIG. 13, a join operation is performed between the compiled A list 114 and the compiled B list 112, where the join condition is based on the global ID attribute. In other words, the join operation is predicated on the global ID in the compiled A list 114 being equal to the global ID in compiled B list 112. The join result 122 is shown in the figure.

(71) A comparison of the join result 122 in FIG. 13 with the join result shown in FIG. 4A will reveal that the two results are identical. The result obtained in FIG. 4A was obtained by joining data tables A and B, which were not split. By comparison, the join result 122 in FIG. 13 was made on partitioned data tables A and B, while at the same time allowing for each database partition A.sub.1, A.sub.2, B.sub.1, B.sub.2 to employ a local dictionary on the specified attribute.

(72) The above description illustrates various embodiments of the present invention along with examples of how aspects of the present invention may be implemented. The above examples and embodiments should not be deemed to be the only embodiments, and are presented to illustrate the flexibility and advantages of the present invention as defined by the following claims. Based on the above disclosure and the following claims, other arrangements, embodiments, implementations and equivalents will be evident to those skilled in the art and may be employed without departing from the spirit and scope of the invention as defined by the claims.