8.2.1.6 嵌套循环联接算法

MySQL 使用嵌套循环算法或其上的变体在 table 之间执行联接。

嵌套循环加入算法

一个简单的嵌套循环联接(NLJ)算法一次从一个循环中的第一个 table 中读取行,然后将每一行传递给一个嵌套循环,该循环处理联接中的下一个 table。重复此过程的次数与要连接的 table 的次数相同。

假设要使用以下联接类型执行三个 tablet1t2t3之间的联接:

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 算法一次将行从外循环传递到内循环,所以它通常会多次读取在内循环中处理的 table。

块嵌套循环联接算法

块嵌套循环(BNL)嵌套算法使用对外部循环中读取的行的缓冲,以减少必须读取内部循环中的 table 的次数。例如,如果将 10 行读入缓冲区并将缓冲区传递到下一个内部循环,则可以将内部循环中读取的每一行与缓冲区中的所有 10 行进行比较。这将内部 table 必须读取的次数减少了一个数量级。

MySQL 连接缓冲具有以下 Feature:

  • 当联接的类型为ALLindex(换句话说,当无法使用任何可能的键并分别对数据行或索引行进行完全扫描时)或range时,可以使用联接缓冲。缓冲的使用也适用于外部联接,如第 8.2.1.11 节,“阻止嵌套循环和批处理键访问联接”中所述。

  • 连接缓冲区永远不会为第一个非恒定 table 分配,即使其类型为ALLindex

  • 联接中只有感兴趣的列存储在其联接缓冲区中,而不是整个行。

  • 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 是连接缓冲区中每个已存储的t1t2组合的大小,并且 C *是缓冲区中的组合数目,则对 tablet3进行扫描的次数为:

(S * C)/join_buffer_size + 1

t3的扫描次数随着join_buffer_size的值增加而减少,直到join_buffer_size足够大以容纳所有先前的行组合为止。那时,通过增大它无法获得任何速度。