10.2.1.12 块嵌套循环和批量键访问连接
版本8.0
在MySQL中，有一种批量键访问（BKA）连接算法，它既使用对连接表的索引访问，也使用连接缓冲区。BKA算法支持内连接、外连接和半连接操作，包括嵌套外连接。BKA的优势在于，更高效的表扫描提升了连接性能。此外，以前仅用于内连接的块嵌套循环（BNL）连接算法得到了扩展，可用于外连接和半连接操作，包括嵌套外连接。
以下部分将讨论原始BNL算法扩展所基于的连接缓冲区管理、扩展后的BNL算法以及BKA算法。有关半连接策略的信息，请参见10.2.2.1节 “使用半连接转换优化IN和EXISTS子查询谓词”。
- 块嵌套循环和批量键访问算法的连接缓冲区管理
- 外连接和半连接的块嵌套循环算法
- 批量键访问连接
- 块嵌套循环和批量键访问算法的优化器提示
块嵌套循环和批量键访问算法的连接缓冲区管理
MySQL不仅可以使用连接缓冲区执行对内表无索引访问的内连接，还可以执行子查询扁平化后出现的外连接和半连接。此外，当对内表进行索引访问时，连接缓冲区也能有效发挥作用。
在存储感兴趣的行的列值时，连接缓冲区管理代码能更高效地利用连接缓冲区空间：如果某行的列为NULL，缓冲区不会为其分配额外字节；对于VARCHAR类型的任何值，会分配最少数量的字节。
代码支持两种类型的缓冲区：常规缓冲区和增量缓冲区。假设使用连接缓冲区B1连接表t1和t2，并且使用连接缓冲区B2将此操作的结果与表t3进行连接：
- 常规连接缓冲区包含每个连接操作数的列。如果
B2是常规连接缓冲区，放入B2的每一行r由B1中的一行r1的列和表t3中匹配行r2的感兴趣列组成。 - 增量连接缓冲区仅包含由第二个连接操作数生成的表的行的列，即相对于第一个操作数缓冲区中的行是增量的。如果
B2是增量连接缓冲区，它包含行r2的感兴趣列以及指向B1中行r1的链接 。
增量连接缓冲区总是相对于早期连接操作的连接缓冲区是增量的，因此第一个连接操作的缓冲区始终是常规缓冲区。在上述示例中，用于连接表t1和t2的缓冲区B1必须是常规缓冲区。
用于连接操作的增量缓冲区的每一行仅包含要连接表的行的感兴趣列。这些列会增加一个对第一个连接操作数生成的表中匹配行的感兴趣列的引用。只要增量缓冲区中的几行都与行r匹配，它们就可以引用同一行r，该行r的列存储在先前的连接缓冲区中。
增量缓冲区减少了从用于先前连接操作的缓冲区复制列的频率。这节省了缓冲区空间，因为通常情况下，第一个连接操作数生成的一行可以与第二个连接操作数生成的几行匹配，无需对第一个操作数的一行进行多次复制。由于复制时间减少，增量缓冲区也节省了处理时间。
在MySQL 8.0中，optimizer_switch系统变量的block_nested_loop标志的工作方式如下：
- 在MySQL 8.0.20之前，它控制优化器如何使用块嵌套循环连接算法。
- 在MySQL 8.0.18及更高版本中，它还控制哈希连接的使用（请参见10.2.1.4节 “哈希连接优化”）。
- 从MySQL 8.0.20开始，该标志仅控制哈希连接，块嵌套循环算法不再受其控制，且该算法已不再被支持。
batched_key_access标志控制优化器如何使用批量键访问连接算法。
默认情况下，block_nested_loop为on，batched_key_access为off。请参见10.9.2节 “可切换的优化”。也可以应用优化器提示；请参见 “块嵌套循环和批量键访问算法的优化器提示”。
有关半连接策略的信息，请参见10.2.2.1节 “使用半连接转换优化IN和EXISTS子查询谓词”。
外连接和半连接的块嵌套循环算法
MySQL的BNL算法的原始实现得到了扩展，以支持外连接和半连接操作（后来被哈希连接算法取代；请参见10.2.1.4节 “哈希连接优化”）。
当使用连接缓冲区执行这些操作时，放入缓冲区的每一行都会附带一个匹配标志。
如果使用连接缓冲区执行外连接操作，会将第二个操作数生成的表的每一行与连接缓冲区中的每一行进行匹配检查。找到匹配项时，会形成一个新的扩展行（原始行加上第二个操作数的列），并将其发送给后续的连接操作进行进一步扩展。此外，缓冲区中匹配行的匹配标志会被启用。在检查完要连接的表的所有行后，会扫描连接缓冲区。缓冲区中每个匹配标志未启用的行，会用NULL补全（第二个操作数的每列都为NULL值）进行扩展，并发送给后续的连接操作进行进一步扩展 。
在MySQL 8.0中，optimizer_switch系统变量的block_nested_loop标志的工作方式如下：
- 在MySQL 8.0.20之前，它控制优化器如何使用块嵌套循环连接算法。
- 在MySQL 8.0.18及更高版本中，它还控制哈希连接的使用（请参见10.2.1.4节 “哈希连接优化”）。
- 从MySQL 8.0.20开始，该标志仅控制哈希连接，块嵌套循环算法不再受其控制，且该算法已不再被支持。
更多信息请参见10.9.2节 “可切换的优化”。也可以应用优化器提示；请参见 “块嵌套循环和批量键访问算法的优化器提示”。
在EXPLAIN输出中，当Extra值包含Using join buffer (Block Nested Loop)且type值为ALL、index或range时，表示对某个表使用了BNL。
有关半连接策略的信息，请参见10.2.2.1节 “使用半连接转换优化IN和EXISTS子查询谓词”。
批量键访问连接
MySQL实现了一种名为批量键访问（BKA）连接算法的表连接方法。当对第二个连接操作数生成的表进行索引访问时，可以应用BKA。与BNL连接算法一样，BKA连接算法使用连接缓冲区来累积连接操作第一个操作数生成的行的感兴趣列。然后，BKA算法为缓冲区中的所有行构建用于访问要连接表的键，并将这些键批量提交给数据库引擎进行索引查找。这些键通过多范围读取（MRR）接口提交给引擎（请参见10.2.1.11节 “多范围读取优化”）。提交键后，MRR引擎函数会以最佳方式在索引中进行查找，获取这些键找到的连接表的行，并开始将匹配行提供给BKA连接算法。每个匹配行都与连接缓冲区中的一行引用关联。
使用BKA时，join_buffer_size的值定义了每次向存储引擎请求时键批的大小。缓冲区越大，对连接操作右表的访问就越顺序化，这可以显著提高性能。
要使用BKA，必须将optimizer_switch系统变量的batched_key_access标志设置为on。BKA使用MRR，因此mrr标志也必须为on。目前，MRR的成本估算过于保守。因此，为了使用BKA，还必须将mrr_cost_based设置为off。以下设置启用BKA：
mysql> SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';
MRR函数有两种执行场景：
- 第一种场景用于传统的基于磁盘的存储引擎，如
InnoDB和MyISAM。对于这些引擎，通常会将连接缓冲区中所有行的键一次性提交给MRR接口。特定于引擎的MRR函数会对提交的键执行索引查找，从中获取行ID（或主键），然后根据BKA算法的请求，逐个获取所有这些选定行ID的行。每行返回时都带有一个关联引用，以便访问连接缓冲区中的匹配行。MRR函数以最佳方式获取行：按行ID（主键）顺序获取。这提高了性能，因为读取是按磁盘顺序进行的，而不是随机顺序。 - 第二种场景用于远程存储引擎，如
NDB。MySQL服务器（SQL节点）将连接缓冲区中部分行的键包及其关联信息发送到MySQL集群数据节点。作为回应，SQL节点会收到一个（或多个）匹配行的包以及相应的关联信息。BKA连接算法获取这些行并构建新的连接行。然后，将一组新的键发送到数据节点，并使用返回包中的行构建新的连接行。这个过程会持续，直到连接缓冲区中的最后一批键被发送到数据节点，并且SQL节点已接收并连接了与这些键匹配的所有行。这提高了性能，因为SQL节点发送到数据节点的带键包越少，执行连接操作时SQL节点与数据节点之间的往返次数就越少。
在第一种场景中，会预留一部分连接缓冲区来存储通过索引查找选择的行ID（主键），并将其作为参数传递给MRR函数。
没有专门的缓冲区来存储为连接缓冲区中的行构建的键。相反，会将一个为缓冲区中的下一行构建键的函数作为参数传递给MRR函数。
在EXPLAIN输出中，当Extra值包含Using join buffer (Batched Key Access)且type值为ref或eq_ref时，表示对某个表使用了BKA。
块嵌套循环和批量键访问算法的优化器提示
除了使用optimizer_switch系统变量在会话范围内控制优化器对BNL和BKA算法的使用外，MySQL还支持优化器提示，以便在每条语句的基础上影响优化器。请参见10.9.3节 “优化器提示”。
要使用BNL或BKA提示为外连接的任何内表启用连接缓冲，必须为外连接的所有内表启用连接缓冲。
网友评论