MYSQL表联接算法深入研究

在关系型数据库中，表联接是一种常见的操作，它使得我们可以根据不同的条件将多个表中的数据进行连接。而MySQL作为一种常用的关系型数据库，其表联接算法包括NLJ、BNL、BKA、BNLH等多种，在实际应用中选择不同的算法还需要考虑到数据量、表结构等因素。本文将对MySQL中常见的表联接算法进行浅述，包括各个算法的实现原理和适用场景。

SNLJ算法（ Simple Nested-Loops Join,简单嵌套循环连接 ）

算法简述

简单嵌套循环连接（Simple Nested-Loops Join）算法基于一个简单的思想，即对于两个输入数据表R和S，Simple Nested-Loops Join算法从表R中选取一条记录，然后循环遍历表S的所有记录，将R和S之间满足联接条件的记录匹配，并将匹配后的结果存放在一个新的结果集中。然后，算法继续从表R中选取下一条记录，重复以上的操作，直到R中所有的记录都被遍历过。见下图：

优缺点

该算法的一个明显优点是实现简单，实现逻辑清晰明了。

但是存在一个关键问题：*被驱动表S的被扫描的次数等于驱动表R的记录数*。

当数据表R和S中的记录数（Rn和Sn）非常大时，所需要扫描的记录条数为RnSn，即笛卡尔积，算法的执行时间会急剧增加。如果两R,S表都有十万条记录，那么RnSn将会是100亿条，这是无法被接受的。

适用场景

由于上述缺点不能够被接受，MYSQL并没有采用该算法，而是实现了效率更高的BNL算法。

BNL算法**（** Block Nested-Loops Join，基于块的嵌套循环联接 ）

算法简述

BNL算法在SNLJ算法上做了优化：

首先，将驱动表尽量放到内存当中。理想状态下，驱动表R，全部被放到了内存。然后，将被驱动表S表中的每条记录都在内存中与驱动表R表的记录逐个匹配筛选。

这样被驱动表S只需从磁盘扫描1次，而驱动表也只需要从磁盘扫描一次。这样相比SNLJ算法，扫描被驱动被的次数，从Rn次降低到了1次，大大降低了磁盘IO的压力，从而提高了效率。

如果内存配置不足，不能一次性将驱动表R所有记录加到内存（Join Buffer），那么驱动表会被切分成块，再逐块加载到内存中。这也正是算法名称中Block的含义。

这时，算法过程如下：

将驱动表R分成N块，首先将第一块N1的记录加载到内存（Join Buffer）中，然后扫描被驱动表S，将被驱动表S中的每条记录，逐条加载到内存，与内存中的N1记录进行匹配。然后将驱动表R的第二块N2的记录加载到内存中，然后扫描被驱动表S，将被驱动表S中的每条记录，逐条加载到内存，与内存中的N2记录进行匹配。重复以上操作，直到驱动表的N块记录都添加到内存中，并与被驱动表S所有记录匹配完毕。

可以看出，上述过程中，被驱动表被扫描的次数，也只有驱动表R被分的块数N。这相较于SNLJ算法中的被扫描的次数（驱动表R的记录数），大大减少了。

图示如下：

驱动表第一个块加载到内存，并与被驱动表逐行比较：

驱动表第二个块加载到内存，并与被驱动表逐行比较：

驱动表的其他块依次加入内存，并于被驱动表比较，不再画图表示。

适用场景

在被驱动表的联接字段不存在索引时，会使用BNL算法。

相关配置

Join Buffer 由join_buffer_size配置控制，这个配置在BNL算法中决定了驱动表被分的块数，也即是被驱动表被扫描的次数，所以对性能的提升尤为重要。

join_buffer_size 默认为256K，这对于大量数据的场景很显然是不够的，需要手动调大该配置。

join_buffer_size可以全局配置（配置文件[mysqld]模块join_buffer_size参数），也可以在会话级别配置（select /*+ set_var(join_buffer_size=248M) */ * from …;）。

在大表使用BNL算法时，适当提升该配置，将会提升查询效率。

示例

表R和表S的name字段都没有索引。

Explain 时extra字段中，存在using join buffer(flat,BNL join)，表示用到了BNL算法。

INLJ算法（ Index Nested-Loops Join，基于索引的嵌套循环联接 ）

算法简述

上述BNL算法，尽管使用到了内存，不必一遍遍的从磁盘上扫描被驱动表，但是没有使用索引，所以仍需要在内存中逐行的联接匹配查询，所以联接时所需的比较的次数仍然是驱动表行数Rn被驱动表行数Sn，即RnSn。

如果在联接时被驱动表存在索引，这样就可以利用B+树的特性（层高固定数层，一般3-4层），将联接比较次数降为驱动表行数被驱动表B+树的层高，Rn3或Rn*4（唯一索引的场景，非唯一索引要加上同值个数），这样就大大提高了联接匹配效率。

这就是基于索引的嵌套循环联接INLJ算法的优势。

适用场景

被驱动表的被联接字段有索引，这样才可以用到INLJ算法，从而使联接效率大大提高。

相关配置

该算法不需要配置就可以使用，也是最常用的算法，需要注意的是驱动表选择的问题。

*不同的联接语句哪个是驱动表？*

使用左联接时（left join）时，左侧表是驱动表。

使用右联接时（right join）时，右侧表是驱动表。

使用内连接时（join）时，由优化器自行选择驱动表。

使用内连接时，可以使用straight join代替join，从而指定左侧表是驱动表。

*选择驱动表的原则有哪些？*

被驱动表的联接字段尽量有索引，这样才可以用到高效的INLJ算法。

如果两个表的联接字段索引情况一样（都有索引或都没有索引），要小表驱动大表：在通过where条件过滤后剩余的参与join计算的个字段数据总量小的表，作为驱动表。这样无论是INLJ算法还是BNL算法，效率都会相对较高。

示例

通过explain可以看到S表关联查询时，用到了主键索引，Extra中没有其他信息，这说明用到了INLJ算法。

BKA算法（Batched Key Access Join,批量键访问联接）

算法简述

INLJ算法虽然已经用到了被驱动表的索引，但是，当用到的索引是二级索引且需要回表时，就会因回表产生大量的随机IO。如下图：

BKA算法就是在INLJ的基础上优化这个问题，想办法将回表时的随机IO变成顺序IO。

具体来说，BKA算法使用到了join_buffer，一次性从驱动表（或上次join的结果）取出多条记录，放到join_buffer中，通过引擎的MRR接口，得到的顺序的回表主键ID。进而使用有顺序的主键ID，回表查询，使得回表动作由随机IO变成了顺序IO，从而提高效率。

如下图：

进一步的，可以使用MRR接口进行进一步优化。

在上述联接中，查询被驱动表索引时（上例中的S.score），也是随机顺序的。可以先根据主键id排序，然后再查询，这就使对被驱动表的索引查询由随机顺序，改为了顺序查询，进而进一步提高查询效率。这也就是BKA算法中的MRR键排序（Key Sorting for Batched Key Access）。

适用场景

当被驱动表的联接字段是二级索引且不是覆盖索引，需回表获取数据，且需查询的数据量巨大，可以考虑使用BKA算法进行优化。

相关配置

*开启MRR*

set optimizer_switch=‘mrr=on’;

*开启MRR键排序*

set optimizer_switch=‘mrr_sort_keys=on’;

*调整join cache级别*

set join_cache_level=6;

示例

执行计划中extra字段中有Using join buffer (flat, BKA join); Rowid-ordered scan，说明使用到了BKA算法，并对主键进行了排序，然后扫描数据。

*开启MRR键排序的场景*

可以看到执行计划中extra字段多了Key-ordered，说明使用了MRR键排序能力。

BNLH算法（Block Nested Loop Hash join,基于块的嵌套循环哈希联接）

算法简述

基本思想如下，首先将驱动表数据加载到内存，并在内存中建立一张哈希表。然后，将对于被驱动表的每一条记录依次对做哈希运算，将得到哈希值与内存中的驱动表的哈希值比较。这样只需要遍历一遍被驱动表，就可以完成联接操作。

跟BNL算法一样，如果join buffer 容量不足以一次性加载所有驱动表数据，则会分块加载一部分，这样被驱动表被扫描的次数，就是驱动表所分的块数。

如下图：

优缺点

BNLH算法的优势有两点，一是不需要被驱动表有索引。二是相比于BNL算法联接，在联接比较时，每条被驱动表的记录需要遍历join buffer中所有驱动表数据，而BHJ算法只需要比较一个哈希桶里的数据，这就大大减少了比较的数据量，从而提高了效率。

哈希算法虽好，但是也有两个弊端。一是该算法只能用于等值联接的场景，二是哈希计算本身也会增加一定的消耗。

适用场景

被驱动表联接字段不存在索引，且联接查询为等值查询，数据量特别大的场景。

相关配置

BHJ算法默认是关闭的，需要将join_cache_level设置为大于等于4的值，并显示地打开优化器的选项，设置过程如下：

set join_cache_join=4;

set optimizer_switch=‘join_cache_hashed=on’;

示例

执行计划中extra字段中有Using join buffer (flat, BNLH join)，说明使用到了BNLH哈希算法。

总结

本文介绍了MYSQL中常见的多种联接算法，不同的算法有不同的适用场景。在SQL问题排查或者优化SQL语句时，可以根据不同的场景选用不同的算法，提高联接查询语句的执行效率。

其他：示例环境说明

1.上文示例中数据库版本为10.9.5-MariaDB-log。

2.上文示例中表结构为如下：

CREATE TABLE S (

id int(11) NOT NULL AUTO_INCREMENT,

name varchar(255) DEFAULT NULL,

score int(11) DEFAULT 0,

PRIMARY KEY (id),

KEY score (score)

) ENGINE=InnoDB;

CREATE TABLE R (

id int(11) NOT NULL AUTO_INCREMENT,

name varchar(255) DEFAULT NULL,

score int(11) DEFAULT 0,

PRIMARY KEY (id),

KEY score (score)

) ENGINE=InnoDB;

name varchar(255) DEFAULT NULL,

score int(11) DEFAULT 0,

PRIMARY KEY (id),

KEY score (score)

) ENGINE=InnoDB;

CREATE TABLE R (

id int(11) NOT NULL AUTO_INCREMENT,

name varchar(255) DEFAULT NULL,

score int(11) DEFAULT 0,

PRIMARY KEY (id),

KEY score (score)

) ENGINE=InnoDB;