澳门皇冠金沙网站-澳门皇冠844网站

热门关键词: 澳门皇冠金沙网站,澳门皇冠844网站

MySql联接算法澳门皇冠844网站,查询优化之

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中的记录做比较,可以减少内层循环的扫描次数

举个简单的例子:外层循环结果集有1000行数据,使用NLJ算法需要扫描内层表1000次,但如果使用BNL算法,则先取出外层表结果集的100行存放到join buffer, 然后用内层表的每一行数据去和这100行结果集做比较,可以一次性与100行数据进行比较,这样内层表其实只需要循环1000/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是通过MRR接口提交给引擎的,这样,MRR使得查询更有效率。

如果外部表扫描的是主键,那么表中的记录访问都是比较有序的,但是如果联接的列是非主键索引,那么对于表中记录的访问可能就是非常离散的。因此对于非主键索引的联接,Batched Key Access Join算法将能极大提高SQL的执行效率。BKA算法支持内连接,外连接和半连接操作,包括嵌套外连接。

Batched Key Access Join算法的工作步骤如下:

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

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

  • 3) Multi-Range Read(MRR)通过收到的Key,根据其对应的ROWID进行排序,然后再进行数据的读取操作。

  • 4) 返回结果集给客户端。

Batched Key Access Join算法的本质上来说还是Simple Nested-Loops Join算法,其发生的条件为内部表上有索引,并且该索引为非主键,并且联接需要访问内部表主键上的索引。这时Batched Key Access Join算法会调用Multi-Range Read(MRR)接口,批量的进行索引键的匹配和主键索引上获取数据的操作,以此来提高联接的执行效率,因为读取数据是以顺序磁盘IO而不是随机磁盘IO进行的。

使用BKA时,join_buffer_size的值定义了对存储引擎的每个请求中批量密钥的大小。缓冲区越大,对连接操作的右侧表的顺序访问就越多,这可以显着提高性能。

要使用BKA,必须将optimizer_switch系统变量的batched_key_access标志设置为on。 BKA使用MRR,因此mrr标志也必须打开。目前,MRR的成本估算过于悲观。因此,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)

 

假设在两张表R和S上进行联接的列都不含有索引,算法的扫描次数为:R RxS,扫描成本为O(RxS)。

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提示为外部联接的任何内部表启用联接缓冲,必须为外部联接的所有内部表启用联接缓冲。

澳门皇冠844网站 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三张表执行INNER JOIN查询,并且每张表使用的联接类型如下:

二、Multi-Range Read (MRR)

MRR 的全称是 Multi-Range Read Optimization,是优化器将随机 IO 转化为顺序 IO 以降低查询过程中 IO 开销的一种手段,这对IO-bound类型的SQL语句性能带来极大的提升,适用于range ref eq_ref类型的查询

MRR优化的几个好处

使数据访问有随机变为顺序,查询辅助索引是,首先把查询结果按照主键进行排序,按照主键的顺序进行书签查找

减少缓冲池中页被替换的次数

批量处理对键值的操作

Table   Join Type
t1      range
t2      ref
t3      ALL

在没有使用MRR特性时

第一步 先根据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)

在不使用 MRR 时,优化器需要根据二级索引返回的记录来进行“回表”,这个过程一般会有较多的随机IO, 使用MRR时,SQL语句的执行过程是这样的:

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

  • 如果二级索引扫描到文件的末尾或者缓冲区已满,则使用快速排序对缓冲区中的内容按照主键进行排序

  • 用户线程调用MRR接口取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
    }
  }
}

此外MRR还可以将某些范围查询,拆分为键值对,来进行批量的数据查询,如下:

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

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

若不使用MRR:此时查询的类型为Range,sql优化器会先将key_part1大于1000小于2000的数据取出,即使key_part2不等于10000,带取出之后再进行过滤,会导致很多无用的数据被取出

若使用MRR:如果索引中key_part2不为10000的元组越多,最终MRR的效果越好。优化器会将查询条件拆分为(1000,1000),(1001,1000),... (1999,1000)最终会根据这些条件进行过滤

但是当内部表对所联接的列含有索引时,Simple Nested-Loops Join算法可以利用索引的特性来进行快速匹配,此时的算法调整为如下:

相关参数

当mrr=on,mrr_cost_based=on,则表示cost base的方式还选择启用MRR优化,当发现优化后的代价过高时就会不使用该项优化

当mrr=on,mrr_cost_based=off,则表示总是开启MRR优化

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的表,听起来和MRR类似,实际上MRR也可以想象成二级索引和 primary key的join

如果被Join的表上没有索引,则使用老版本的BNL策略(BLOCK Nested-loop)

对于联接的列含有索引的情况,外部表的每条记录不再需要扫描整张内部表,只需要扫描内部表上的索引即可得到联接的判断结果。

BKA原理

对于多表join语句,当MySQL使用索引访问第二个join表的时候,使用一个join buffer来收集第一个操作对象生成的相关列值。BKA构建好key后,批量传给引擎层做索引查找。key是通过MRR接口提交给引擎的(mrr目的是较为顺序)MRR使得查询更有效率。 

大致的过程如下:

  • BKA使用join buffer保存由join的第一个操作产生的符合条件的数据

  • 然后BKA算法构建key来访问被连接的表,并批量使用MRR接口提交keys到数据库存储引擎去查找查找。

  • 提交keys之后,MRR使用最佳的方式来获取行并反馈给BKA

BNL和BKA都是批量的提交一部分行给被join的表,从而减少访问的次数,那么它们有什么区别呢?

  • BNL比BKA出现的早,BKA直到5.6才出现,而NBL至少在5.1里面就存在。

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

  • BKA主要是指在被join表上有索引可以利用,那么就在行提交给被join的表之前,对这些行按照索引字段进行排序,因此减少了随机IO,排序这才是两者最大的区别,但是如果被join的表没用索引呢?那就使用NBL

在INNER JOIN中,两张联接表的顺序是可以变换的,根据前面描述的Simple Nested-Loops Join算法,优化器在一般情况下总是选择将联接列含有索引的表作为内表。如果两张表R和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使用了MRR,要想使用BAK必须打开MRR功能,而MRR基于mrr_cost_based的成本估算并不能保证总是使用MRR,官方推荐设置mrr_cost_based=off来总是开启MRR功能。打开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使用索引从表中检索行数据的一种优化...

澳门皇冠844网站 2

可以看到SQL先查询user表,然后将表driver上的索引和表user上的列uid进行匹配。

本文由澳门皇冠金沙网站发布于数据库研究,转载请注明出处:MySql联接算法澳门皇冠844网站,查询优化之