Virtual pair algorithm for outer join resolution

A method for executing an outer join in a relational database distributed across multiple hosts to process a query, the method comprising:

• creating, by at least one computing device, tuple lists for relations in the relational database and for joins referencing each relation;
• performing, by the at least one computing device, a sequence of semijoin reduction steps on the joins;
• and
• adding, by the at least one computing device, virtual connector pairs to one or more reduced tuple lists to connect the one or more reduced tuple lists to at least one other tuple list to enable the query to be processed.

A computer-implemented method comprising:

• receiving, by at least one computing device, a query for a relational database, the query having a set of requested attributes, and the relational database being distributed across multiple hosts;
• creating, by the at least one computing device, tuple lists for relations in the relational database associated with the set of requested attributes and for joins referencing each relation;
• performing, by the at least one computing device, a sequence of semijoin reduction steps on the joins;
• and
• adding, by the at least one computing device, virtual connector pairs to one or more reduced tuple lists to connect the one or more reduced tuple lists to at least one other tuple list to enable the query to be processed.

A computer program product embodied on computer-readable storage media, the computer program product configured to cause data processing apparatus to perform operations comprising:

• receiving a query for a relational database, the query having a set of requested attributes, and the relational database being distributed across multiple hosts;
• creating tuple lists for relations in the relational database associated with the set of requested attributes and for joins referencing each relation;
• performing a sequence of semijoin reduction steps on the joins;
• and
• adding virtual connector pairs to one or more reduced tuple lists to connect the one or more reduced tuple lists to at least one other tuple list to enable the query to be processed.

A computer-implemented method for executing semijoin reductions on outer join operations comprising:

• creating, by at least one computing device, a plurality of tuple lists;
• performing, by the at least one computing device, a sequence of semijoin reduction steps, each semijoin reduction step either switching one tuple list or reducing all tuple lists at one relation;
• inserting, by the at least one computing device, virtual connector pairs into one or more reduced tuple lists from the plurality of tuple lists to connect the one or more reduced tuple lists to at least one other tuple list;
• centralizing, by the at least one computing device, the plurality of tuple lists at a computing-based central host;
• assembling, at the central host, join results having negative row IDs therein;
• and
• retrieving, by the at least one computing device, a query result from the join results by projecting to attributes requested in the query.

A system comprising:

• one or more processor-based hosts hosting one or more relational databases distributed across the one or more hosts;
• one or more computing devices to process a query, the one or more computing devices configured, when executing computer instructions, to:
• create tuple lists for relations in the relational databases and for joins referencing each relation;
• perform by the at least one computing device a sequence of semijoin reduction steps on the joins;
• and
• add virtual connector pairs to one or more reduced tuple lists to connect the one or more reduced tuple lists to at least one other tuple list to enable the query to be processed.