Hash join
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.
Hash joins require an equijoin predicate (a predicate comparing values from one table with values from the other table using the equals operator '=').
of the smaller relation. The hash table
entries consist of the join attribute and its row. Because the hash table is accessed by applying a hash function
to the join attribute, it will be much quicker to find a given join attribute's rows by using this table than by scanning the original relation. Once the hash table
is built, scan the larger relation and find the relevant rows from the smaller relation 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.
[GG]
This algorithm is simple, but it requires that the smaller join relation fits into memory, which is sometimes not the case. A simple approach to handling this situation proceeds as follows:
This is essentially the same as the block nested loop
join algorithm. This algorithm scans
more times than necessary.
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 as many partitions as possible during the initial partitioning phase.
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.
This is more efficient when the NOT IN table is smaller than the FROM table
This is more efficient when the NOT IN table is larger than the FROM table
As with the anti-join, semi-join can also be left and right:
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
With this algorithm, each record from the hash table (that is, FROM table) can only be returned once, since it's removed after being returned.
This is more efficient when the IN table is larger than the FROM table
Join (SQL)
An SQL join clause combines records from two or more tables in a database. It creates a set that can be saved as a table or used as is. A JOIN is a means for combining fields from two tables by using values common to each. ANSI standard SQL specifies four types of JOINs: INNER, OUTER, LEFT, and RIGHT...
and is used in the implementation of a relational
Relational database
A relational database is a database that conforms to relational model theory. The software used in a relational database is called a relational database management system . Colloquial use of the term "relational database" may refer to the RDBMS software, or the relational database itself...
database management system
Database management system
A database management system is a software package with computer programs that control the creation, maintenance, and use of a database. It allows organizations to conveniently develop databases for various applications by database administrators and other specialists. A database is an integrated...
.
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.
Hash joins require an equijoin predicate (a predicate comparing values from one table with values from the other table using the equals operator '=').
Classic hash join
The classic hash join algorithm for an inner join of two relations proceeds as follows: first prepare a hash tableHash table
In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...
of the smaller relation. The hash table
Hash table
In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...
entries consist of the join attribute and its row. Because the hash table is accessed by applying a hash function
Hash function
A hash function is any algorithm or subroutine that maps large data sets to smaller data sets, called keys. For example, a single integer can serve as an index to an array...
to the join attribute, it will be much quicker to find a given join attribute's rows by using this table than by scanning the original relation. Once the hash table
Hash table
In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...
is built, scan the larger relation and find the relevant rows from the smaller relation by looking in the hash table
Hash table
In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...
. 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.
[GG]
This algorithm is simple, but it requires that the smaller join relation fits into memory, which is sometimes not the case. A simple approach to handling this situation proceeds as follows:
- For each tuple
in the build input 
- Add
to the in-memory hash table - If the size of the hash table equals the maximum in-memory size:
- Scan the probe input
, and add matching join tuples to the output relation - Reset the hash table
- Scan the probe input
- Add
- Do a final scan of the probe input
and add the resulting join tuples to the output relation
This is essentially the same as the block nested loop
Block nested loop
A block-nested loop is an algorithm used to join two relations in a relational database.This algorithm is a variation on the simple nested loop join used to join two relations R and S...
join algorithm. This algorithm scans
more times than necessary.Grace hash join
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 as many partitions as possible during the initial partitioning phase.Hybrid hash join
The hybrid hash join algorithm 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:- To hold the current output buffer page for each of the
partitions - 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 anti-join
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:Hash left anti-join
- Prepare a hash tableHash tableIn computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...
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
Hash right anti-join
- 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
Hash semi-join
Hash semi-join is used to return the records found in the other table. Unlike plain join, it returns each matching record from the leading table only once, not regarding how many matches are there in the IN table.As with the anti-join, semi-join can also be left and right:
Hash left semi-join
- 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
Hash right semi-join
- 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's removed after being returned.
This is more efficient when the IN table is larger than the FROM table