查看“块嵌套循环和批量键访问连接”的源代码

在MySQL中，提供了一个使用索引访问和连接缓冲区的批量键访问（BKA）连接算法。BKA算法支持内连接、外连接和半连接操作，包括嵌套外连接。BKA的好处包括通过更高效的表扫描来提高连接性能。此外，之前仅用于内连接的块嵌套循环（BNL）连接算法已得到扩展，可以用于外连接和半连接操作，包括嵌套外连接。



==使用块嵌套循环和批量键访问算法加入缓冲区管理==
MySQL可以利用连接缓冲区执行不仅内连接，而且外连接和半连接，这些连接在子查询展开后出现时无需索引访问内部表。此外，当内部表存在索引访问时，连接缓冲区也可以有效地使用。


连接缓冲区管理代码在存储感兴趣的行列的值时稍微更高效地利用连接缓冲区空间：如果行列的值为NULL，则不会为其在缓冲区中分配额外字节，对于VARCHAR类型的任何值，只会分配最小数量的字节。


该代码支持两种类型的缓冲区，常规缓冲区和增量缓冲区。假设使用连接缓冲区B1来连接表t1和t2，并将此操作的结果与表t3进行连接，使用连接缓冲区B2：

*常规连接缓冲区包含每个连接操作数的列。如果B2是一个常规连接缓冲区，那么放入B2中的每一行r由来自B1的行r1的列和来自表t3的匹配行r2的感兴趣列组成。

*增量连接缓冲区仅包含由第二个连接操作数生成的表的行的列。也就是说，它是相对于第一个操作数缓冲区的增量。如果B2是增量连接缓冲区，则它包含行r2的感兴趣列以及与B1中的行r1的链接。


增量连接缓冲区始终相对于先前连接操作的连接缓冲区而言是增量的，所以第一个连接操作的缓冲区始终是常规缓冲区。在刚刚给出的示例中，用于连接表t1和t2的缓冲区B1必须是常规缓冲区。


用于连接操作的增量缓冲区的每一行只包含要连接的表的感兴趣列。这些列会增加一个对第一个连接操作生成的表中匹配行的感兴趣列的引用。在增量缓冲区中，几行可以引用相同的行r，而这些行的列存储在先前的连接缓冲区中，只要这些行都与行r匹配。


增量缓冲区减少了从先前的连接操作缓冲区复制列的频率。这样可以节省缓冲区空间，因为在一般情况下，第一个连接操作生成的行可以与第二个连接操作生成的多行匹配。不需要从第一个操作数制作多个副本。增量缓冲区还通过减少复制时间来节省处理时间。


在MySQL 8.0中，优化器开关变量optimizer_switch的block_nested_loop标志的工作方式如下：

*在MySQL 8.0.20之前，它控制优化器如何使用块嵌套循环连接算法。

*在MySQL 8.0.18及更高版本中，它还控制哈希连接的使用（参见8.2.1.4节“哈希连接优化”）。

*从MySQL 8.0.20版本开始，该标志仅控制哈希连接，不再支持块嵌套循环算法。


batched_key_access标志控制优化器如何使用批量键访问连接算法。


默认情况下，block_nested_loop是打开的，batched_key_access是关闭的。


==对于外连接和半连接的块嵌套循环算法==
MySQL BNL算法的原始实现被扩展以支持外连接和半连接操作（后来被哈希连接算法所取代）。


当使用连接缓冲区执行这些操作时，将为缓冲区中的每一行提供一个匹配标志。


如果使用连接缓冲区执行外连接操作，将检查第二个操作数生成的表的每一行是否与连接缓冲区中的每一行匹配。当找到一条匹配时，将形成一个新的扩展行（原始行加上来自第二个操作数的列），并将其发送给剩余的连接操作进行进一步扩展。此外，启用缓冲区中匹配行的匹配标志。在检查完待连接的表的所有行后，将扫描连接缓冲区。对于从缓冲区中没有启用匹配标志的每一行，将通过NULL补充（第二个操作数中每一列的NULL值）进行扩展，并将其发送给剩余的连接操作进行进一步扩展。


在MySQL 8.0中，optimizer_switch系统变量的block_nested_loop标志的工作方式如下：

*在MySQL 8.0.20之前，它控制优化器如何使用块嵌套循环连接算法。

*在MySQL 8.0.18及更高版本中，它还控制哈希连接的使用。

*从MySQL 8.0.20开始，该标志仅控制哈希连接，不再支持块嵌套循环算法。


在EXPLAIN输出中，当Extra值包含Using join buffer (Block Nested Loop)且type值为ALL、index或range时，表示使用BNL进行表连接。


==批量键访问连接==
MySQL实现了一种称为批量键访问（BKA）连接算法的表连接方法。当对第二个连接操作数生成的表进行索引访问时，可以应用BKA。与BNL连接算法类似，BKA连接算法使用连接缓冲区来累积连接操作的第一个操作数生成的行的感兴趣列。然后，BKA算法构建用于访问要连接的表的键，并将这些键批量提交给数据库引擎进行索引查找。键通过Multi-Range Read (MRR)接口提交给引擎。提交键后，MRR引擎函数以最优的方式在索引中进行查找，获取通过这些键找到的连接表的行，并开始将匹配的行提供给BKA连接算法。每个匹配的行都与连接缓冲区中的一行关联。


在使用BKA时，join_buffer_size的值定义了每个请求向存储引擎发送的键批量的大小。缓冲区越大，对连接操作的右侧表进行顺序访问的次数就越多，这可以显著提高性能。


要使用BKA，必须将optimizer_switch系统变量的batched_key_access标志设置为on。BKA使用MRR，因此还必须打开mrr标志。目前，对于MRR的成本估计过于悲观。因此，为了使用BKA，还需要关闭mrr_cost_based。以下设置启用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 Cluster数据节点。作为回应，SQL节点接收到与相应关联的一组（或多组）匹配行的数据包。BKA连接算法使用这些行构建新的连接行。然后，向数据节点发送一组新的键，并使用返回的数据包中的行构建新的连接行。这个过程会一直持续，直到连接缓冲区中的最后一组键被发送到数据节点，SQL节点已经收到并连接了与这些键匹配的所有行。这提高了性能，因为SQL节点发送给数据节点的具有键的数据包数量较少，意味着在执行连接操作时它与数据节点之间往返的次数较少。


在第一种场景中，连接缓冲区的一部分被保留用于存储通过索引查找选择的行ID（主键），并作为参数传递给MRR函数。


没有专门的缓冲区来存储为连接缓冲区中的行构建的键。相反，将用于构建下一行键的函数作为参数传递给MRR函数。


在EXPLAIN输出中，当Extra值包含Using join buffer (Batched Key Access)且type值为ref或eq_ref时，表示在表上使用了BKA。


==对于块嵌套循环和批量键访问算法的优化器提示==
除了使用optimizer_switch系统变量来控制优化器在整个会话中使用BNL和BKA算法外，MySQL还支持使用优化器提示来在每个语句中影响优化器。


要使用BNL或BKA提示，以启用外连接的任何内部表的连接缓冲区，必须为外连接的所有内部表启用连接缓冲区。