Leapfrog tree-join
AssigneeLogicBlox, Inc.
InventorTodd L. Veldhuizen
Life of this patent
Estimating the term…
Abstract
A method for joining records from database tables is proposed. Join attributes are ordered into a sequence S0, and a scope C is initialized to empty. Tables including a join attribute A that is first in S0 are identified. A new sequence S′ omits A from S0. Iteration through each identified table proceeds in join attribute A order. The iteration utilizes a tree index structure for each identified table where the index key includes all join attributes in the identified table in S0 order. For each matched value v of the join attribute located during the iterating, a new scope Cv is created by appending “A=v” to the scope C. If S′ is empty, a tuple corresponding to the scope Cv is output. Otherwise, S0 is set to S′ and for each scope Cv, C is set to Cv and the steps beginning with the identifying step are recursively invoked.
Claims22
A method to join records from a set of at least three tables in a database according to a set of join conditions on a set S of join attributes, the method comprising:
- arranging the join attributes S into an ordered sequence S0;
- initializing a scope C to empty;
- identifying tables in the set of tables that include a join attribute A that is first in the ordered sequence S0;
- creating a new sequence S′ of join attributes that omits the join attribute A from S0;
- iterating through each of the identified tables in join attribute A order, the iterating based on a tree index structure for each of the identified tables where the index key includes all join attributes in the identified table in S0 order;
- for each matched value v of the join attribute located during the iterating, creating a new scope Cv by appending “A=v” to the scope C;
- determining whether S′ is empty;
- based on determining that S′ is empty, outputting a tuple corresponding to the scope Cv for each v;
- and
- based on determining that S′ is not empty, setting S0 to S′ and for each scope Cv, setting C to Cv and recursively invoking the identifying, creating, iterating, appending, determining, outputting and recursively invoking.
A system for joining records from a set of at least three tables in a database according to a set of join conditions on a set S of join attributes, the system comprising:
- a memory having computer readable computer instructions;
- and
- a processor for executing the computer readable instructions to perform a method comprising:
- arranging the join attributes S into an ordered sequence S0;
- initializing a scope C to empty;
- identifying tables in the set of tables that include a join attribute A that is first in the ordered sequence S0;
- creating a new sequence S′ of join attributes that omits the join attribute A from S0;
- iterating through each of the identified tables in join attribute A order, the iterating based on a tree index structure for each of the identified tables where the index key includes all join attributes in the identified table in S0 order;
- for each matched value v of the join attribute located during the iterating, creating a new scope Cv by appending “A=v” to the scope C;
- determining whether S′ is empty;
- based on determining that S′ is empty, outputting a tuple corresponding to the scope Cv for each v;
- and
- based on determining that S′ is not empty, setting S0 to S′ and for each scope Cv, setting C to Cv and recursively invoking the identifying, creating, iterating, appending, determining, outputting and recursively invoking.
A computer program product for system for joining records from a set of at least three tables in a database according to a set of join conditions on a set S of join attributes, 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:
- arranging the join attributes S into an ordered sequence S0;
- initializing a scope C to empty;
- identifying tables in the set of tables that include a join attribute A that is first in the ordered sequence S0;
- creating a new sequence S′ of join attributes that omits the join attribute A from S0;
- iterating through each of the identified tables in join attribute A order, the iterating based on a tree index structure for each of the identified tables where the index key includes all join attributes in the identified table in S0 order;
- for each matched value v of the join attribute located during the iterating, creating a new scope Cv by appending “A=v” to the scope C;
- determining whether S′ is empty;
- based on determining that S′ is empty, outputting a tuple corresponding to the scope Cv for each v;
- and
- based on determining that S′ is not empty, setting S0 to S′ and for each scope Cv, setting C to Cv and recursively invoking the identifying, creating, iterating, appending, determining, outputting and recursively invoking.
Dependencies are inferred from the claim text.