询问优化之,MySql联接算法

日期:2019-10-21编辑作者:计算机网络

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

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)

 

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>

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

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

Table   Join Type
t1      range
t2      ref
t3      ALL

如果使用了Simple Nested-Loops 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
    }
  }
}

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

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

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

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

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

其执行计划如下:

图片 2

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

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

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

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

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

  • 系统变量Join_buffer_size决定了Join Buffer的大小。
  • Join Buffer可被用于联接是ALL、index、和range的类型。
  • 每次联接使用一个Join Buffer,因此多表的联接可以使用多个Join Buffer。
  • Join Buffer在联接发生之前进行分配,在SQL语句执行完后进行释放。
  • Join Buffer只存储要进行查询操作的相关列数据,而不是整行的记录。

对于上面提到的三个表进行联接操作,如果使用Join Buffer,则算法的伪代码如下:

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

举一个例子,把driver表的_create_date列和user表的create_date列的索引删除,进行联接查询,执行下面的SQL语句:

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

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

图片 3

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

图片 4

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

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

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

图片 5

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

图片 6

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

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

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算法的工作步骤如下:

  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)接口,批量的进行索引键的匹配和主键索引上获取数据的操作,以此来提高联接的执行效率。

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

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查询有更好的了解。 ###参考 有不对的地方希望大家多交流,谢谢。

《MySql技术内幕:SQL编程》

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

本文由今晚最快开奖现场直播发布于计算机网络,转载请注明出处:询问优化之,MySql联接算法

关键词:

SqlServer注意事项总结,事务隔离级别详解

本篇文章主要介绍SqlServer使用时的注意事项。 SQL 事务隔离级别 想成为一个高级程序员,数据库的使用是必须要会的...

详细>>

Sever数据常见难点,跨越服务器务器备份表

exec sp_configure 'show advanced options',1 reconfigure exec sp_configure 'Ad Hoc Distributed Queries',1 reconfigure SELECT * into T_System_Organizatio...

详细>>

处理上百万条的数据库如何提高处理查询速度,

**1、 对查询进行优化,应尽量制止全表扫描,首先应思量在where 及 order by 涉及的列上构建目录。  php 管理上百万条...

详细>>

计算两个日期之间的工作日数,获取指定日期为

转自:http://www.maomao365.com/?p=6771 /**//**//**//// summary ///总括多少个日子之间的办事日数,(星期6,星期日,不算工作日)...

详细>>