澳门新蒲京娱乐

澳门新蒲京娱乐 14
作业隔断等第详解,SqlServer注意事项统计
澳门新蒲京娱乐 20
20免安装版配置方法图文教程澳门新蒲京娱乐:

查询优化之,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数据库使用Join Buffer的原则如下:

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 ...)) ...

 

在INNER JOIN中,两张联接表的顺序是可以变换的,根据前面描述的Simple
Nested-Loops
Join算法,优化器在一般情况下总是选择将联接列含有索引的表作为内表。如果两张表R和S在联接列上都有索引,并且索引的高度相同,那么优化器会选择记录数少的表作为外部表,这是因为内部表的扫描次数总是索引的高度,与记录的数量无关。
下面这条SQL语句:

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

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)

 

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

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)

 

注意:最终优化器确定联接表的顺序只会按照确切的扫描成本来确定,即:M(外表)+M(外表)*N(内表);这里的外表和内表分别指的是外表和内表的扫描次数,如果含有索引,就是索引B+树的高度,其他一般都是表的记录数。

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

这里为什么首先使用user表,因为user表的联接列uid并没有索引,而driver表的联接列driver_id有索引,所以Simple
Nested-Loops Join算法将driver表作为内部表。

可以看到,SQL执行计划的Extra列中提示Using join
buffer,这就代表使用了Block Nested-Loops Join算法。MySql
5.6会在Extra列显示更为详细的信息,如下面所示:

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

转载请注明出处。 作者:wuxiwei
出处:

如果使用了Simple Nested-Loops Join算法,则算法实现的伪代码如下:

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

注意点:在MySql 5.5版本中,Join Buffer只能在INNER JOIN中使用,在OUTER
JOIN中则不能使用,即Block Nested-Loops Join算法不支持OUTER
JOIN。下面的left join语句:

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

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

图片 2

  1. 将外部表中相关的列放入Join Buffer中。
  2. 批量的将Key(索引键值)发送到Multi-Range Read(MRR)接口。
  3. Multi-Range
    Read(MRR)通过收到的Key,根据其对应的ROWID进行排序,然后再进行数据的读取操作。
  4. 返回结果集给客户端。
mysql> SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';
Query OK, 0 rows affected (0.00 sec)

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

对于Multi-Range
Read(MRR)的介绍属于MySql索引的内容,这里简单说明:MySQL
5.6的新特性MRR。这个特性根据rowid顺序地,批量地读取记录,从而提升数据库的整体性能。在MySQL中默认关闭的,如果需要开启:

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

图片 3

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

其执行计划如下:

相关文章

No Comments, Be The First!
近期评论
    功能
    网站地图xml地图