mysql8 参考手册--嵌套循环联接算法优化

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及更高版本中，在这种情况下采用了哈希联接优化。请参见第8.2.1.4节“哈希联接优化”。

MySQL连接缓冲具有以下特征：
1、当连接的类型为ALL或时 index（换句话说，当无法使用任何可能的键并分别对数据或索引行进行完整扫描时），可以使用连接缓冲 range。缓冲的使用也适用于外部联接，如第8.2.1.12节“阻止嵌套循环和批处理键访问联接”所述。
2、连接缓冲区永远不会分配给第一个非恒定表，即使它的类型是 ALL或 index。
3、联接中只有感兴趣的列存储在其联接缓冲区中，而不是整个行。
4、的join_buffer_size 系统变量来确定每个的大小联接缓冲液用于处理查询。
5、为每个可以缓冲的连接分配一个缓冲区，因此可以使用多个连接缓冲区来处理给定查询。
6、在执行连接之前分配连接缓冲区，并在查询完成后释放连接缓冲区。

对于先前针对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
    }
  }
}