MySql联接算法

作者:计算机专家

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算法。

【mysql】关于ICP、MRR、BKA等特性,mysqlicpmrrbka

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算法 从一张表中老是读取一条记下,然后将记录与嵌套表中的笔录举行比较。算法如下:

一、Index Condition Pushdown(ICP)

Index Condition Pushdown (ICP)是mysql使用索引从表中检索行数据的一种优化措施,从mysql5.6起来帮助,mysql5.6事先,存款和储蓄引擎会通过遍历索引定位基表中的行,然后回到给Server层,再去为那一个数据行举办WHERE后的口径的过滤。mysql 5.6之后援救ICP后,若是WHERE条件能够利用索引,MySQL 会把这一部分过滤操作放到存款和储蓄引擎层,存款和储蓄引擎通过索引过滤,把满意的行从表中读收取。ICP能压缩引擎层访问基表的次数和 Server层访谈存款和储蓄引擎的次数。

  • ICP的对象是收缩从基表中读取操作的数码,从而裁减IO操作

  • 对此InnoDB表,ICP只适用于补助索引

  • 当使用ICP优化时,施行安插的Extra列展现Using indexcondition提醒

  • 数据库配置 optimizer_switch="index_condition_pushdown=on”;

Block Nested-Loop算法

MySQL BNL算法原来只帮忙内连接,今后已帮衬外连接半连接操作,包括嵌套外连接

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

举个简易的例子:外层循环结果集有一千行数据,使用NLJ算法要求扫描内层表一千次,但假若运用BNL算法,则先抽取外层表结果集的100行寄存到join buffer, 然后用内层表的每一行数据去和这100行结果集做相比较,能够一回性与100行数据开展相比,那样内层表其实只须要循环一千/100=10回,收缩了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>

运用景况举例

协理索引INDEX (a, b, c)

SELECT * FROM peopleWHERE a='12345' AND b LIKE '%xx%'AND c LIKE '%yy%';

若不选取ICP:则是经过二级索引中a的值去基表收取全体a='12345'的数码,然后server层再对b LIKE '%xx%'AND c LIKE '%yy%' 进行过滤

若使用ICP:则b LIKE '%xx%'AND c LIKE '%yy%'的过滤操作在二级索引中成就,然后再去基表取相关数据

Batched Key Access 算法

对于多表join语句,当MySQL使用索引采访第一个join表的时候,使用三个join buffer来搜罗第三个操作对象生成的相干列值。BKA营造好key后,批量传给引擎层做索引查找。key是因而M纳瓦拉福特Explorer接口提交给引擎的,那样,M揽胜宝马X3使得查询更有功能。

只要外界表扫描的是主键,那么表中的记录拜会都以相比平稳的,但是假使连接的列是非主键索引,那么对于表中著录的会见大概便是不行离散的。因而对于非主键索引的连片,Batched Key Access Join算法将能大幅度拉长SQL的实行作用。BKA算法帮助内接连,外接连和半连接操作,包含嵌套外接连。

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

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

  • 2) 批量的将Key(索引键值)发送到Multi-Range Read(M瑞虎奥迪Q5)接口。

  • 3) Multi-Range Read(M途锐LAND)通过接收的Key,依照其对应的ROWID实行排序,然后再实行多少的读取操作。

  • 4) 重临结果集给客商端。

Batched Key Access Join算法的真相上来讲照旧Simple Nested-Loops Join算法,其产生的原则为个中表上有索引,何况该索引为非主键,并且连接须要拜望内部表主键上的目录。那时Batched Key Access Join算法会调用Multi-Range Read(M库罗德ENCORE)接口,批量的扩充索引键的极度和主键索引上获取数据的操作,以此来加强联接的试行作用,因为读取数据是以一一磁盘IO并不是轻易磁盘IO实行的。

使用BKA时,join_buffer_size的值定义了对存款和储蓄引擎的每一个须要中批量密钥的深浅。缓冲区越大,对连日操作的左边表的相继访谈就越来越多,那足以显着提升品质。

要使用BKA,必须将optimizer_switch系统变量的batched_key_access标识设置为on。 BKA使用M兰德安德拉RAV4,因而mrr标记也必须张开。近日,MEvoque揽胜极光的工本预计过于悲观。由此,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_ref时,表示使用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)

 

如若在两张表凯雷德和S上拓宽联网的列都不分包索引,算法的扫视次数为:君越+福特ExplorerxS,扫描开支为O(奥德赛xS)。

ICP特点

  • mysql 5.6中只扶助 MyISAM、InnoDB、NDB cluster

  • mysql 5.6中不协理分区表的ICP,从MySQL 5.7.3方始援救分区表的ICP

  • ICP的优化攻略可用于range、ref、eq_ref、ref_or_null 类型的拜候数据方式

  • 不扶助主建索引的ICP(对于Innodb的聚集索引,完整的记录已经被读取到Innodb Buffer,此时利用ICP并无法减低IO操作)

  • 当 SQL 使用覆盖索引时但只检索部分数据时,ICP 不可能运用

  • ICP的加速效果决意于在积存引擎内经过ICP筛选掉的数指标比例

BNL和BKA算法的优化器Hint

而外选取optimizer_switch系统变量来支配优化程序在对话范围内采取BNL和BKA算法之外,MySQL还帮助优化程序提醒,以便在各样语句的底蕴上海电影制片厂响优化程序。 请参见“优化程序Hint”。

要利用BNL或BKA提醒为外界联接的别的内部表启用联接缓冲,必需为外界联接的有着内部表启用联接缓冲。

图片 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查询,而且每张表使用的连接类型如下:

二、Multi-Range Read (MRR)

MRubicon瑞虎 的齐全部都是 Multi-Range Read Optimization,是优化器将随便 IO 转化为种种 IO 以减低查询进程中 IO 开支的一种花招,那对IO-bound类型的SQL语句质量带来非常大的升官,适用于range ref eq_ref类型的询问

MRAV4卡宴优化的多少个实惠

使数据访谈有自由变为顺序,查询协理索引是,首先把询问结果遵照主键实行排序,依据主键的逐条举大篆签查找

减掉缓冲池中页被交流的次数

批量甩卖对键值的操作

Table   Join Type
t1      range
t2      ref
t3      ALL

在未有选取M冠道Lacrosse本性时

第一步 先根据where条件中的协理索引获取帮忙索引与主键的汇聚,结果集为rest

select key_column, pk_column from tb where key_column=x order by key_column

其次步 通过第一步获取的主键来得到相应的值

for each pk_column value in rest do:
select non_key_column from tb where pk_column=val

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

使用MRR特性时

首先步 先依照where条件中的协理索引获取支持索引与主键的见面,结果集为rest

select key_column, pk_column from tb where key_column = x order by key_column

其次步 将结果集rest放在buffer里面(read_rnd_buffer_size 大小直到buffer满了),然后对结果集rest依照pk_column排序,获得结果集是rest_sort

其三步 利用已经排序过的结果集,访问表中的数量,此时是各种IO.

select non_key_column fromtb where pk_column in (rest_sort)

在不选拔 M讴歌RDXLAND 时,优化器必要依据二级索引重临的记录来进展“回表”,那几个历程常常会有非常多的妄动IO, 使用M冠道Kuga时,SQL语句的进行进程是这么的:

  • 优化器将二级索引查询到的记录停放一块缓冲区中

  • 假如二级索引围观到文件的最终大概缓冲区已满,则利用高效排序对缓冲区中的内容依照主键举办排序

  • 客商线程调用M帕杰罗奥德赛接口取cluster index,然后依据cluster index 取行数据

  • 当根据缓冲区中的 cluster index取完数据,则接二连三调用进度 2) 3),直至扫描甘休

通过上述进程,优化器将二级索引随机的 IO 进行排序,转化为主键的有序排列,进而实现了随意 IO 到各种 IO 的转载,升高质量

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
    }
  }
}

除此以外MEvoque奇骏还足以将一些范围查询,拆分为键值对,来进展批量的数量查询,如下:

SELECT * FROM t WHERE key_part1 >= 1000 AND key_part1 < 2000AND key_part2 = 10000;

表t上有二级索引(key_part1, key_part2),索引依据key_part1,key_part2的各类排序。

若不使用M途胜帕杰罗:此时询问的体系为Range,sql优化器会先将key_part1大于一千紧跟于2000的数量收取,尽管key_part2不等于一千0,带抽出之后再开展过滤,会促成众多没用的多少被收取

若使用MRR:要是索引中key_part2不为10000的元组更多,最后M奥迪Q5CR-V的效果越好。优化器会将查询条件拆分为(一千,一千),(1001,一千),... (一九九八,1000)最终会依靠那一个条件举办过滤

但是当在那之中表对所联网的列含有索引时,Simple Nested-Loops Join算法能够使用索引的表征来拓宽高效合作,此时的算法调度为如下:

相关参数

当mrr=on,mrr_cost_based=on,则意味cost base的法子还挑拣启用MR本田UR-V优化,当开采优化后的代价过高时就能够不接纳该项优化

当mrr=on,mrr_cost_based=off,则意味总是敞开MSportageKuga优化

SET  @@optimizer_switch='mrr=on,mrr_cost_based=on';

参数read_rnd_buffer_size 用来支配键值缓冲区的分寸。二级索引围观到文件的末尾也许缓冲区已满,则使用高效排序对缓冲区中的内容依据主键进行排序

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

三、Batched Key Access (BKA) 和 Block Nested-Loop(BNL)

Batched Key Access (BKA)  进步表join品质的算法。当被join的表能够采纳索引时,就先排好顺序,然后再去寻觅被join的表,听上去和M中华VEvoque类似,实际上MHaval索罗德也得以虚构成二级索引和 primary key的join

假定被Join的表上未有索引,则采用老版本的BNL战术(BLOCK Nested-loop)

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

BKA原理

对于多表join语句,当MySQL使用索引访谈第2个join表的时候,使用三个join buffer来搜聚第贰个操作对象生成的有关列值。BKA构建好key后,批量传给引擎层做索引查找。key是经过MMuranoCRUISER接口提交给引擎的(mrr目标是相比较顺序)M中华V君越使得查询更有功能。 

大抵的历程如下:

  • BKA使用join buffer保存由join的第二个操作发生的相符条件的数目

  • 然后BKA算法塑造key来访谈被接连的表,并批量选拔M昂科雷索罗德接口提交keys到数据仓库储存款和储蓄引擎去探索查找。

  • 交付keys之后,M中华VPRADO使用最棒的方法来获取行并申报给BKA

BNL和BKA都是批量的交由一部分行给被join的表,进而减少访谈的次数,那么它们有怎么着界别吧?

  • BNL比BKA出现的早,BKA直到5.6才面世,而NBL起码在5.第11中学间就存在。

  • BNL重要用以当被join的表上无索引

  • BKA重固然指在被join表上有索引能够使用,那么就在行提交给被join的表在此以前,对这么些行依据索引字段举行排序,由此削减了随意IO,排序那才是三头最大的分别,可是如果被join的表没用索引呢?这就使用NBL

在INNEPRADO JOIN中,两张联接表的相继是足以转换的,依照前面描述的Simple Nested-Loops Join算法,优化器在经常景色下延续采取将对接列含有索引的表作为内表。假使两张表智跑和S在联接列上都有目录,何况索引的万丈一致,那么优化器会接纳记录数少的表作为外界表,那是因为当中表的扫视次数三番两次索引的莫斯中国科学技术大学学,与记录的数额毫无干系。 上边那条SQL语句:

BKA和BNL标识

Using join buffer (Batched Key Access)和Using join buffer (Block Nested Loop)

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

连带参数

BAK使用了MEnclaveKuga,要想利用BAK必得张开MLX570瑞虎成效,而MLAND奔驰M级基于mrr_cost_based的资金估计并不可能确认保证总是选拔MPAJERO奇骏,官方推荐设置mrr_cost_based=off来连接敞开MEscort帕杰罗成效。张开BAK功效(BAK暗中同意OFF):

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

BKA使用join buffer size来规定buffer的高低,buffer越大,访谈被join的表/内部表就越顺序。

BNL暗中认可是开启的,设置BNL相关参数:

SET optimizer_switch=’block_nested_loop’

支持inner join, outer join, semi-join operations,including nested outer joins

BKA首要适用于join的表上有索引可应用,无索引只好利用BNL

 

其实践安插如下:

四、总结

ICP(Index Condition Pushdown)

Index Condition Pushdown是用索引去表里取多少的一种优化,收缩了引擎层访问基表的次数和Server层访谈存款和储蓄引擎的次数,在引擎层就可见过滤掉多量的数额,降低io次数,升高查询语句品质

MRR(Multi-Range Read)

是依据协助/第二索引的查询,减弱随便IO,况且将自由IO转化为各样IO,升高查询成效。

  • 不使用MRR之前(MySQL5.6在此以前),先依照where条件中的协助索引获取支持索引与主键的联谊,再经过主键来获取相应的值。支持索引获取的主键来访谈表中的数据会导致放肆的IO(帮助索引的蕴藏顺序并不是与主键的各类一致),随机主键不在同二个page里时会导致多次IO和率性读。

  • 使用MRR优化(MySQL5.6过后),先遵照where条件中的协助索引获取协理索引与主键的群集,再将结果集放在buffer(read_rnd_buffer_size 直到buffer满了),然后对结果集依据pk_column排序,获得稳步的结果集rest_sort。最终动用已经排序过的结果集,访谈表中的多寡,此时是种种IO。即MySQL 将基于援救索引获取的结果集依据主键实行排序,将冬日化为有序,能够用主键顺序访谈基表,将轻便读转化为顺序读,多页数据记录可二遍性读入或基于此次的主键范围分次读入,缩小IO操作,升高查询功能。

 

*Nested Loop Join算法*

将驱动表/外界表的结果集作为循环基础数据,然后循环该结果集,每趟获得一条数据作为下一个表的过滤条件查询数据,然后合併结果,获取结果集再次回到给客户端。Nested-Loop一回只将一行传入内层循环, 所以外层循环(的结果集)有多少行, 内部存储器循环便要奉行稍微次,成效相当不好。


Block Nested-Loop Join*算法

将外层循环的行/结果集存入join buffer, 内层循环的每一行与成套buffer中的记录做比较,进而减弱内层循环的次数。首要用来当被join的表上无索引。


Batched Key Access*算法

当被join的表能够利用索引时,就先好顺序,然后再去研究被join的表。对那个行依照索引字段展开排序,因此调整和缩短了自由IO。如若被Join的表上未有索引,则采取老版本的BNL战略(BLOCK Nested-loop)。

 

参考:

一、Index Condition Pushdown(ICP) Index Condition Pushdown (ICP)是mysql使用索引从表中检索行数据的一种优化...

图片 2

可以看来SQL先查询user表,然后将表driver上的目录和表user上的列uid进行相称。

本文由杏彩发布,转载请注明来源

关键词: