Leapfrog tree-join

Abstract

An apparatus for joining records from a plurality of database tables, the apparatus including: a processor; and a memory storing computer readable instructions that, when executed by the processor, control the processor to: select, as a current join attribute, a first join attribute from an ordered sequence of join attributes; and join records according to each join attribute in the ordered sequence by: identifying tables in the plurality of tables that include the current join attribute; iterating, based on a tree index structure, through each of the identified tables in current join attribute order; for each matched value located during the iterating, appending the matched value to a join scope; and in response to the ordered sequence containing a next join attribute, for each matched value in the join scope, setting the next join attribute as the current join attribute and recursively invoking the identifying, iterating, and appending.

What is claimed: 
     
         1 . A computer implemented method for joining records from a plurality of database tables, the method comprising:
 selecting, as a current join attribute, a first join attribute from an ordered sequence of a plurality of join attributes;   identifying tables of the plurality of database tables that include the current join attribute;   iterating, based on a tree index structure for each of the identified tables, through each of the identified tables in current join attribute order;   for each matched value of the join attribute located during the iterating, appending the matched value to a join scope; and   in response to the ordered sequence containing a next join attribute, for each matched value in the join scope, selecting the next join attribute as the current join attribute for recursively invoking the identifying, iterating, and appending.   
     
     
         2 . The computer implemented method of  claim 1 , wherein the ordered sequence is a non-prefix-coherent ordered sequence. 
     
     
         3 . The computer implemented method of  claim 1 , wherein rows in the database tables that meet a filtering condition are skipped by the iterating. 
     
     
         4 . The computer implemented method of  claim 1 , further comprising building the tree index structure, the tree index structure having either a B-tree structure or a trie structure. 
     
     
         5 . The computer implemented method of  claim 1 , wherein an index key of the tree index structure includes all join attributes in the identified two or more tables in the ordered sequence order. 
     
     
         6 . The computer implemented method of  claim 1  further comprising, in response to the ordered sequence containing no next join attribute, outputting a tuple corresponding to the join scope. 
     
     
         7 . The computer implemented method of  claim 6 , wherein a non-join attribute value from a database table is output along with the tuple. 
     
     
         8 . The computer implemented method of  claim 1  further comprising determining the ordered sequence of the plurality of join attributes with a query optimizer. 
     
     
         9 . An apparatus for joining records from a plurality of database tables, the apparatus comprising:
 at least one processor; and   at least one memory having stored thereon computer readable instructions that, when executed by the at least one processor, control the processor to:
 select, as a current join attribute, a first join attribute from an ordered sequence of a plurality of join attributes; and 
 join records according to each join attribute in the ordered sequence of the plurality of join attributes by:
 identifying tables in the plurality of tables that include the current join attribute; 
 iterating, based on a tree index structure for each of the identified tables, through each of the identified tables in current join attribute order; 
 for each matched value of the join attribute located during the iterating, appending the matched value to a join scope; and 
 in response to the ordered sequence containing a next join attribute, for each matched value in the join scope, setting the next join attribute as the current join attribute and recursively invoking the identifying, iterating, and appending. 
 
   
     
     
         10 . The apparatus of  claim 9 , wherein the ordered sequence is a non-prefix-coherent ordered sequence. 
     
     
         11 . The apparatus of  claim 9 , wherein rows in the database tables that meet a filtering condition are skipped by the iterating. 
     
     
         12 . The apparatus of  claim 9 , wherein the method further comprises building a tree index structure, the tree index structure having a B-tree structure or a trie structure. 
     
     
         13 . The apparatus of  claim 9 , wherein an index key of the tree index structure includes all join attributes in the identified two or more tables in the ordered sequence order. 
     
     
         14 . The apparatus of  claim 9 , wherein the computer readable instructions, when executed by the at least one processor, further control the processor to, in response to the records being joined according to each attribute in the ordered sequence, outputting a tuple corresponding to the join scope. 
     
     
         15 . The apparatus of  claim 14 , wherein a non-join attribute value from a database table is output along with the tuple. 
     
     
         16 . The apparatus of  claim 9  further comprising a query optimizer configured to determine the ordered sequence of the plurality of join attributes. 
     
     
         17 . A non-transitory computer readable storage medium having stored thereon computer program code that, when executed by a computer processor, causes the computer processor to implement a method for joining records from a plurality of database tables, the method comprising:
 selecting, as a current join attribute, a first join attribute from an ordered sequence of a plurality of join attributes;   identifying tables of the plurality of database tables that include the current join attribute;   iterating, based on a tree index structure for each of the identified tables, through each of the identified tables in current join attribute order;   for each matched value of the join attribute located during the iterating, appending the matched value to a join scope; and   in response to the ordered sequence containing a next join attribute, for each matched value in the join scope, selecting the next join attribute as the current join attribute for recursively invoking the identifying, iterating, appending, determining, and recursively invoking.   
     
     
         18 . The computer program product of  claim 17 , wherein rows in the database tables that meet a filtering condition are skipped by the iterating. 
     
     
         19 . The computer program product of  claim 17 , wherein the method comprises, in response to the ordered sequence containing no next join attribute, outputting a tuple corresponding to the join scope. 
     
     
         20 . The computer program product of  claim 17 , wherein an index key of the tree index structure includes all join attributes in the identified two or more tables in the ordered sequence order.