Documentation Home
MySQL 8.0 参考手册  / 第8章优化  / 8.2 优化SQL语句  / 8.2.1 优化 SELECT 语句  /  8.2.1.6 嵌套循环连接算法

8.2.1.6 嵌套循环连接算法

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

嵌套循环连接算法

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

假设 要使用以下连接类型执行 三个表t1t2和 之间的连接: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 连接缓冲具有以下特点:

  • 当连接的类型为 ALLor index(换句话说,当没有可能的键可以使用,并且分别对数据或索引行进行完整扫描时)或 range. 缓冲的使用也适用于外部连接,如第 8.2.1.11 节“阻止嵌套循环和成批密钥访问连接”中所述。

  • 永远不会为第一个非常量表分配连接缓冲区,即使它是 ALLor 类型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的组合的大小,是缓冲区中的组合数,则扫描表的次数为: t2Ct3

(S * C)/join_buffer_size + 1

扫描次数t3随着值的join_buffer_size 增加而减少,直到 join_buffer_size大到足以容纳所有先前的行组合为止。在这一点上,通过增大它不会获得任何速度。