当前位置:u赢电竞手机版 > uwin电竞app官网下载 > MySql联接算法uwin电竞app官网下载

MySql联接算法uwin电竞app官网下载

文章作者:uwin电竞app官网下载 上传时间:2019-10-26

BNL和BKA算法的优化器Hint

除了使用optimizer_switch系统变量来控制优化程序在会话范围内使用BNL和BKA算法之外,MySQL还支持优化程序提示,以便在每个语句的基础上影响优化程序。 请参见“优化程序Hint”。

要使用BNL或BKA提示为外部联接的任何内部表启用联接缓冲,必须为外部联接的所有内部表启用联接缓冲。

uwin电竞app官网下载 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 ...)) ...

 

uwin电竞app官网下载 2

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)

 

如果使用了Simple 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算法需要扫描内层表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)

 

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.

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

再次查看SQL执行计划如下:

MySql数据库使用Join Buffer的原则如下:

在MySql 5.5中的执行计划如下:

uwin电竞app官网下载 3

对于上面的SQL语句,使用Block Nested-Loops Join算法需要的时间3.84秒,而不使用的时间是11.93秒。可以看出Block Nested-Loops Join算法对性能提示很多。

uwin电竞app官网下载 4

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

《MySql技术内幕:SQL编程》

select _create_date FROM driver left join user on driver._create_date = user.create_time;

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

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

###Block Nested-Loops Join算法 如果联接表没有索引时,Simple Nested-Loops Join算法扫描内部表很多次,执行效率会非常差。而Block Nested-Loops Join算法就是针对没有索引的联接情况设计的,其使用Join Buffer(联接缓存)来减少内部循环取表的次数。

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

可以看到并没有Using join buffer提示,这就意味着没有使用Block Nested-Loops Join算法,但是在MySql 5.6以后开始支持,上面的SQL语句在MySql 5.6中的执行计划如下:

select _create_date FROM driver join user on driver._create_date = user.create_time;

###总结 MySql 5.6以后越来越多的算法和策略的支持,让联接查询的操作效率越来越快,在学习的时候了解了这些优化效果,更重要的是在实践中明白SQL优化器的工作原理,善于用EXPLAIN等SQL分析命令,对MySql查询有更好的了解。 ###参考 有不对的地方希望大家多交流,谢谢。

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

###Batched Key Access Joins算法 MySql 5.6开始支持Batched Key Access Joins算法(简称BKA),该算法的思想是结合索引和group前面两种方法来提高(search for match)查询比较的操作,以此加快执行效率。

本文由u赢电竞手机版发布于uwin电竞app官网下载,转载请注明出处:MySql联接算法uwin电竞app官网下载

关键词: mysql