Хэш-соединение в реляционных базах данных

Algorithm used in relational databases
The hash join is an example of a join algorithm and is used in the implementation of a relational database management system. All variants of hash join algorithms involve building hash tables from the tuples of one or both of the joined relations, and subsequently probing those tables so that only tuples with the same hash code need to be compared for equality in equijoins. Hash joins are typically more efficient than nested loops joins, except when the probe side of the join is very small. They require an equijoin predicate (a predicate comparing records from one table with those from the other table using a conjunction of equality operators '=' on one or more columns).

A better approach is known as the "grace hash join", after the GRACE database machine for which it was first implemented. This algorithm avoids rescanning the entire relation by first partitioning both and 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 the smallest partitions possible during the initial partitioning phase.

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). Depending on the sizes of the tables, different algorithms can be applied:

Prepare a hash table for the NOT IN side of the join. Scan the other table, selecting any rows where the join attribute hashes to an empty entry in the hash table. This is more efficient when the NOT IN table is smaller than the FROM table.

Prepare a hash table for the FROM side of the join. Scan the NOT IN table, removing the corresponding records from the hash table on each hash hit. Return everything that left in the hash table. This is more efficient when the NOT IN table is larger than the FROM table.

Prepare a hash table for the IN side of the join. Scan the other table, returning any rows that produce a hash hit. The records are returned right after they produced a hit. The actual records from the hash table are ignored. This is more efficient when the IN table is smaller than the FROM table.

Prepare a hash table for the FROM side of the join. Scan the IN table, returning the corresponding records from the hash table and removing them. With this algorithm, each record from the hash table (that is, FROM table) can only be returned once, since it is removed after being returned. This is more efficient when the IN table is larger than the FROM table.