MySQL机制介绍之NLJ、BNL、BKA

发表于 | 分类于 |

背景

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

NLJ

将驱动表的结果集作为循环基础数据，然后循环从该结果集中每次一条获取数据作为下一个表的过滤条件查询数据，然后合并结果。
如果有多表join，则将前面的表的结果集作为循环数据，取到每行再到链接的下一个表循环匹配。

SNLJ

Simple Nested-Loops Join(SNLJ，简单嵌套循环联接)，该算法比较简单、直接。驱动表中的每一条记录都与被驱动表中的记录进行匹配判断。对于两表连接，驱动表只需要被访问一次，而被驱动表需要访问多次。这个算法的开销非常大，复杂度为笛卡尔积。

其实现伪代码如下：

1
2
3
4
For each row r in R do                         -- 扫描R表（驱动表）
    For each row s in S do                     -- 扫描S表（被驱动表）
        If r and s satisfy the join condition  -- 如果r和s满足join条件
            Then output the tuple <r, s>       -- 返回结果集

INLJ

Index Nested-Loops Join(INLJ，基于索引的嵌套循环联接)，由于SNLJ算法非常粗暴，每次都会扫描全表。所以一般会在被驱动表的相关字段上建立索引，以降低SNLJ的复杂度，这种算法就被称为INLJ。
外表中的每条记录通过内表的索引进行访问，就是读取外部表一行数据，然后去内部表索引进行二分查找匹配；而一般B+树的高度为3~4层，也就是说匹配一次的io消耗也就3~4次，因此索引查询的成本是比较固定的，故优化器都倾向于使用记录数少的表作为外表。

其实现为代码如下：

1
2
3
4
For each row r in R do                     -- 扫描R表
    lookup s in S index                    -- 查询S表的索引（固定3~4次IO，B+树高度）
        If find s == r                     -- 如果r匹配了索引s
            Then output the tuple <r, s>   -- 返回结果集

BNL

在SNLJ中，被驱动表需要进行全表扫描多次，由于MySQL的内存有限，所以可能会导致被驱动表中的数据页频繁的被读进内存又刷到磁盘中。
能不能有一个办法避免这样的情况发生呢？于是便加入了join buffer的概念。一次性判断多条记录，从而减少全表扫描的次数。
这种方式被称为BNL，BNL将外层循环的行/结果集存入到join buffer，然后每次遍历被驱动表都与join buffer中的数据进行比较。以此来减少全表扫描的次数。


1
2
3
4
5
For each tuple r in R do                             -- 扫描外表R
    store used columns as p from R in Join Buffer    -- 将部分或者全部R的记录保存到Join Buffer中，记为p
    For each tuple s in S do                         -- 扫描内表S
        If p and s satisfy the join condition        -- p与s满足join条件
            Then output the tuple                    -- 返回为结果集

开启BNL的方式：set optimizer_switch='block_nested_loop=on'

join buffer

在MySQL实例中存在多种join查询的语句时，可通过调整join buffer的大小来减少磁盘访问。
但是由于join buffer是会话级别的，所以并不能设置太大，避免出现内存问题。

  • 系统变量Join_buffer_size决定了Join Buffer的大小。
  • Join Buffer可被用于联接是ALL、index、和range的类型。
  • 每次联接使用一个Join Buffer，因此多表的联接可以使用多个Join Buffer。
  • Join Buffer在联接发生之前进行分配，在SQL语句执行完后进行释放。
  • Join Buffer只存储要进行查询操作的相关列数据，而不是整行的记录。

BKA

Batched Key Access Join(BKA，批量键访问联接)，MySQL在5.6版本中引入了BKA算法来对INLJ算法进行优化。
BKA其实就等价于MRR+INLJ。关于MRR的介绍可以参考MySQL机制介绍之MRR


BKA主要工作流程为：

  1. 将外部表中相关的列放入Join Buffer中。
  2. 批量的将Key（索引键值）发送到Multi-Range Read（MRR）接口。
  3. Multi-Range Read（MRR）通过收到的Key，根据其对应的ROWID进行排序，然后再进行数据的读取操作。
  4. 返回结果集给客户端。

开启BKA方式：SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

CHJ

// TODO studing

https://yq.aliyun.com/articles/27687
https://www.cnblogs.com/zuochanzi/p/10409752.html