Method for calculating distributed joins in main memory with minimal communicaton overhead

A system for executing a distributed equi-join query for a set of documents, wherein the query includes a precondition part and a join condition part, the system comprising one or more processors configured to provide:

• a first logical server having a processor under command of program code, the program code including code for:
• generating a first tuple list of documents matching the precondition part of the query, the first tuple list including an index identifier for each row of the first tuple list, each row of the first tuple list including a first set of value identifiers that represent values for one or more attributes represented in the columns of the first document;
• extracting, from the first tuple list, a first subset of value identifiers by removing duplicate occurrences of value identifiers from the first set of value identifiers;
• sending the first subset of value identifiers with a join condition attribute to a second index server;
• and
• the second index server having a processor under command of program code including code for:
• mapping the first subset of value identifiers to a second subset of value identifiers of second attributes represented in columns of a second document of the set of documents based on a dictionary of value identifiers and their associated values in the first server, the second set of value identifiers represented with corresponding index identifiers in a second tuple list;
• and
• performing a lookup in the second tuple list to obtain results that generate a third tuple list including the mapped portion of the second set of value identifiers with corresponding index identifiers in the second tuple list.

A first server configured to perform operations comprising one or more processors configured for:

• receiving at the first server data characterizing a query involving an equi-join operation, the data received from a second server;
• generating a first list of unique value identifiers for records matching the query, the first list of unique value identifiers including value identifiers of an attribute of a join condition specified in the query, the value identifiers including an index identifier for each row of the first list of unique value identifiers, each row of the first tuple list including a first set of value identifiers that represent values for one or more attributes represented in the columns of the first document;
• transmitting the first list of unique value identifiers to a third server;
• receiving at the first server data characterizing a second list of unique value identifiers being a subset of the first list of unique value identifiers that correspond to only those value identifiers from the first list that correspond to attributes that are in records of the third server;
• generating a first list of records that both match the query and include a value identifier from the second list of unique value identifiers;
• and
• transmitting the first list of records to the second server, the second server to join the first list of records with a second list of records from the third server having an attribute corresponding to a value identifier from the second list of unique value identifiers.