嵌套循环联接算法
MySQL使用嵌套循环算法或其上的变体在表之间执行联接。
- 嵌套循环加入算法
- 块嵌套循环连接算法
嵌套循环加入算法
一个简单的嵌套循环联接(NLJ)算法一次从一个循环中的第一个表中读取行,然后将每一行传递给一个嵌套循环,该循环处理联接中的下一个表。重复此过程的次数与要连接的表的次数相同。
假定将使用以下联接类型执行三个表t1
,t2
和之间的t3
联接:
Table Join Type t1 range t2 ref t3 ALL
如果使用简单的NLJ算法,则按以下方式处理联接:
for each rowin t1 matching range {for each rowin t2 matching reference key {for each rowin t3 {if row satisfies join conditions, send to client } } }
因为NLJ算法一次将行从外循环传递到内循环,所以它通常读取多次在内循环中处理的表。
块嵌套循环连接算法
块嵌套循环(BNL)嵌套算法使用对在外部循环中读取的行进行缓冲,以减少必须读取内部循环中的表的次数。例如,如果将10行读入缓冲区并将缓冲区传递到下一个内部循环,则可以将内部循环中读取的每一行与缓冲区中的所有10行进行比较。这将内部表必须读取的次数减少了一个数量级。
在MySQL 8.0.18之前,当无法使用索引时,该算法适用于等联接。在MySQL 8.0.18及更高版本中,在这种情况下采用了哈希联接优化。请参见“哈希联接优化”。
MySQL连接缓冲具有以下特征:
- 当连接的类型为
ALL
或时index
(换句话说,当无法使用任何可能的键并分别对数据或索引行进行完整扫描时),可以使用连接缓冲range
。缓冲的使用也适用于外部联接,如“阻止嵌套循环和批处理键访问联接”所述。 - 连接缓冲区永远不会分配给第一个非恒定表,即使它的类型是
ALL
或index
。 - 联接中只有感兴趣的列存储在其联接缓冲区中,而不是整个行。
join_buffer_size
系统变量来确定每个的大小联接缓冲液用于处理查询。- 为每个可以缓冲的连接分配一个缓冲区,因此可以使用多个连接缓冲区来处理给定查询。
- 在执行连接之前分配连接缓冲区,并在查询完成后释放连接缓冲区。
对于先前针对NLJ算法(无缓冲)描述的示例连接,使用连接缓冲按如下方式进行连接:
for each rowin t1 matching range {for each rowin t2 matching reference key { store used columns from t1, t2in join bufferif buffer is full {for each rowin t3 {for each t1, t2 combinationin join buffer {if row satisfies join conditions, send to client } } empty join buffer } } }if buffer is not empty {for each rowin t3 {for each t1, t2 combinationin join buffer {if row satisfies join conditions, send to client } } }
如果S
是每个所存储的大小t1
,t2
在组合联接缓冲液和C
在缓冲器中的组合的数量,次表的数量t3
被扫描的是:
(S * C)/join_buffer_size + 1
数t3
扫描降低为价值join_buffer_size
时增加,最高可达点join_buffer_size
是大到足以容纳所有上一行组合。那时,通过增大它无法获得任何速度。