Only the columns required for the join are stored in the join buffer. This means that you will need less memory for the join buffer than you may at first expect. (不需要配置太高buffer)
The size of the join buffer is configured with the join_buffer_size variable. The value of join_buffer_size is the minimum size of the buffer! Even if less than 1 KiB of country code values will be stored in the join buffer in the discussed example, if join_buffer_size is set to 1 GiB, then 1 GiB will be allocated. For this reason, keep the value of join_buffer_size low and only increase it as needed.
One join buffer is allocated per join using the block nested loop algorithm.
Each join buffer is allocated for the entire duration of the query.
The block nested loop algorithm can be used for full table scans, full index scans, and range scans.(适用table access 方式)
The block nested loop algorithm will never be used for constant tables as well as the first nonconstant table. This means that it requires a join between two tables with more than one row after filtering by unique indexes to use the block nested loop algorithm
可以通过 optimizer switch 配置BNL() 、 NO_BNL()
BNL 特别擅长在non-indexed joins 的场景,很多时候性能优于hash join。As of version 8.0.20, block nested-loop joins are no longer used; instead, a hash join has replaced it.
哈希join (Hash Join)
build phase. 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.
probe phase. 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.
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.
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.
Clear the in-memory buffer and continue with the rest of the partitions one by one
无论是内存hash还是磁盘hash,都使用xxHash64 hash function。xxHash64有足够快,hash质量好(reducing the number of hash collisions)的特点
BNL不会被选中的时候,MySQL就会选用hash join。
在整理这篇资料时,对要使用的哈希连接算法存在以下要求:
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. If you join the two tables t1 and t2, then examples of join conditions that are supported for hash join include
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.