性能优化之Block Nested-Loop Join(BNL)

一 介绍

相信许多开发/DBA在使用MySQL的过程中,对于MySQL处理多表关联的方式或者说性能一直不太满意。对于开发提交的含有join的查询,一般比较抗拒,从而建议将join拆分,避免join可能带来的性能问题,同时也增加了程序和DB的网络交互。

MySQL本身只支持一种表间关联方式,就是嵌套循环(Nested Loop)。如果关联表的数据量很大,则join关联的执行时间会非常长。在5.5以后的版本中,MySQL通过引入BNL算法来优化嵌套执行,本文介绍两种join算法 Nested-Loop Join (NLJ) 和Block Nested-Loop Join(BNL) .

二 原理

2.1 Nested Loop Join算法

NLJ 算法:将驱动表/外部表的结果集作为循环基础数据,然后循环从该结果集每次一条获取数据作为下一个表的过滤条件查询数据,然后合并结果。如果有多表join,则将前面的表的结果集作为循环数据,取到每行再到联接的下一个表中循环匹配,获取结果集返回给客户端。 Nested-Loop 的伪算法如下:

因为普通Nested-Loop一次只将一行传入内层循环, 所以外层循环(的结果集)有多少行, 内存循环便要执行多少次.在内部表的连接上有索引的情况下,其扫描成本为O(Rn),若没有索引,则扫描成本为O(Rn*Sn)。如果外部表有很多记录,则Nested-Loops Join会扫描内部表很多次,执行效率非常差。

2.2 Block Nested-Loop Join算法

BNL 算法:将外层循环的行/结果集存入join buffer, 内层循环的每一行与整个buffer中的记录做比较,从而减少内层循环的次数. 举例来说,外层循环的结果集是100行,使用NLJ 算法需要扫描内部表100次,如果使用BNL算法,先把对Outer Loop表(外部表)每次读取的10行记录放到join buffer,然后在InnerLoop表(内部表)中直接匹配这10行数据,内存循环就可以一次与这10行进行比较, 这样只需要比较10次,对内部表的扫描减少了9/10。所以BNL算法就能够显著减少内层循环表扫描的次数. 前面描述的query, 如果使用join buffer, 那么实际join 算法如下:

如果t1, t2参与join的列长度只和为s, c为二者组合数, 那么t3表被扫描的次数为

(S * C)/ join_buffer_size + 1

扫描t3的次数随着join_buffer_size的增大而减少, 直到join buffer能够容纳所有的t1, t2组合, 再增大join buffer size, query 的速度就不会再变快了.

从图中可以看到把t1和t2的结果集放到join_buffer中,而不用每次t1和t2关联后马上有和t3关联,这也是没有必要的,然后只需一次扫描t3即可完成这个查询;需要注意的是join buffer中只保留查询结果中出现的列值,它的大小不依赖于表的大小,我们在伪代码中看到当join buffer被填满后,mysql将会flush buffer。

2.3 MySQL使用Join Buffer有以下要点:

  1. join_buffer_size变量决定buffer大小。
  2. 只有在join类型为all, index, range的时候才可以使用join buffer。
  3. 能够被buffer的每一个join都会分配一个buffer, 也就是说一个query最终可能会使用多个join buffer。
  4. 第一个nonconst table不会分配join buffer, 即便其扫描类型是all或者index。
  5. 在join之前就会分配join buffer, 在query执行完毕即释放。
  6. join buffer中只会保存参与join的列, 并非整个数据行。

三 如何使用

MySQL 5.6版本及以后,优化器管理参数optimizer_switch中的block_nested_loop 参数控制着BNL是否被用于优化器。默认条件下是开启,若果设置为off,优化器在选择 join方式的时候会选择NLJ算法。

四 参考资料

  1. https://dev.mysql.com/doc/refman/5.6/en/nested-loop-joins.html
  2. https://dev.mysql.com/doc/refman/5.6/en/bnl-bka-optimization.html
  3. http://hidba.org/?p=300

原文发表时间:2018-02-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏DOTNET

ASP.NET MVC编程——模型

1 ViewModel 是一种专门提供给View使用的模型,使用ViewModel的理由是实体或领域模型所包含的属性比View使用的多或少,这种情况下实体或领域...

3348
来自专栏我的博客

倒排索引

倒排索引(英语:Inverted index),也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中...

3447
来自专栏linux驱动个人学习

高通 display 驱动【转】

1.8K4
来自专栏好好学习吧

vim简单使用教程

vim的学习曲线相当的大(参看各种文本编辑器的学习曲线),所以,如果你一开始看到的是一大堆VIM的命令分类,你一定会对这个编辑器失去兴趣的。下面的文章翻译自《L...

1453
来自专栏xingoo, 一个梦想做发明家的程序员

在Elasticsearch中查询Term Vectors词条向量信息

这篇文章有点深度,可能需要一些Lucene或者全文检索的背景。由于我也很久没有看过Lucene了,有些地方理解的不对还请多多指正。 更多内容还请参考整理的E...

33410
来自专栏YG小书屋

MapReduce:N keys,N files(三)数据倾斜优化

还是如何将N个keys写到N个文件的需求。 这次的问题是单个key太大,引起的单个reduce任务执行时间过长,导致整个MR运行时间过长。数据大部分的key在...

902
来自专栏好好学习吧

Python怎么去写单元测试用例去测试hello world呢

逛着博客园,看到乙醇大佬的一篇随笔 https://www.cnblogs.com/nbkhic/p/9370446.html,于是就在想怎么测试这句hello...

2613
来自专栏圣杰的专栏

CASE WHEN 高阶用法?

两个表做关联时,以左表为准,若左表某列不为空,则与右表对应列进行关联匹配,为空则不做匹配。 ? 以上做法,有一种说不出来的感觉,不管怎样,问题是解决了。 如...

35813
来自专栏java一日一条

Github 的清点对象算法

这就叫”清点对象”(counting objects),Github需要实时计算出来,需要克隆的对象总数。

772
来自专栏SDNLAB

码农学ODL之Toaster代码解析

Toaster(烤面包机)是OpenDaylight的一个例子,该例子的目的不是让你如何烤面包,而是借这个例子学习OpenDaylight的特性。在Toaste...

4036

扫码关注云+社区

领取腾讯云代金券