Hash join

From Wikipedia, the free encyclopedia

The Hash join is an example of a join algorithm and is used in the implementation of a relational database management system.

The task of a join algorithm is to find, for each distinct value of the join attribute, the set of tuples in each relation which have that value.

The classic hash join algorithm for an inner join of two relations proceeds as follows: first prepare a hash table for the smaller relation, by applying a hash function to the join attribute of each row. Then scan the larger relation and find the relevant rows by looking in the hash table. The first phase is usually called the "build" phase, while the second is called the "probe" phase. Similarly, the join relation on which the hash table is built is called the "build" input, whereas the other input is called the "probe" input.

This algorithm is simple, but it requires that the smaller join relation fits into memory, which is typically not the case. A simple approach to handling this situation proceeds as follows:

1. For each tuple r in the build input R
   1. Add r to the in-memory hash table
   2. If the size of the hash table equals the maximum in-memory size:
      1. Scan the probe input S, and add matching join tuples to the output relation
      2. Reset the hash table
2. Do a final scan of the probe input S and add the resulting join tuples to the output relation

(This is essentially the same as the block nested loop join algorithm.) This algorithm scans S more times than necessary. A better approach is known as the "grace hash join", after the GRACE database machine for which it was first implemented.^[1] This algorithm avoids rescanning the entire S relation by first partitioning both R and S via a hash function, and writing these partitions out to disk. The algorithm then loads pairs of partitions into memory, builds a hash table for the smaller partitioned relation, and probes the other relation for matches with the current hash table. Because the partitions were formed by hashing on the join key, it must be the case that any join output tuples must belong to the same partition. It is possible that one or more of the partitions still does not fit into the available memory, in which case the algorithm is recursively applied: an additional orthogonal hash function is chosen to hash the large partition into sub-partitions, which are then processed as before. Since this is expensive, the algorithm tries to reduce the chance that it will occur by forming as many partitions as possible during the initial partitioning phase.

The hybrid hash join algorithm^[2] is a refinement of the grace hash join which takes advantage of more available memory. During the partitioning phase, the hybrid hash join uses the available memory for two purposes:

1. To hold the current output buffer page for each of the k partitions
2. To hold an entire partition in-memory, known as "partition 0"

Because partition 0 is never written to or read from disk, the hybrid hash join typically performs fewer I/O operations than the grace hash join. Note that this algorithm is memory-sensitive, because there are two competing demands for memory (the hash table for partition 0, and the output buffers for the remaining partitions). Choosing too large a hash table might cause the algorithm to recurse because one of the non-zero partitions is too large to fit into memory.

Hash joins require an equi-join predicate (a predicate comparing values from one table with values from the other table using the equals operator '='). Hash joins can also be evaluated for an anti-join predicate (a predicate selecting values from one table when no related values are found in the other). Applying this algorithm proceeds as follows: first prepare a hash table for the 'not in' side of the join. Then scan the other table, selecting any rows where the join attribute hashes to an empty entry in the hash table.

[edit] References

1. ^ Kitsuregawa, M.; Tanaka, H.; Moto-Oka, T. (1983). "Application of Hash to Data Base Machine and Its Architecture". New Generation Computing 1 (1): 63–74. 
2. ^ DeWitt, D.J.; Katz, R.; Olken, F.; Shapiro, L.; Stonebraker, M.; Wood, D. (1984). "Implementation techniques for main memory database systems". Proc. ACM SIGMOD Conf. 

[edit] External links