Leapfrog tree-join
View Patent ↗A method for joining records from database tables is proposed. Join attributes are ordered into a sequence S 0 , and a scope C is initialized to empty. Tables including a join attribute A that is first in S 0 are identified. A new sequence S′ omits A from S 0 . 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 S 0 order. For each matched value v of the join attribute located during the iterating, a new scope C v is created by appending “A=v” to the scope C. If S′ is empty, a tuple corresponding to the scope C v is output. Otherwise, S 0 is set to S′ and for each scope C v , C is set to C v and the steps beginning with the identifying step are recursively invoked.
1. 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 S 0 ;
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 S 0 ;
creating a new sequence S′ of join attributes that omits the join attribute A from S 0 ;
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 S 0 order;
for each matched value v of the join attribute located during the iterating, creating a new scope C v 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 C v for each v; and
based on determining that S′ is not empty, setting S 0 to S′ and for each scope C v , setting C to C v and recursively invoking the identifying, creating, iterating, appending, determining, outputting and recursively invoking.
2. The method of claim 1 , wherein the ordered sequence S 0 is a non-prefix-coherent ordered sequence.
3. The method of claim 1 , wherein rows in the database tables that meet a filtering condition are skipped by the iterating.
4. The method of claim 1 , further comprising building a tree index structure
5. The method of claim 1 , wherein the tree index structure is a B-tree structure.
6. The method of claim 1 , wherein the tree index structure is a trie structure.
7. The method of claim 1 , wherein a non-join attribute value from a database table is output along with the tuple.
8. The method of claim 1 , wherein a query optimizer is utilized to determine the ordered sequence.
9. 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 S 0 ;
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 S 0 ;
creating a new sequence S′ of join attributes that omits the join attribute A from S 0 ;
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 S 0 order;
for each matched value v of the join attribute located during the iterating, creating a new scope C v 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 C v for each v; and
based on determining that S′ is not empty, setting S 0 to S′ and for each scope C v , setting C to C v and recursively invoking the identifying, creating, iterating, appending, determining, outputting and recursively invoking.
10. The system of claim 9 , wherein the ordered sequence S 0 is a non-prefix-coherent ordered sequence.
11. The system of claim 9 , wherein rows in the database tables that meet a filtering condition are skipped by the iterating.
12. The system of claim 9 , wherein the method further comprises building a tree index structure
13. The system of claim 9 , wherein the tree index structure is a B-tree structure.
14. The system of claim 9 , wherein the tree index structure is a trie structure.
15. The system of claim 9 , wherein a non-join attribute value from a database table is output along with the tuple.
16. The system of claim 9 , wherein a query optimizer is utilized to determine the ordered sequence.
17. 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 S 0 ;
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 S 0 ;
creating a new sequence S′ of join attributes that omits the join attribute A from S 0 ;
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 S 0 order;
for each matched value v of the join attribute located during the iterating, creating a new scope C v 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 C v for each v; and
based on determining that S′ is not empty, setting S 0 to S′ and for each scope C v , setting C to C v and recursively invoking the identifying, creating, iterating, appending, determining, outputting and recursively invoking.
18. The computer program product of claim 17 , wherein the ordered sequence S 0 is a non-prefix-coherent ordered sequence.
19. The computer program product of claim 17 , wherein rows in the database tables that meet a filtering condition are skipped by the iterating.
20. The computer program product of claim 17 , wherein the tree index structure is a trie structure.
21. The computer program product of claim 17 , wherein a non-join attribute value from a database table is output along with the tuple.
22. The computer program product of claim 17 , wherein a query optimizer is utilized to determine the ordered sequence.