Leapfrog tree-join

An apparatus for joining records from a plurality of database tables, the apparatus comprising:

• at least one memory having computer readable computer instructions;
• and
• a processor for executing the computer readable instructions to perform a method comprising:
• receiving a set of at least three database tables stored in at least one table memory of the at least one memory, and a set of join conditions on a set S of join attributes;
• initializing, in the at least one scope memory of the at least one memory, a scope C to empty;
• joining records according to each join attribute A in an ordered sequence S.sub.0, which is an ordered sequence of the join attributes S, by:
• identifying tables in the set of tables that include the join attribute A;
• dropping the join attribute A from S.sub.0;
• iterating through each of the identified tables in join attribute A order, the iterating based on a tree index structure held in at least one index memory for each of the identified tables where the index key includes all join attributes in the identified table in S.sub.0 order, and wherein the iterating includes seeking subsequent rows in each of the identified tables using the tree index structure, the at least one index memory having faster access times than the at least one table memory;
• for each matched value v of the join attribute located during the iterating, creating, in the at least one scope memory, a new scope C.sub.v by appending “A=v” to the scope C;
• and
• for each scope C.sub.v, setting C to C.sub.v and recursively invoking the identifying, creating, iterating, appending, outputting and recursively invoking;
• and in response to the records being joined according to each attribute in the ordered sequence S.sub.0, outputting a tuple corresponding to the scope C.sub.v for each v.

A non-transitory computer readable storage medium for system for joining records from plurality of database tables, the computer program product comprising:

• a computer readable storage medium having computer-readable program code embodied thereon, which when executed by a computer processor, causes the computer processor to implement a method, the method comprising:
• receiving a set of at least three database tables stored in at least one first memory, and a set of join conditions on a set S of join attributes;
• initializing, in at least one second memory, a scope C to empty;
• joining records according to each join attribute in ordered sequence S.sub.0, which is an ordered sequence of the join attributes S, by:
• identifying tables in the set of tables that include a join attribute A that is first in the ordered sequence S.sub.0;
• dropping the join attribute A from S.sub.0;
• iterating through each of the identified tables in join attribute A order, the iterating based on a tree index structure held in at least one third memory for each of the identified tables where the index key includes all join attributes in the identified table in S.sub.0 order, and wherein the iterating includes seeking subsequent rows in each of the identified tables using the tree index structure, the at least one third memory having faster access times than the at least one first memory;
• for each matched value v of the join attribute located during the iterating, creating, in the at least one second memory, a new scope C.sub.v by appending “A=v” to the scope C;
• and
• for each scope C.sub.v, setting C to C.sub.v and recursively invoking the identifying, creating, iterating, appending, outputting and recursively invoking;
• and in response to the records being joined according to each attribute in the ordered sequence S.sub.0, outputting a tuple corresponding to the scope C.sub.v for each v.