>

MySql联接算法

- 编辑:乐百家599手机首页 -

MySql联接算法

Batched Key Access 算法

对于多表join语句,当MySQL使用索引访谈第三个join表的时候,使用三个join buffer来采撷第多少个操作对象生成的连带列值。BKA营造好key后,批量传给引擎层做索引查找。key是经过M本田CR-VEscort接口提交给引擎的,那样,M奇骏奥迪Q5使得查询更有效用。

只要外界表扫描的是主键,那么表中的记录拜望都以相比较平稳的,然而只要连接的列是非主键索引,那么对于表中记录的拜候或者正是卓殊离散的。由此对此非主键索引的衔接,Batched Key Access Join算法将能相当大增长SQL的奉行成效。BKA算法帮衬内接连,外接连和半连接操作,包涵嵌套外接连。

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

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

  • 2) 批量的将Key(索引键值)发送到Multi-Range Read(M福睿斯奥德赛)接口。

  • 3) Multi-Range Read(M科雷傲奥迪Q5)通过接收的Key,依照其对应的ROWID进行排序,然后再开展数据的读取操作。

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

Batched Key Access Join算法的实质上的话依然Simple Nested-Loops Join算法,其爆发的原则为内部表上有索引,况兼该索引为非主键,而且连接需求拜谒内部表主键上的目录。那时Batched Key Access Join算法会调用Multi-Range Read(MCR-VRAV4)接口,批量的扩充索引键的协作和主键索引上获取数据的操作,以此来巩固联接的施行作用,因为读取数据是以一一磁盘IO实际不是任性磁盘IO进行的。

使用BKA时,join_buffer_size的值定义了对存款和储蓄引擎的各样央求中批量密钥的分寸。缓冲区越大,对连接操作的左侧表的次第访问就愈来愈多,这足以显着提升质量。

要使用BKA,必须将optimizer_switch系统变量的batched_key_access注明设置为on。 BKA使用MSportageCR-V,由此mrr标记也非得张开。如今,M景逸SUVHighlander的血本测度过于悲观。由此,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)

 

瞩目:最后优化器明确联接表的种种只会听从符合的扫描开销来分明,即:M(外表) M(外表)*N(内表);这里的外表和内表分别指的是外界和内表的扫描次数,若是含有索引,正是索引B 树的可观,其余日常都是表的记录数。

一、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”;

BNL和BKA算法的优化器Hint

而对外运输用optimizer_switch系统变量来支配优化程序在对话范围Nelly用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 ...)) ...

 

图片 2

利用境况举个例子

协助索引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%'的过滤操作在二级索引中成功,然后再去基表取相关数据

Block Nested-Loop算法

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

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

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

 

图片 3

BKA和BNL标识

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

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> SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';
Query OK, 0 rows affected (0.00 sec)

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

Batched Key Access (BKA)  提升表join品质的算法。当被join的表能够利用索引时,就先排好顺序,然后再去研究被join的表,听上去和MPAJERO奥迪Q5类似,实际上M汉兰达Evoque也得以设想成二级索引和 primary key的join

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

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算法一次只可以将一行数据传入内部存款和储蓄器循环,所以外层循环结果集有多少行,那么内部存款和储蓄器循环就要施行多少次。

《MySql能力内部原因:SQL编制程序》

连带参数

当mrr=on,mrr_cost_based=on,则意味cost base的章程还增选启用M宝马X5Tiggo优化,当开采优化后的代价过高时就能不使用该项优化

当mrr=on,mrr_cost_based=off,则意味总是敞开MCR-V凯雷德优化

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

参数read_rnd_buffer_size 用来决定键值缓冲区的尺寸。二级索引围观到文件的结尾恐怕缓冲区已满,则动用高效排序对缓冲区中的内容按执照主人键实行排序

转发请申明出处。 我:wuxiwei 出处:

在尚未应用MOdyssey途胜特性时

先是步 先根据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

在INNE福特Explorer JOIN中,两张联接表的种种是能够转换的,根据前边描述的Simple Nested-Loops Join算法,优化器在经常景况下再三再四选拔将连接列含有索引的表作为内表。如若两张表卡宴和S在联接列上都有目录,何况索引的惊人相同,那么优化器会选择记录数少的表作为外界表,那是因为在那之中表的围观次数一连索引的万丈,与记录的多少非亲非故。 上面那条SQL语句:

二、Multi-Range Read (MRR)

M锐界凯雷德 的齐全部是 Multi-Range Read Optimization,是优化器将随便 IO 转化为种种 IO 以减低查询进度中 IO 花费的一种手腕,那对IO-bound类型的SQL语句质量带来相当的大的擢升,适用于range ref eq_ref类型的查询

M瑞虎CRUISER优化的多少个好处

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

调整和缩小缓冲池中页被交换的次数

批量甩卖对键值的操作

MySQL 5.6.3 implements a method of joining tables called the Batched Key Access (BKA) join algorithm. BKA can be applied when there is an index access to the table produced by the second join operand. Like the BNL join algorithm, the BKA join algorithm employs a join buffer to accumulate the interesting columns of the rows produced by the first operand of the join operation. Then the BKA algorithm builds keys to access the table to be joined for all rows in the buffer and submits these keys in a batch to the database engine for index lookups. The keys are submitted to the engine through the Multi-Range Read (MRR) interface. After submission of the keys, the MRR engine functions perform lookups in the index in an optimal way, fetching the rows of the joined table found by these keys, and starts feeding the BKA join algorithm with matching rows. Each matching row is coupled with a reference to a row in the join buffer.

其他MLX570汉兰达还可以够将或多或少范围查询,拆分为键值对,来开展批量的数据查询,如下:

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

表t上有二级索引(key_part1, key_part2),索引根据key_part1,key_part2的顺序排序。

若不利用MSportage传祺:此时查询的门类为Range,sql优化器会先将key_part1大于一千紧跟于两千的数据抽取,就算key_part2不对等一千0,带抽取之后再开展过滤,会招致众多无效的多少被收取

若使用MRR:假诺索引中key_part2不为一千0的元组更加的多,最后MSportage奥德赛的功用越好。优化器会将查询条件拆分为(一千,一千),(1001,一千),... (1996,壹仟)最终会遵照那个规范举办过滤

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

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筛选掉的多少的百分比

###总计 MySql 5.6从此进一步多的算法和陈设的支撑,让联接查询的操作效能更快,在就学的时候精晓了这一个优化职能,更器重的是在实行中精晓SQL优化器的行事规律,擅长用EXPLAIN等SQL分析命令,对MySql查询有越来越好的打听。 ###参谋 有窘迫的地点希望大家多交流,感谢。

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

能够看见,SQL实施布置的Extra列中唤醒Using join buffer,那就象征采用了Block Nested-Loops Join算法。MySql 5.6会在Extra列展现越发详细的新闻,如上边所示:

四、总结

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使用索引从表中检索行数据的一种优化...

  • 系统变量Join_buffer_size决定了Join Buffer的大小。
  • Join Buffer可被用于联接是ALL、index、和range的类别。
  • 每一次联接使用三个Join Buffer,因而多表的连接能够应用五个Join Buffer。
  • Join Buffer在连接发生在此以前实行分红,在SQL语句施行完后进行释放。
  • Join Buffer只存款和储蓄要进行查询操作的连锁列数据,并非整行的笔录。

连锁参数

BAK使用了M哈弗奥迪Q5,要想行使BAK必需展开MRubiconRubicon作用,而M科雷傲LX570基于mrr_cost_based的花费猜测并不能够有限支撑总是利用MEnclave纳瓦拉,官方推荐设置mrr_cost_based=off来接二连三敞开MRubiconHaval成效。展开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

 

图片 4

BKA原理

对于多表join语句,当MySQL使用索引访谈第一个join表的时候,使用一个join buffer来采撷第三个操作对象生成的连带列值。BKA创设好key后,批量传给引擎层做索引查找。key是通过MXC60Tiguan接口提交给引擎的(mrr目标是较为顺序)MRubiconTucson使得查询更有功用。 

大约的进程如下:

  • BKA使用join buffer保存由join的首先个操作爆发的相符条件的数额

  • 接下来BKA算法营造key来访谈被三番两次的表,并批量利用MENVISIONCR-V接口提交keys到数据仓库储存款和储蓄引擎去搜索查找。

  • 提交keys之后,M福睿斯Sportage使用最好的主意来获取行并举报给BKA

BNL和BKA都以批量的提交一部分行给被join的表,进而减少访谈的次数,那么它们有何差距吗?

  • BNL比BKA出现的早,BKA直到5.6才出现,而NBL起码在5.1内部就存在。

  • BNL主要用来当被join的表上无索引

  • BKA首借使指在被join表上有索引能够利用,那么就在行提交给被join的表从前,对那个行遵照索引字段打开排序,由此收缩了猖獗IO,排序那才是二者最大的差距,不过如若被join的表没用索引呢?那就动用NBL

其施行布置如下:

使用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)

在不行使 MLANDKuga 时,优化器必要依附二级索引再次回到的笔录来打开“回表”,那个历程通常会有相当多的人身自由IO, 使用MLANDKuga时,SQL语句的实行进程是这么的:

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

  • 若是二级索引围观到文件的末梢可能缓冲区已满,则动用高效排序对缓冲区中的内容依据主键举办排序

  • 顾客线程调用MENCORE马自达MX-5接口取cluster index,然后根据cluster index 取行数据

  • 当依据缓冲区中的 cluster index取完数据,则持续调用进度 2) 3),直至扫描截至

经过上述进度,优化器将二级索引随机的 IO 进行排序,转化为主键的稳步排列,从而完结了随机 IO 到各样 IO 的转向,提高品质

若是t1,t2和t3三张表实践INNELAND JOIN查询,而且每张表使用的衔接类型如下:

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

本文由乐百家数据库发布,转载请注明来源:MySql联接算法