4.5 嵌套循环联接算法

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连接缓冲具有以下特征：

• 当连接的类型为ALL或时 index（换句话说，无法使用可能的键，并且分别对数据行或索引行进行完全扫描 时），可以使用连接缓冲 range)。缓冲的使用也适用于外部联接，阻止嵌套循环和批处理键访问联接”所述

• 连接缓冲区永远不会分配给第一个非恒定表，即使它的类型是 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

数t3扫描降低为价值join_buffer_size 时增加，最高可达点 join_buffer_size是大到足以容纳所有上一行组合。那时，通过增大它无法获得任何速度。