查看“嵌套循环连接算法”的源代码

MySQL使用嵌套循环算法或其变种来执行表之间的连接。


==嵌套循环连接算法==
简单的嵌套循环连接（NLJ）算法逐行从第一个表中读取行，并将每一行传递给处理连接中的下一个表的嵌套循环。这个过程根据需要进行多次，直到所有要连接的表都处理完为止。


假设要使用以下连接类型在表t1、t2和t3之间执行连接：

 Table   Join Type
 t1      range
 t2      ref
 t3      ALL


如果使用简单的NLJ算法，连接的处理过程如下：

 for each row in t1 matching range {
   for each row in t2 matching reference key {
     for each row in t3 {
       if row satisfies join conditions, send to client
     }
   }
 }


因为NLJ算法逐行从外部循环传递行到内部循环，所以它通常会多次读取在内部循环中处理的表。


==块嵌套循环连接算法==
块嵌套循环（BNL）连接算法使用外部循环中读取的行的缓冲区来减少内部循环中读取表的次数。例如，如果将10行读入缓冲区并将缓冲区传递给下一个内部循环，那么在内部循环中读取的每一行都可以与缓冲区中的所有10行进行比较。这将减少内部表必须被读取的次数。


在MySQL 8.0.18之前，当无法使用索引时，该算法应用于等值连接；在MySQL 8.0.18及更高版本中，对于这种情况，使用哈希连接优化。从MySQL 8.0.20开始，MySQL不再使用块嵌套循环，并且在先前使用块嵌套循环的所有情况下，都使用哈希连接。


MySQL连接缓冲具有以下特点：

*当连接的类型为ALL或index时（换句话说，无法使用任何可能的键，并且分别执行完整的数据或索引行扫描）或范围时，可以使用连接缓冲。连接缓冲也适用于外连接。

*对于第一个非常量表，不会分配连接缓冲区，即使它是ALL或index类型。

*连接缓冲仅存储与连接相关的感兴趣的列，而不是整个行。

*join_buffer_size系统变量确定用于处理查询的每个连接缓冲区的大小。

*为每个可进行缓冲的连接分配一个缓冲区，因此给定的查询可能使用多个连接缓冲区进行处理。

*连接缓冲在执行连接之前分配，在查询完成后释放。



对于先前描述的使用NLJ算法（无缓冲）的示例连接，使用连接缓冲的连接处理如下：

 for each row in t1 matching range {
   for each row in t2 matching reference key {
     store used columns from t1, t2 in join buffer
     if buffer is full {
       for each row in t3 {
         for each t1, t2 combination in join buffer {
           if row satisfies join conditions, send to client
         }
       }
       empty join buffer
     }
   }
 }
 
 if buffer is not empty {
   for each row in t3 {
     for each t1, t2 combination in join buffer {
       if row satisfies join conditions, send to client
     }
   }
 }



如果S是连接缓冲区中存储的每个t1、t2组合的大小，C是缓冲区中的组合数，则扫描t3表的次数为：

 (S * C)/join_buffer_size + 1


随着join_buffer_size值的增加，t3扫描的次数减少，直到join_buffer_size足够大，可以容纳所有先前的行组合为止。在该点之后，再增加join_buffer_size的大小不会带来速度上的提升。