MySQL 查询优化之 Block Nested-Loop 与 Batched Key Access Joins

在MySQL中,能够选拔批量密钥访谈(BKA)连接算法,该算法使用对连接表的目录访谈和接二连三缓冲区。

BKA算法辅助:内连接,外接连和半连接操作,包蕴嵌套外接连。

BKA的优点:尤其便捷的表扫描提升了连年属性。

别的,先前仅用于内一连的块嵌套循环(BNL)连接算法现已扩充,可用于外连接半连接操作,包括嵌套外连接

以下部分商量了三回九转缓冲区管理,它是原始BNL算法扩充,增添BNL算法和BKA算法的底子。
有关半总是计谋的音讯,请参见“使用半接连转换优化子查询,派生表和视图引用”

  • Nested Loop Join
    算法

  • Block Nested-Loop
    算法

  • Batched Key Access
    算法

  • BNL和BKA算法的优化器Hint

连片算法是MySql数据库用于拍卖联接的情理战略。在MySql
5.5本子仅扶助Nested-Loops Join算法,假设联接表上有索引时,Nested-Loops
Join是老大迅猛的算法。即便有目录时间复杂度为O(N),若未有索引,则可就是最坏的情况,时间复杂度为O(N²)。MySql根据不一样的行使处境,协助二种Nested-Loops
Join算法,一种是Simple Nested-Loops Join算法,别的一种是Block
Nested-Loops Join算法。

Nested Loop Join算法

将外层表的结果集作为循环的底子数据,然后循环从该结果集每便一条获取数据作为下三个表的过滤条件去查询数据,然后合併结果。如若有八个表join,那么相应将眼下的表的结果集作为循环数据,取结果集中的每一行再到下三个表中继续开展巡回相配,获取结果集并赶回给客商端。

伪代码如下

for each row in t1 matching range {
  for each row in t2 matching reference key {
     for each row in t3 {
      if row satisfies join conditions,
      send to client
    }
  }
 }

 

平凡的Nested-Loop
Join算法二回只好将一行数据传入内部存款和储蓄器循环,所以外层循环结果集有多少行,那么内部存款和储蓄器循环将在试行多少次。

###Simple Nested-Loops Join算法
从一张表中年岁至期頣是读取一条记下,然后将记录与嵌套表中的笔录进行比较。算法如下:

Block Nested-Loop算法

MySQL
BNL算法原来只扶助内连接,今后已支持外连接半连接操作,包括嵌套外连接

BNL算法原理:将外层循环的行/结果集存入join
buffer,内部存款和储蓄器循环的每一行数据与一切buffer中的记录做相比,能够减掉内层循环的围观次数

举个简易的例子:外层循环结果集有1000行数据,使用NLJ算法须求扫描内层表一千次,但一旦运用BNL算法,则先收取外层表结果集的100行寄存到join
buffer,
然后用内层表的每一行数据去和那100行结果集做比较,能够贰遍性与100行数据开展相比较,那样内层表其实只需求循环1000/100=十一遍,收缩了9/10。

伪代码如下

for each row in t1 matching range {
   for each row in t2 matching reference key {
    store used columns from t1, t2 in join buffer
    if buffer is full {
      for each row in t3 {
         for each t1, t2 combination in join buffer {
          if row satisfies join conditions,
          send to client
        }
        }
       empty buffer
     }
   }
 }

 if buffer is not empty {
    for each row in t3 {
     for each t1, t2 combination in join buffer {
       if row satisfies join conditions,
       send to client
      }
   }
 }

 

一经t1, t2涉足join的列长度只和为s, c为两个组合数, 那么t3表被围观的次数为

(S * C)/join_buffer_size + 1

 

扫描t3的次数随着join_buffer_size的叠合而裁减, 直到join
buffer能够容纳全部的t1, t2组成, 再增大join buffer size, query
的速度就不会再变快了。

 

optimizer_switch系统变量的block_nested_loop注脚调整优化器是或不是选择块嵌套循环算法。

暗中认可景况下,block_nested_loop已启用。

在EXPLAIN输出中,当Extra值包含Using join buffer(Block Nested Loop)type值为ALL,index或range时,表示使用BNL。

示例

mysql> explain SELECT  a.gender, b.dept_no FROM employees a, dept_emp b WHERE a.birth_date = b.from_date;
+----+-------------+-------+------------+------+---------------+------+---------+------+--------+----------+----------------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows   | filtered | Extra                                              |
+----+-------------+-------+------------+------+---------------+------+---------+------+--------+----------+----------------------------------------------------+
|  1 | SIMPLE      | a     | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 298936 |   100.00 | NULL                                               |
|  1 | SIMPLE      | b     | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 331143 |    10.00 | Using where; Using join buffer (Block Nested Loop) |
+----+-------------+-------+------------+------+---------------+------+---------+------+--------+----------+----------------------------------------------------+
2 rows in set, 1 warning (0.00 sec)

 

For each row r in R do
    For each row s in S do
        If r and s satisfy the join condition
            Then output the tuple <r, s>

Batched Key Access 算法

对此多表join语句,当MySQL使用索引访谈第一个join表的时候,使用一个join
buffer来收罗第二个操作对象生成的有关列值。BKA创设好key后,批量传给引擎层做索引查找。key是由此M奥迪Q5揽胜接口提交给引擎的,那样,MKoleos智跑使得查询更有效用。

一经外部表扫描的是主键,那么表中的记录拜候都以相比平稳的,但是一旦连接的列是非主键索引,那么对于表中著录的拜谒或然正是可怜离散的。由此对于非主键索引的连接,Batched
Key Access
Join算法将能急剧增长SQL的实施效能。BKA算法协助内接连,外接连和半连接操作,满含嵌套外接连。

Batched Key Access Join算法的干活步骤如下:

  • 1) 将表面表中相关的列放入Join Buffer中。

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

  • 3) Multi-Range
    Read(MOdysseyLacrosse)通过接受的Key,依据其对应的ROWID进行排序,然后再实行多少的读取操作。

  • 4) 重返结果集给顾客端。

Batched Key Access Join算法的面目上来讲照旧Simple Nested-Loops
Join算法,其爆发的准绳为个中表上有索引,而且该索引为非主键,并且连接供给会见内部表主键上的目录。那时Batched
Key Access Join算法会调用Multi-Range
Read(M宝马7系福睿斯)接口,批量的进展索引键的十分和主键索引上获取数据的操作,以此来进步联接的推行效用,因为读取数据是以一一磁盘IO并不是随机磁盘IO实行的。

使用BKA时,join_buffer_size的值定义了对存款和储蓄引擎的各种央求中批量密钥的轻重。缓冲区越大,对连年操作的侧边表的逐条访谈就更加的多,那能够显着提升品质。

要使用BKA,必须将optimizer_switch系统变量的batched_key_access注明设置为on。
BKA使用M奥迪Q5宝马7系,因而mrr标识也亟须展开。方今,MHavalEnclave的本金估量过于悲观。因而,mrr_cost_based也无法不关闭本领利用BKA。

以下设置启用BKA:

mysql> SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

 

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

示例:

mysql> show index from employees;
+-----------+------------+----------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table     | Non_unique | Key_name       | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-----------+------------+----------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| employees |          0 | PRIMARY        |            1 | emp_no      | A         |      298936 |     NULL | NULL   |      | BTREE      |         |               |
| employees |          1 | idx_name       |            1 | last_name   | A         |        1679 |     NULL | NULL   |      | BTREE      |         |               |
| employees |          1 | idx_name       |            2 | first_name  | A         |      277495 |     NULL | NULL   |      | BTREE      |         |               |
| employees |          1 | idx_birth_date |            1 | birth_date  | A         |        4758 |     NULL | NULL   |      | BTREE      |         |               |
+-----------+------------+----------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
4 rows in set (0.00 sec)


mysql> explain SELECT a.gender, b.dept_no FROM employees a, dept_emp b WHERE a.birth_date = b.from_date;
+----+-------------+-------+------------+------+----------------+----------------+---------+-----------------------+--------+----------+-------+
| id | select_type | table | partitions | type | possible_keys  | key            | key_len | ref                   | rows   | filtered | Extra |
+----+-------------+-------+------------+------+----------------+----------------+---------+-----------------------+--------+----------+-------+
|  1 | SIMPLE      | b     | NULL       | ALL  | NULL           | NULL           | NULL    | NULL                  | 331143 |   100.00 | NULL  |
|  1 | SIMPLE      | a     | NULL       | ref  | idx_birth_date | idx_birth_date | 3       | employees.b.from_date |     62 |   100.00 | NULL  |
+----+-------------+-------+------------+------+----------------+----------------+---------+-----------------------+--------+----------+-------+

#使用hint,强制走bka

mysql> explain SELECT /*+ bka(a)*/ a.gender, b.dept_no FROM employees a, dept_emp b WHERE a.birth_date = b.from_date;
+----+-------------+-------+------------+------+----------------+----------------+---------+-----------------------+--------+----------+----------------------------------------+
| id | select_type | table | partitions | type | possible_keys  | key            | key_len | ref                   | rows   | filtered | Extra                                  |
+----+-------------+-------+------------+------+----------------+----------------+---------+-----------------------+--------+----------+----------------------------------------+
|  1 | SIMPLE      | b     | NULL       | ALL  | NULL           | NULL           | NULL    | NULL                  | 331143 |   100.00 | NULL                                   |
|  1 | SIMPLE      | a     | NULL       | ref  | idx_birth_date | idx_birth_date | 3       | employees.b.from_date |     62 |   100.00 | Using join buffer (Batched Key Access) |
+----+-------------+-------+------------+------+----------------+----------------+---------+-----------------------+--------+----------+----------------------------------------+
2 rows in set, 1 warning (0.00 sec)

 

假使在两张表Tiguan和S上海展览中心开交接的列都不含有索引,算法的扫描次数为:XC60+PRADOxS,扫描开销为O(CR-VxS)。

BNL和BKA算法的优化器Hint

除了这些之外选拔optimizer_switch系统变量来调整优化程序在对话范围内使用BNL和BKA算法之外,MySQL还帮忙优化程序指示,以便在各样语句的功底上海电电影发行体制片厂响优化程序。
请参见“优化程序Hint”。

要运用BNL或BKA提醒为外界联接的别的内部表启用联接缓冲,必得为外界联接的兼具内部表启用联接缓冲。

4503.com 1

使用qb_name

SELECT /*+ QB_NAME(qb1) MRR(@qb1 t1) BKA(@qb2) NO_MRR(@qb3t1 idx1, id2) */ ...
  FROM (SELECT /*+ QB_NAME(qb2) */ ...
  FROM (SELECT /*+ QB_NAME(qb3) */ ... FROM ...)) ...

 

借使t1,t2和t3三张表推行INNE奇骏 JOIN查询,并且每张表使用的连接类型如下:

Table   Join Type
t1      range
t2      ref
t3      ALL

要是应用了Simple Nested-Loops Join算法,则算法达成的伪代码如下:

for each row in t1 matching range {
  for each row in t2 matching reference key {
    for each row in t3 {
      if row satisfies join conditions,
      send to client
    }
  }
}

可是当在那之中表对所联网的列含有索引时,Simple Nested-Loops
Join算法能够运用索引的风味来张开高效协作,此时的算法调度为如下:

For each row r in R do
    lookup r in S index
        If find s == r
           Then output the tuple <r, s>

对此联接的列含有索引的动静,外界表的每条记下不再要求扫描整张内部表,只必要扫描内部表上的目录就可以获得联接的推断结果。

在INNE索罗德 JOIN中,两张联接表的相继是足以转换的,遵照前边描述的Simple
Nested-Loops
Join算法,优化器在日常景观下三番五次挑三拣四将接入列含有索引的表作为内表。假使两张表牧马人和S在联接列上都有目录,并且索引的惊人同样,那么优化器会选拔记录数少的表作为外界表,那是因为中间表的围观次数延续索引的冲天,与记录的数据毫不相关。
上边那条SQL语句:

SELECT * FROM driver join user on driver.driver_id = user.uid;

其推行陈设如下:

4503.com 2

能够见见SQL先查询user表,然后将表driver上的目录和表user上的列uid举行相配。

此地为什么首先利用user表,因为user表的连通列uid并从未索引,而driver表的对接列driver_id有目录,所以Simple
Nested-Loops Join算法将driver表作为内部表。

专一:最后优化器显明联接表的逐个只会循途守辙方便的围观费用来规定,即:M(外表)+M(外表)*N(内表);这里的表面和内表分别指的是外表和内表的围观次数,假如带有索引,正是索引B+树的惊人,其余日常都以表的记录数。

###Block Nested-Loops Join算法 要是联接表未有索引时,Simple
Nested-Loops Join算法扫描内部表很数十次,实施功能会丰富数差。而Block
Nested-Loops Join算法正是对准未有索引的连结情形统一计划的,其选用Join
Buffer(联接缓存)来压缩中间循环取表的次数。

MySql数据库使用Join Buffer的尺度如下:

  • 系统变量Join_buffer_size决定了Join Buffer的大小。
  • Join Buffer可被用来联接是ALL、index、和range的项目。
  • 历次联接使用八个Join Buffer,由此多表的连片能够运用五个Join Buffer。
  • Join Buffer在交接产生此前开展分配,在SQL语句实行完后扩充自由。
  • Join Buffer只存款和储蓄要开展询问操作的有关列数据,并非整行的记录。

对此地方提到的三个表举办连接操作,假若使用Join
Buffer,则算法的伪代码如下:

for each row in t1 matching range {
  for each row in t2 matching reference key {
    store used columns from t1, t2 in join buffer
    if buffer is full {
      for each row in t3 {
        for each t1, t2 combination in join buffer {
          if row satisfies join conditions,
          send to client
        }
      }
      empty buffer
    }
  }
}
if buffer is not empty {
  for each row in t3 {
    for each t1, t2 combination in join buffer {
      if row satisfies join conditions,
      send to client
    }
  }
}

举二个例子,把driver表的_create_date列和user表的create_date列的目录删除,举行交接查询,实行下边包车型地铁SQL语句: