注册 登录
  • 欢迎访问"运维那点事",推荐使用Google浏览器访问,可以扫码关注本站的"微信公众号"。
  • 如果您觉得本站对你有帮助,那么可以扫码捐助以帮助本站更好地发展。

MySQL联接查询算法(NLJ、BNL、BKA、HashJoin)

MySQL SQL 彭东稳 1333次浏览 已收录 0个评论

联接算法是MySQL数据库用于处理联接的物理策略。目前MySQL数据库仅支持Nested-Loops Join算法。而MySQL的分支版本MariaDB除了支持Nested-Loops Join算法外,还支持Classic Hash Join算法。当联接的表上有索引时,Nested-Loops Join是非常高效的算法。根据B+树的特性,其联接的时间复杂度为O(N),若没有索引,则可视为最坏的情况,时间复杂度为O(N²)。MySQL数据库根据不同的使用场合,支持两种Nested-Loops Join算法,一种是Simple Nested-Loops Join(NLJ)算法,另一种是Block Nested-Loops Join(BNL)算法。

在讲述MySQL的Join类型与算法前,看看两张表的Join的过程:

MySQL联接查询算法(NLJ、BNL、BKA、HashJoin)

上图的Fetch阶段是指当内表关联的列是辅助索引时,但是需要访问表中的数据,那么这时就需要再访问主键索引才能得到数据的过程,不论表的存储引擎是InnoDB存储引擎还是MyISAM,这都是无法避免的,只是MyISAM的回表速度要快点,因为其辅助索引存放的就是指向记录的指针,而InnoDB存储引擎是索引组织表,需要再次通过索引查找才能定位数据。

Fetch阶段也不是必须存在的,如果是聚集索引联接,那么直接就能得到数据,无需回表,也就没有Fetch这个阶段。另外,上述给出了两张表之间的Join过程,多张表的Join就是继续上述这个过程。

接着计算两张表Join的成本,这里有下列几种概念:

外表的扫描次数,记为O。通常外表的扫描次数都是1,即Join时扫描一次驱动表的数据即可

内表的扫描次数,记为I。根据不同Join算法,内表的扫描次数不同

读取表的记录数,记为R。根据不同Join算法,读取记录的数量可能不同

Join的比较次数,记为M。根据不同Join算法,比较次数不同

回表的读取记录的数,记为F。若Join的是辅助索引,可能需要回表取得最终的数据

评判一个Join算法是否优劣,就是查看上述这些操作的开销是否比较小。当然,这还要考虑I/O的访问方式,顺序还是随机,总之Join的调优也是门艺术,并非想象的那么简单。

  • Simple Nested-Loops Join(SNLJ)算法

Simple Nested-Loops Join算法相当简单、直接。即外表(驱动表)中的每一条记录与内表中的记录进行比较判断。算法如下:

下图能更好地显示整个SNLJ的过程:

MySQL联接查询算法(NLJ、BNL、BKA、HashJoin)

其中R表为外部表(Outer Table),S表为内部表(Inner Table)。这是一个最简单的算法,这个算法的开销其实非常大。假设在两张表R和S上进行联接的列都不含有索引,外表的记录数为RN,内表的记录数位SN。根据上一节对于Join算法的评判标准来看,SNLJ的开销如下表所示:

开销统计 SNLJ
外表扫描次数(O) 1
内表扫描次数(I) RN
读取记录数(R) RN + SN*RN
Join比较次数(M) SN*RN
回表读取记录次数(F) 0

可以看到读取记录数的成本和比较次数的成本都是SN*RN,也就是笛卡儿积。假设外表内表都是1万条记录,那么其读取的记录数量和Join的比较次数都需要上亿。实际上数据库并不会使用到SNLJ算法。

  • Index Nested-Loops Join(INLJ)算法

SNLJ算法虽然简单明了,但是也是相当的粗暴。因此,在Join的优化时候,通常都会建议在内表建立索引,以此降低Nested-Loop Join算法的开销,MySQL数据库中使用较多的就是这种算法,以下称为INLJ。来看这种算法的伪代码:

由于内表上有索引,所以比较的时候不再需要一条条记录进行比较,而可以通过索引来减少比较,从而加速查询。整个过程如下图所示:

MySQL联接查询算法(NLJ、BNL、BKA、HashJoin)

可以看到外表中的每条记录通过内表的索引进行访问,就是读取外部表一行数据,然后去内部表索引进行二分查找匹配;而一般B+树的高度为3~4层,也就是说匹配一次的io消耗也就3~4次,因此索引查询的成本是比较固定的,故优化器都倾向于使用记录数少的表作为外表(这里是否又会存在潜在的问题呢?)。故INLJ的算法成本如下表所示:

开销统计 SNLJ INLJ
外表扫描次数(O) 1 1
内表扫描次数(I) R 0
读取记录数(R) RN + SN*RN RN + Smatch
Join比较次数(M) SN*RN RN * IndexHeight
回表读取记录次数(F) 0 Smatch (if possible)

上表Smatch表示通过索引找到匹配的记录数量。同时可以发现,通过索引可以大幅降低内表的Join的比较次数,每次比较1条外表的记录,其实就是一次indexlookup(索引查找),而每次index lookup的成本就是树的高度,即IndexHeight。

INLJ的算法并不复杂,也算简单易懂。但是效率是否能达到用户的预期呢?其实如果是通过表的主键索引进行Join,即使是大数据量的情况下,INLJ的效率亦是相当不错的。因为索引查找的开销非常小,并且访问模式也是顺序的(假设大多数聚集索引的访问都是比较顺序的)。

大部分人诟病MySQL的INLJ慢,主要是因为在进行Join的时候可能用到的索引并不是主键的聚集索引,而是辅助索引,这时INLJ的过程又需要多一步Fetch的过程,而且这个过程开销会相当的大:

MySQL联接查询算法(NLJ、BNL、BKA、HashJoin)

由于访问的是辅助索引,如果查询需要访问聚集索引上的列,那么必要需要进行回表取数据,看似每条记录只是多了一次回表操作,但这才是INLJ算法最大的弊端。首先,辅助索引的index lookup是比较随机I/O访问操作。其次,根据index lookup再进行回表又是一个随机的I/O操作。所以说,INLJ最大的弊端是其可能需要大量的离散操作,这在SSD出现之前是最大的瓶颈。而即使SSD的出现大幅提升了随机的访问性能,但是对比顺序I/O,其还是慢了很多,依然不在一个数量级上。

另外,在INNER JOIN中,两张联接表的顺序是可以变换的,即R INNER JOIN S ON Condition P等效于S INNER JOIN R ON Condition P。根据前面描述的Simple Nested-Loops Join算法,优化器在一般情况下总是选择将联接列含有索引的表作为内部表。如果两张表R和S在联接列上都有索引,并且索引的高度相同,那么优化器会选择记录数少的表作为外部表,这是因为内部表的扫描次数总是索引的高度,与记录的数量无关。所以,联接列只要有一个字段有索引即可,但最好是数据集多的表有索引;但是,但有WHERE条件的时候又另当别论了。

下面这条SQL语句,其中emp_no分别是两张表的主键:

可以看到执行计划是先查询表employees,然后将表titles上的主键索引和表employees上的列emp_no进行匹配。此语句在我笔记本上执行大概需要1.29s钟。

这里为什么首先使用employees表呢?因为表employees中的记录少于表titles,这样联接需要匹配的次数就少了,所以SQL优化器选择表employees作为外部表。具体情况如下:

但是这里有一个warning,查看了warning发现MySQL优化器把此语句改写了。

若我们执行的SQL带有WHERE条件时呢?看看不一样的执行计划。如果条件为表employees的主键,执行计划如下:

可以看到执行计划算是极优,同时employees表还是驱动表。自然执行时间也是非常短的,在我笔记本上执行时间为0.00秒。

如果WHERE条件是一个没有索引的字段呢?执行计划如下:

从执行计划上看跟不加WHERE条件几乎差不多,但是可以看到filtered为10%了,而不是100%,说明需要返回的数据量变小了。另外Extra字段中标识使用了WHERE条件过滤。这条SQL在我笔记本上无缓存执行时间为0.8s。

如果WHERE条件是一个有索引的字段呢?这里就不得不提MySQL一个非常重要的特性了,pushed-down conditions(条件下推)优化。就是把索引条件下推到存储引擎层进行数据的过滤并返回过滤后的数据。那么此时的执行计划就如下:

如果能在外部表中过滤掉相当多的一部分数据,那么毫无疑问,内部表的查询次数就会相应的减少很多,联接的执行效率也会因此提高很多。在我笔记本上无缓存执行时间也是0.15秒。

如果我们换一下带索引的条件,把一直成为内部表的titles作为WHERE条件,那么外部表是否会变成titles表呢?执行计划如下:

可以看到确实变为外部表了,因为此时经过过滤后的titles表数据集比employees表要少很多。但是由于title字段选择性不算高,所以执行时间为0.47秒。

最后,如果我们把title和employees表各自选择一个带索引的字段进行WHERE条件过滤,执行计划如下:

虽然从执行计划上看,没有什么太大的变化,但是由于索引的过滤,所以执行时间也同样是很短,在我笔记本上为0.15秒。

虽然在INNER JOIN中可以使用pushed-down conditions的优化方式,但是不能直接在OUTER JOIN中使用该方式,因为有些不满足联接条件的记录会通过外部表行的方式再次添加到结果中,因此需要有条件地使用pushed-down conditions的优化。在优化器内部对于联接查询会设置一个标志来表示是否启用pushed-down conditions的过滤。

  • Block Nested-Loops Join(BNL)算法

在有索引的情况下,MySQL会尝试去使用Index Nested-Loop Join算法,在有些情况下,可能Join的列就是没有索引,那么这时MySQL的选择绝对不会是最先介绍的Simple Nested-Loop Join算法,因为那个算法太粗暴,不忍直视。数据量大些的复杂SQL估计几年都可能跑不出结果。而Block Nested-Loop Join算法较Simple Nested-Loop Join的改进就在于可以减少内表的扫描次数,甚至可以和Hash Join算法一样,仅需扫描内表一次。其使用Join Buffer(联接缓冲)来减少内部循环读取表的次数。

可以看到相比Simple Nested-Loop Join算法,Block Nested-LoopJoin算法仅多了一个所谓的Join Buffer,为什么这样就能减少内表的扫描次数呢?下图相比更好地解释了Block Nested-Loop Join算法的运行过程:

MySQL联接查询算法(NLJ、BNL、BKA、HashJoin)

可以看到Join Buffer用以缓存联接需要的列,然后以Join Buffer批量的形式和内表中的数据进行联接比较。就上图来看,记录r1,r2 … rT的联接仅需扫内表一次,如果join buffer可以缓存所有的外表列,那么联接仅需扫描内外表各一次,从而大幅提升Join的性能。

MySQL数据库使用Join Buffer的原则如下:

* 系统变量Join_buffer_size决定了Join Buffer的大小。

* Join Buffer可被用于联接是ALL、index、和range的类型。

* 每次联接使用一个Join Buffer,因此多表的联接可以使用多个Join Buffer。

* Join Buffer在联接发生之前进行分配,在SQL语句执行完后进行释放。

* Join Buffer只存储要进行查询操作的相关列数据,而不是整行的记录。

Join_buffer_size变量

所以,Join Buffer并不是那么好用的。首先变量join_buffer_size用来控制Join Buffer的大小,调大后可以避免多次的内表扫描,从而提高性能。也就是说,当MySQL的Join有使用到Block Nested-Loop Join,那么调大变量join_buffer_size才是有意义的。而前面的Index Nested-Loop Join如果仅使用索引进行Join,那么调大这个变量则毫无意义。

变量join_buffer_size的默认值是256K,显然对于稍复杂的SQL是不够用的。好在这个是会话级别的变量,可以在执行前进行扩展。建议在会话级别进行设置,而不是全局设置,因为很难给一个通用值去衡量。另外,这个内存是会话级别分配的,如果设置不好容易导致因无法分配内存而导致的宕机问题。

Join Buffer缓存对象

另外,Join Buffer缓存的对象是什么,这个问题相当关键和重要。然在MySQL的官方手册中是这样记录的:Only columns of interest to the join are stored in the join buffer, not whole rows.

可以发现Join Buffer不是缓存外表的整行记录,而是缓存“columns of interest”,具体指所有参与查询的列都会保存到Join Buffer,而不是只有Join的列。比如下面的SQL语句,假设没有索引,需要使用到Join Buffer进行链接:

假设上述SQL语句的外表是a,内表是b,那么存放在Join Buffer中的列是所有参与查询的列,在这里就是(a.col1,a.col2,a.col3)。

通过上面的介绍,我们现在可以得到内表的扫描次数为:

对于有经验的DBA就可以预估需要分配的Join Buffer大小,然后尽量使得内表的扫描次数尽可能的少,最优的情况是只扫描内表一次。

Join Buffer的分配

需要牢记的是,Join Buffer是在Join之前就进行分配,并且每次Join就需要分配一次Join Buffer,所以假设有N张表参与Join,每张表之间通过Block Nested-Loop Join,那么总共需要分配N-1个Join Buffer,这个内存容量是需要DBA进行考量的。

在MySQL 5.6(包括MariaDB 5.3)中,优化了Join Buffer在多张表之间联接的内存使用效率。MySQL 5.6将Join Buffer分为Regular join buffer和Incremental join buffer。假设B1是表t1和t2联接使用的Join Buffer,B2是t1和t2联接产生的结果和表t3进行联接使用的join buffer,那么:

* 如果B2是Regular join buffer,那么B2就会包含B1的Join Buffer中r1相关的列,以及表t2中相关的列。

* 如果B2是Incremental join buffer,那么B2包含表t2中的数据及一个指针,该指针指向B1中r1相对应的数据。

因此,对于第一次联接的表,使用的都是Regular join buffer,之后再联接,则使用Incremental join buffer。又因为Incremental join buffer只包含指向之前Join Buffer中数据的指针,所以Join Buffer的内存使用效率得到了大幅的提高。

此外,对于NULL类型的列,其实不需要存放在Join Buffer中,而对于VARCHAR类型的列,也是仅需最小的内存即可,而不是以CHAR类型在Join Buffer中保存。最后,在MySQL 5.5版本中,Join Buffer只能在INNER JOIN中使用,在OUTER JOIN中则不能使用,即Block Nested Loop算法不支持OUTER JOIN。从MySQL 5.6及MariaDB 5.3开始,Join Buffer的使用得到了进一步扩展,在OUTER JOIN中使join buffer得到支持。

Block Nested-Loop Join开销

Block Nested-Loop Join极大的避免了内表的扫描次数,如果Join Buffer可以缓存外表的数据,那么内表的扫描仅需一次,这和Hash Join非常类似。但是Block Nested-Loop Join依然没有解决的是Join比较的次数,其仍然通过Join判断式进行比较。综上所述,到目前为止各Join算法的成本比较如下所示:

开销统计 SNLJ INLJ BNL
外表扫描次数(O) 1 1 1
内表扫描次数(I) R 0 RN*used_column_size/join_buffer_size + 1
读取记录数(R) RN + SN*RN RN + Smatch RN + S*I
Join比较次数(M) SN*RN RN * IndexHeight SN*RN
回表读取记录次数(F) 0 Smatch (if possible) 0

这个算法很好测试,我们可以随便构建两张没有索引的字段进行联接,然后查看一下执行计划。下面是我在MySQL 5.7版本上的执行计划。

可以看到,SQL执行计划的Extra列中提示Using join buffer (Block Nested Loop),很明显使用了BNL算法。

  • Batched Key Access Join(BKA)算法

Index Nested-Loop Join虽好,但是通过辅助索引进行联接后需要回表,这里需要大量的随机I/O操作。若能优化随机I/O,那么就能极大的提升Join的性能。为此,MySQL 5.6(MariaDB 5.3)开始支持Batched Key Access Join算法(简称BKA),该算法通过常见的空间换时间,随机I/O转顺序I/O,以此来极大的提升Join的性能。

在说明Batched Key Access Join前,首先介绍下MySQL 5.6的新特性mrr——multi range read。因为这个特性也是BKA的重要支柱。MRR优化的目的就是为了减少磁盘的随机访问,InnoDB由于索引组织表的特性,如果你的查询是使用辅助索引,并且有用到表中非索引列(投影非索引字段,及条件有非索引字段),因此需要回表读取数据做后续处理,过于随机的回表会伴随着大量的随机I/O。这个过程如下图所示:

MySQL联接查询算法(NLJ、BNL、BKA、HashJoin)

而mrr的优化在于,并不是每次通过辅助索引读取到数据就回表去取记录,范围扫描(range access)中MySQL将扫描到的数据存入read_rnd_buffer_size,默认256K。然后对其按照Primary Key(RowID)排序,然后使用排序好的数据进行顺序回表,因为我们知道InnoDB中叶子节点数据是按照PRIMARY KEY(ROWID)进行排列的,那么这样就转换随机读取为顺序读取了。这对于IO-bound类型的SQL查询语句带来性能极大的提升。

MRR优化可用于range,ref,eq_ref类型的查询,工作方式如下图:

MySQL联接查询算法(NLJ、BNL、BKA、HashJoin)

要开启mrr还有一个比较重的参数是在变量optimizer_switch中的mrr和mrr_cost_based选项。mrr选项默认为on,mrr_cost_based选项默认为off。mrr_cost_based选项表示通过基于成本的算法来确定是否需要开启mrr特性。然而,在MySQL当前版本中,基于成本的算法过于保守,导致大部分情况下优化器都不会选择mrr特性。为了确保优化器使用mrr特性,请执行下面的SQL语句:

但如果强制开启MRR,那在某些SQL语句下,性能可能会变差;因为MRR需要排序,假如排序的时间超过直接扫描的时间,那性能就会降低。optimizer_switch可以是全局的,也可以是会话级的。

当然,除了调整参数外,数据库也提供了语句级别的开启或关闭MRR,使用方法如下:

在讲述完mrr特性后,再来看BKA Join就非常清晰明了。通过mrr特性优化Join的回表操作,从而提升Join的性能。其算法伪代码如下:

这时BKA Join的整个过程如下所示:

MySQL联接查询算法(NLJ、BNL、BKA、HashJoin)

对于多表join语句,当MySQL使用索引访问第二个join表的时候,使用一个join buffer来收集第一个操作对象生成的相关列值。BKA构建好key后,批量传给引擎层做索引查找。key是通过MRR接口提交给引擎的,这样,MRR使得查询更有效率。

如果外部表扫描的是主键,那么表中的记录访问都是比较有序的,但是如果联接的列是非主键索引,那么对于表中记录的访问可能就是非常离散的。因此对于非主键索引的联接,Batched Key Access Join算法将能极大提高SQL的执行效率。BKA算法支持内连接,外连接和半连接操作,包括嵌套外连接。

Batched Key Access Join算法的工作步骤如下:

1) 将外部表中相关的列放入Join Buffer中。

2) 批量的将Key(索引键值)发送到Multi-Range Read(MRR)接口。

3) Multi-Range Read(MRR)通过收到的Key,根据其对应的ROWID进行排序,然后再进行数据的读取操作。

4) 返回结果集给客户端。

Batched Key Access Join算法的本质上来说还是Simple Nested-Loops Join算法,其发生的条件为内部表上有索引,并且该索引为非主键,并且联接需要访问内部表主键上的索引。这时Batched Key Access Join算法会调用Multi-Range Read(MRR)接口,批量的进行索引键的匹配和主键索引上获取数据的操作,以此来提高联接的执行效率,因为读取数据是以顺序磁盘IO而不是随机磁盘IO进行的。

在MySQL 5.6中默认关闭BKA(MySQL 5.7默认打开),必须将optimizer_switch系统变量的batched_key_access标志设置为on。BKA使用MRR,因此mrr标志也必须打开。目前,MRR的成本估算过于悲观。因此,mrr_cost_based也必须关闭才能使用BKA。以下设置启用BKA:

因为BKA算法的本质是通过MRR接口将非主键索引对于记录的访问,转化为根据ROWID排序的较为有序的记录获取,所以要想通过BKA算法来提高性能,不但需要确保联接的列参与match的操作(联接的列可以是唯一索引或者普通索引,但不能是主键),还要有对非主键列的search操作。例如下列SQL语句:

列a.gender是表employees的数据,但不是通过搜索idx_birth_date索引就能得到数据,还需要回表访问主键来获取数据。因此这时可以使用BKA算法。但是如果联接不涉及针对主键进一步获取数据,内部表只参与联接判断,那么就不会启用BKA算法,因为没有必要去调用MRR接口。比如search的主键(a.emp_no),那么肯定就不需要BKA算法了,直接覆盖索引就可以返回数据了(二级索引有主键值)。

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

  • Classic Hash Join(CHJ)

MySQL数据库虽然提供了BKA Join来优化传统的JOIN算法,的确在一定程度上可以提升JOIN的速度。但不可否认的是,仍然有许多用户对于Hash Join算法有着强烈的需求。Hash Join不需要任何的索引,通过扫描表就能快速地进行JOIN查询,通过利用磁盘的带宽带最大程度的解决大数据量下的JOIN问题。

MariaDB支持Classic Hash Join算法,该算法不同于Oracle的Grace Hash Join,但是也是通过Hash来进行连接,不需要索引,可充分利用磁盘的带宽。

其实MariaDB的Classic Hash Join和Block Nested Loop Join算法非常类似(Classic Hash Join也称为Block Nested Loop Hash Join),但并不是直接通过进行JOIN的键值进行比较,而是根据Join Buffer中的对象创建哈希表,内表通过哈希算法进行查找,从而在Block Nested Loop Join算法的基础上,又进一步减少了内表的比较次数,从而提升JOIN的查询性能。过程如下图所示:

MySQL联接查询算法(NLJ、BNL、BKA、HashJoin)

Classic Hash Join算法先将外部表中数据放入Join Buffer中,然后根据键值产生一张散列表,这是第一个阶段,称为build阶段。随后读取内部表中的一条记录,对其应用散列函数,将其和散列表中的数据进行比较,这是第二个阶段,称为probe阶段。

如果将Hash查找应用于Simple Nested-Loops Join中,则执行计划的Extra列会显示BNLH。如果将Hash查找应用于Batched Key Access Join中,则执行计划的Extra列会显示BKAH。

同样地,如果Join Buffer能够缓存所有驱动表(外表)的查询列,那么驱动表和内表的扫描次数都将只有1次,并且比较的次数也只是内表记录数(假设哈希算法冲突为0)。反之,需要扫描多次内部表。为了使Classic Hash Join更有效果,应该更好地规划Join Buffer的大小。

要使用Classic Hash Join算法,需要将join_cache_level设置为大于等于4的值,并显示地打开优化器的选项,设置过程如下:

最后,各JOIN算法成本之间的比较如下表所示:

开销统计 SNLJ INLJ BNL CHJ
外表扫描次数(O) 1 1 1 1
内表扫描次数(I) R 0 RN*used_column_size/join_buffer_size + 1 RN*used_column_size/join_buffer_size + 1
读取记录数(R) RN + SN*RN RN + Smatch RN + SN*I RN + SN*I
Join比较次数(M) SN*RN RN * IndexHeight SN*RN SN/I
回表读取记录次数(F) 0 Smatch (if possible) 0 0

Hash Join算法虽好,但是仅能用于等值连接,非等值连接的JOIN查询,其就显得无能为力了。另外,创建哈希表也是费时的工作,但是一旦建立完成后,其就能大幅提升JOIN的速度。所以通常情况下,大表之间的JOIN,Hash Join算法会比较有优势。小表通过索引查询,利用BKA Join就已经能很好的完成查询。目前MySQL 8.0已经出了,但目前还没有看到Hash Join的身影,不知未来会不会加入。

<摘录>

InnoDB存储引擎 – 姜

MySQL Join算法与调优白皮书 – 姜

https://dev.mysql.com/doc/refman/5.7/en/bnl-bka-optimization.html


如果您觉得本站对你有帮助,那么可以支付宝扫码捐助以帮助本站更好地发展,在此谢过。
喜欢 (0)or分享 (0)
关于作者:

您必须 登录 才能发表评论!