hash join describe
hash join:Hash Join The hash join algorithm is a very recent addition to MySQL and is supported in MySQL 8.0.18 and later. It marks a significant break with the tradition of nested loop joins including the block nested loop variant. It is particularly useful for large joins without indexes but can in some cases even outperform an index join. MySQL implements a hybrid between a classic in-memory hash join and the on-disk GRACE hash join algorithm. 2 If it is possible to store all the hashes in memory, then the pure in-memory implementation is used. The join buffer is used for the in-memory part, so the amount of memory that can be used for the hashes is limited by join_buffer_ size . When the join does not fit in memory, the join spills over to disk, but the actual join operations are still performed in memory.
The in-memory hash join algorithm consists of two steps: 1. One of the tables in the join is chosen as the build table . The hash is calculated for the columns required for the join and loaded into memory. This is known as the build phase . 2. The other table in the join is the probe input . For this table, rows are read one at a time, and the hash is calculated. Then a hash key lookup is performed on the hashes calculated from the build table, and the result of the join is generated from the matching rows. This is known as the probe phase .
When the hashes of the build table do not fit into memory, MySQL automatically switches to use the on-disk implementation (based on the GRACE hash join algorithm). The switch from the in-memory to the on-disk algorithm happens if the join buffer becomes full during the build phase. The on-disk algorithm consists of three steps: 1. Calculate the hashes of all rows in both the build and probe tables and store them on disk in several small files partitioned by the hash. The number of partitions is chosen to make each partition of the probe table fit into the join buffer but with a limit of at most 128 partitions. 2. Load the first partition of the build table into memory and iterate over the hashes from the probe table in the same way as for the probe phase for the in-memory algorithm. Since the partitioning in step 1 uses the same hash function for both the build and probe tables, it is only necessary to iterate over the first partition of the probe table. 3. Clear the in-memory buffer and continue with the rest of the partitions one by one. Both the in-memory and on-disk algorithms use the xxHash64 hash function which is known as being fast while still providing hashes of good quality (reducing the number of hash collisions). For the optimal performance, the join buffer needs to be large enough to fit all the hashes from the build table. That said, the same considerations for join_buffer_size exist for hash joins as for block nested loop joins.
MySQL will use the hash join whenever the block nested loop would otherwise be chosen, and the hash join algorithm is supported for the query. At the time of writing, the following requirements exist for the hash join algorithm to be used: • The join must be an inner join. • The join cannot be performed using an index, either because there is no available index or because the indexes have been disabled for the query. • All joins in the query must have at least one equi-join condition between the two tables in the join, and only columns from the two tables as well as constants are referenced in the condition. • As of 8.0.20, anti, semi, and outer joins are also supported. 3 If you join the two tables t1 and t2 , then examples of join conditions that are supported for hash join include • t1.t1_val = t2.t2_val • t1.t1_val = t2.t2_val + 2 • t1.t1_val1 = t2.t2_val AND t1.t1_val2 > 100 • MONTH(t1.t1_val) = MONTH(t2.t2_val) If you consider the recurring example query for this section, you can execute it using a hash join by ignoring the indexes on the tables that can be used for the join: SELECt CountryCode, country.Name AS Country, city.Name AS City, city.District FROM world.country IGNORE INDEX (Primary) INNER JOIN world.city IGNORE INDEX (CountryCode) ON city.CountryCode = country.Code WHERe Continent = 'Asia'; The pseudo code for performing this join is similar to that of a block nested loop except that the columns needed for the join are hashed and that there is support for overflowing to disk.
result = [] join_buffer = [] partitions = 0 on_disk = False for country_row in country: if country_row.Continent == 'Asia': hash = xxHash64(country_row.Code) if not on_disk: join_buffer.append(hash) if is_full(join_buffer): # Create partitions on disk on_disk = True partitions = write_buffer_to_disk(join_buffer) join_buffer = [] else write_hash_to_disk(hash) if not on_disk: for city_row in city: hash = xxHash64(city_row.CountryCode) if hash in join_buffer: country_row = get_row(hash) city_row = get_row(hash) result.append(join_rows(country_row, city_row)) else: for city_row in city: hash = xxHash64(city_row.CountryCode) write_hash_to_disk(hash) for partition in range(partitions): join_buffer = load_build_from_disk(partition) for hash in load_hash_from_disk(partition): if hash in join_buffer: country_row = get_row(hash) city_row = get_row(hash) result.append(join_rows(country_row, city_row)) join_buffer = []
The pseudo code starts out reading the rows from the country table and calculates the hash for the Code column and stores it in the join buffer. If the buffer becomes full, then the code switches to the on-disk algorithm and writes out the hashes from the buffer. This is also where the number of partitions is determined. After this the rest of the country table is hashed. In the next part, for the in-memory algorithm, there is a simple loop over the rows in the city table comparing the hashes to those in the buffer. For the on-disk algorithm, the hashes of the city table are first calculated and stored on disk; then the partitions are handled one by one.
The values of the Code column for the matching rows from the country table are hashed and stored in the join buffer. Then a table scan is executed for the city table with the hash calculated of CountryCode for each row, and the result is constructed from the matching rows.
You can see the query performs very well with the hash join examining the same number of rows as the block nested loop, but it is faster than an index join. This is not a mistake: in some cases, a hash join can outperform even an index join. You can use the following rules to estimate how the hash join algorithm will perform compared to index and block nested loop joins: • For a join without using an index, the hash join will usually be much faster than a block nested join unless a LIMIT clause has been added. Improvements of more than a factor of 1000 have been observed. 4 • For a join without an index where there is a LIMIT clause, a block nested loop can exit when enough rows have been found, whereas a hash join will complete the entire join (but can skip fetching the rows). If the number of rows included due to the LIMIT clause is small compared to the total number of rows found by the join, a block nested loop may be faster. • For joins supporting an index, the hash join algorithm can be faster if the index has a low selectivity. The biggest benefit using the hash joins is by far for joins without an index and without a LIMIT clause. In the end, only testing can prove which join strategy is the optimal for your queries.
You can enable and disable support for hash joins using the hash_join optimizer switch. Additionally, the block_nested_loop optimizer switch must be enabled. Both are enabled by default. If you want to configure the use of hash joins for specific joins, you can use the HASH_JOIN() and NO_HASH_JOIN() optimizer hints. That concludes the discussion about the three high-level join strategies supported in MySQL. There are some lower-level optimizations as well that are worth considering.
