块嵌套循环和批处理密钥访问联接
在MySQL中,可以使用批处理键访问(BKA)联接算法,该算法同时使用对联接表的索引访问和联接缓冲区。BKA算法支持内部联接,外部联接和半联接操作,包括嵌套的外部联接。BKA的好处包括由于更有效的表扫描而提高了连接性能。此外,以前仅用于内部联接的块嵌套循环(BNL)联接算法得到了扩展,可以用于外部联接和半联接操作,包括嵌套的外部联接。
以下各节讨论基于原始BNL算法,扩展的BNL算法和BKA算法的扩展的连接缓冲区管理。有关半联接策略的信息,请参见“使用 EXISTS 策略优化子查询”
- 用于块嵌套循环和批处理密钥访问算法的联接缓冲区管理
- 外部联接和半联接的块嵌套循环算法
- 批量密钥访问联接
- 块嵌套循环和批处理密钥访问算法的优化器提示
用于块嵌套循环和批处理密钥访问算法的联接缓冲区管理
MySQL可以使用联接缓冲区来执行内部联接,而无需内部索引访问内部表,还可以执行在子查询展平后出现的外部联接和半联接。此外,当对内部表进行索引访问时,可以有效使用连接缓冲区。
连接缓冲区管理代码在存储感兴趣的行列的值时会稍微更有效地利用连接缓冲区空间:如果行列的值为,则不会在缓冲区中为行列分配其他字节NULL
,并且为的任何值分配最小字节数该VARCHAR
类型。
该代码支持两种类型的缓冲区:常规缓冲区和增量缓冲区。假设使用了连接缓冲区B1
来连接表t1
,t2
并且t3
使用连接缓冲区将该操作的结果与表连接B2
:
- 常规连接缓冲区包含每个连接操作数中的列。如果
B2
是常规联接缓冲区,则r
放入的每一行B2
均由r1
fromB1
的一行的列r2
和table 的匹配行的有趣的列组成t3
。 - 增量连接缓冲区仅包含第二个连接操作数产生的表行中的列。也就是说,它从第一个操作数缓冲区递增到一行。如果
B2
是增量连接缓冲区,则它包含该行的有趣列以及从r2
到该行的链接。r1
B1
增量连接缓冲区始终相对于来自较早连接操作的连接缓冲区是增量的,因此来自第一次连接操作的缓冲区始终是常规缓冲区。在刚才的例子中,缓冲B1
用来连接表t1
和t2
必须是常规缓冲区。
用于联接操作的增量缓冲区的每一行仅包含要联接表中一行的有趣列。这些列通过引用第一个连接操作数产生的表中匹配行的有趣列来进行扩充。r
只要所有这些行都与row匹配,增量缓冲区中的几行就可以引用同一行,该行的列存储在先前的join缓冲区中r
。
增量缓冲区使从以前的联接操作所使用的缓冲区中复制列的频率降低。这样可以节省缓冲区空间,因为通常情况下,第一个连接操作数产生的行可以与第二个连接操作数产生的几行匹配。不必从第一个操作数复制一行。由于减少了复制时间,因此增量缓冲区还可以节省处理时间。
系统变量的block_nested_loop
和batched_key_access
标志optimizer_switch
控制优化器如何使用Block Nested-Loop和Batched Key Access连接算法。默认情况下,block_nested_loop
is on
和batched_key_access
is off
。请参见“可切换的优化”。优化程序提示也可能适用;请参阅块嵌套循环和批处理密钥访问算法的优化器提示。
有关半联接策略的信息,请参见“使用 EXISTS 策略优化子查询”
外部联接和半联接的块嵌套循环算法
MySQL BNL算法的原始实现已扩展为支持外部联接和半联接操作。
当使用连接缓冲区执行这些操作时,放入缓冲区的每一行都将提供一个匹配标志。
如果使用联接缓冲区执行外部联接操作,则检查第二个操作数产生的表的每一行是否与联接缓冲区中的每一行匹配。找到匹配项后,将形成一个新的扩展行(原始行加上第二个操作数的列),并通过其余的join操作发送以进行进一步扩展。另外,启用缓冲区中匹配行的匹配标志。在检查了要连接的表的所有行之后,将扫描连接缓冲区。缓冲区中未启用匹配标志的每一行都以NULL
补码(NULL
第二个操作数中每一列的值),并通过其余的join操作发送以进行进一步扩展。
系统变量的block_nested_loop
标志optimizer_switch
控制优化器如何使用块嵌套循环算法。默认情况下block_nested_loop
为on
。请参见“可切换的优化”。优化程序提示也可能适用;请参阅块嵌套循环和批处理密钥访问算法的优化器提示。
在EXPLAIN
输出端,为表使用BNL的当被所指Extr
值包含Using join buffer(Block Nested Loop)
与所述type
值是ALL
,index
,或range
。
有关半联接策略的信息,请参见“使用 EXISTS 策略优化子查询”
批量密钥访问联接
MySQL实现了一种联接表的方法,称为批处理密钥访问(BKA)联接算法。当对第二个连接操作数产生的表进行索引访问时,可以应用BKA。像BNL连接算法一样,BKA连接算法采用连接缓冲区来累加连接操作的第一个操作数所产生的行的感兴趣的列。然后,BKA算法将构建键以访问要为缓冲区中的所有行连接的表,并将这些键批量提交给数据库引擎以进行索引查找。密钥通过多范围读取(MRR)接口提交给引擎(请参见“多范围读取优化”))。提交键之后,MRR引擎函数以最佳方式在索引中执行查找,以获取由这些键找到的联接表的行,并开始向BKA联接算法提供匹配的行。每个匹配的行都与对联接缓冲区中的行的引用耦合。
当使用BKA时,的值join_buffer_size
定义在对存储引擎的每个请求中这批密钥的大小。缓冲区越大,对连接操作右侧表的顺序访问就越多,这可以显着提高性能。
要使用BKA,必须将系统变量的batched_key_access
标志optimizer_switch
设置为on
。BKA使用MRR,因此mrr
标记也必须为on
。当前,MRR的成本估算过于悲观。因此,也有必要对mrr_cost_based
要off
用于要使用的BKA。以下设置启用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节点已接收并联接了与这些键匹配的所有行。
在第一种情况下,保留了一部分连接缓冲区来存储由索引查找选择并作为参数传递给MRR函数的行ID(主键)。
没有特殊的缓冲区来存储为连接缓冲区中的行构建的键。而是将为缓冲区中的下一行建立键的函数作为参数传递给MRR函数。
在EXPLAIN
输出中,当Extr
值包含Using join buffer(Batched Key Access)
且type
值为ref
或时,表示对表使用BKA eq_ref
。
块嵌套循环和批处理密钥访问算法的优化器提示
除了在整个optimizer_switch
会话范围内使用系统变量来控制优化器对BNL和BKA算法的使用之外,MySQL还支持优化器提示,以针对每个语句影响优化器。请参见“优化器提示”。
若要使用BNL或BKA提示为外部联接的任何内部表启用联接缓冲,必须为外部联接的所有内部表启用联接缓冲。