Partitioned join with dense inner table representation

Abstract

To perform a join operation on database objects, data structures contained in a first database object are distributed across database partitions in accordance with a partitioning scheme. Data structures of the first database object are associated with respective indices computed complementarily to the partitioning scheme. Other indices are computed from the respective data structures of a second database object. The join operation is performed at each of the database partitions on the data structures in the respective first and second database objects having the indices and the other indices in common.

What is claimed is: 
     
       1. A method of performing a join operation on a plurality of database objects comprising:
 distributing data structures contained in a first database object across a plurality of database partitions in accordance with a partitioning scheme, the database partitions being stored in respective data storage units of a plurality of processing nodes, each of the processing nodes comprising a processor and a data storage unit, the processing nodes being communicatively coupled one to another, wherein each of the plurality of database partitions uniquely corresponds to a partition processing module configured to perform one or more operations on the corresponding database partition in parallel with one or more other partition processing modules to complete a common task on the first database object; 
 associating the data structures of the first database object with indices computed complementary to the partitioning scheme; 
 computing other indices from data structures contained in a second database object; and 
 performing the join operation at each of the database partitions on the data structures in the respective first and second database objects having the indices and the other indices in common. 
 
     
     
       2. The method of  claim 1 , further comprising:
 performing, as the partitioning scheme, a hash function on key values identifying data in the respective first and second database objects on which the join operation is predicated; and 
 distributing the first and second database objects across the database partitions in accordance with the hashed key values. 
 
     
     
       3. The method of  claim 2 , further comprising:
 determining whether data values in the data structure of the first database object meet a density criterion. 
 
     
     
       4. The method of  claim 3 , further comprising:
 constructing a memory array that associates each of the data structures of the first database object with the respective indices in response to the data values meeting the density criterion. 
 
     
     
       5. The method of  claim 3 , further comprising:
 constructing a hash table that associates the hashed key values with the data structures in response to the data values failing to meet the density criterion. 
 
     
     
       6. The method of  claim 1 , further comprising:
 distributing the data structures in the first and second database objects in accordance with a modulus operation K MOD N, where K is the key value and N is the number of partitions over which the data structures are distributed; and 
 computing the index and the other index in accordance with an integer division operation K/N. 
 
     
     
       7. The method of  claim 1 , further comprising:
 distributing the data structures in the first and second database objects in accordance with a modulus operation (K MOD P) MOD N, where K is the key value, N is the number of partitions over which the data structures are distributed and P is a predetermined prime number; and 
 computing the index and the other index in accordance with an integer division operation ((K/P)*S)+((K MOD P)/N), where S is a scale factor. 
 
     
     
       8. The method of  claim 7 , wherein the scale factor, S, is determined at each partition from one of:
     S≥ 1+(( P− 1)/ N )); and 
     S≥ 1+( P/N ); 
 wherein P is the prime number, and N is the quantity of partitions.