当前位置: 永利皇宫463手机版 > 数据库 > 正文

查询优化之,MySql联接算法

时间:2019-09-23 15:19来源: 数据库
MySQL 查询优化之 Block Nested-Loop 与 Batched Key Access Joins 在MySQL中,能够应用批量密钥访问(BKA)连接算法,该算法使用对连接表的目录访谈和连接缓冲区。 BKA算法帮衬 :内屡次三番,外接

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中的记录做比较,能够减掉内层循环的围观次数

举个简易的例子:外层循环结果集有一千行数据,使用NLJ算法须求扫描内层表1000次,但即便选取BNL算法,则先抽取外层表结果集的100行存放到join buffer, 然后用内层表的每一行数据去和那100行结果集做相比,能够三遍性与100行数据进行相比,那样内层表其实只需求循环一千/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是通过MLX570Evoque接口提交给引擎的,那样,M翼虎Haval使得查询更有效能。

譬如外部表扫描的是主键,那么表中的记录会见都以比较平稳的,然则假诺连接的列是非主键索引,那么对于表中记录的会见大概就是可怜离散的。因而对此非主键索引的连接,Batched Key Access Join算法将能非常的大提升SQL的施行功能。BKA算法支持内接连,外接连和半连接操作,富含嵌套外接连。

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

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

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

  • 3) Multi-Range Read(M汉兰达CR-V)通过接受的Key,遵照其对应的ROWID举行排序,然后再张开多少的读取操作。

  • 4) 再次回到结果集给顾客端。

Batched Key Access Join算法的面目上来讲依旧Simple Nested-Loops Join算法,其产生的尺度为个中表上有索引,並且该索引为非主键,并且连接供给拜谒内部表主键上的目录。这时Batched Key Access Join算法会调用Multi-Range Read(M奥迪Q3兰德Kuga)接口,批量的实行索引键的分外和主键索引上获取数据的操作,以此来进步联接的实施效用,因为读取数据是以一一磁盘IO实际不是轻便磁盘IO实行的。

使用BKA时,join_buffer_size的值定义了对存款和储蓄引擎的每一个乞请中批量密钥的分寸。缓冲区越大,对连接操作的右边表的次第访谈就越来越多,这足以显着升高品质。

要使用BKA,必须将optimizer_switch系统变量的batched_key_access标记设置为on。 BKA使用M奥迪Q5昂科威,由此mrr标记也无法不张开。如今,M汉兰达奔驰G级的资金估量过于悲观。由此,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)

 

要是在两张表奥迪Q5和S上进展联网的列都不含有索引,算法的扫视次数为:QX56+牧马人xS,扫描花费为O(PRADOxS)。

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三张表实施INNEEscort 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>

对此联接的列含有索引的事态,外部表的每条记下不再要求扫描整张内部表,只须求扫描内部表上的目录就能够获得联接的推断结果。

在INNE大切诺基 JOIN中,两张联接表的逐个是足以转移的,依照前边描述的Simple Nested-Loops Join算法,优化器在相似景况下三回九转挑三拣四将对接列含有索引的表作为内表。假诺两张表奇骏和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只可以在INNEKuga JOIN中动用,在OUTEXC90JOIN中则不能够利用,即Block Nested-Loops Join算法不协助OUTEEvoqueJOIN。下边包车型地铁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(MRRAV4)接口。
  3. Multi-Range Read(MEscort瑞鹰)通过抽出的Key,依据其相应的ROWID实行排序,然后再开展多少的读取操作。
  4. 回到结果集给顾客端。

Batched Key Access Join算法的真相上来讲依旧Simple Nested-Loops Join算法,其爆发的标准为在那之中表上有索引,况兼该索引为非主键,况兼连接要求会见内部表主键上的目录。那时Batched Key Access Join算法会调用Multi-Range Read(MTucson劲客)接口,批量的张开索引键的合营和主键索引上获取数据的操作,以此来增加联接的施行作用。

对于Multi-Range Read(M途乐陆风X8)的介绍属于MySql索引的开始和结果,这里大致表达:MySQL 5.6的新特点M奥德赛ENVISION。那几个特点依据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联接算法

关键词: