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数据库用于拍卖联接的大体策略。在MySql
5.伍版本仅支持Nested-Loops Join算法,如若联接表上有索引时,Nested-Loops
Join是那些神速的算法。假使有目录时间复杂度为O(N),若未有索引,则可身为最坏的意况,时间复杂度为O(N²)。MySql依据区别的利用处境,协助三种Nested-Loops
Join算法,一种是Simple Nested-Loops Join算法,别的1种是Block
Nested-Loops Join算法。

Nested Loop Join算法

将外层表的结果集作为循环的底子数据,然后循环从该结果集每一次一条获取数据作为下3个表的过滤条件去询问数据,然后合并结果。倘使有多个表join,那么应该将前方的表的结果集作为循环数据,取结果集中的每一行再到下1个表中继续实行巡回相配,获取结果集并赶回给客户端。

伪代码如下

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算法3遍只好将1行数据传入内部存款和储蓄器循环,所以外层循环结果集有多少行,那么内部存储器循环就要执行稍微次。

###Simple Nested-Loops Join算法
从一张表中年老年是读取一条记下,然后将记录与嵌套表中的记录举办相比。算法如下:

Block Nested-Loop算法

MySQL
BNL算法原本只补助内连接,今后已协理外连接半连接操作,包括嵌套外连接

BNL算法原理:将外层循环的行/结果集存入join
buffer,内部存款和储蓄器循环的每壹行数据与壹切buffer中的记录做相比较,能够减掉内层循环的围观次数

举个简单的事例:外层循环结果集有一千行数据,使用NLJ算法供给扫描内层表一千次,但固然运用BNL算法,则先取出外层表结果集的十0行存放到join
buffer,
然后用内层表的每1行数据去和那十0行结果集做比较,可以3遍性与拾0行数据开展相比,那样内层表其实只需求循环一千/100=13遍,裁减了9/十。

伪代码如下

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经t壹, t2插手join的列长度只和为s, c为两岸组合数, 那么t3表被扫描的次数为

(S * C)/join_buffer_size + 1

 

扫描t三的次数随着join_buffer_size的增大而缩减, 直到join
buffer能够容纳全数的t壹, t贰结缘, 再增大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表的时候,使用3个join
buffer来收集第壹个操作对象生成的相关列值。BKA创设好key后,批量传给引擎层做索引查找。key是由此M汉兰达Escort接口提交给引擎的,那样,M福特Explorer牧马人使得查询更有效能。

比方外部表扫描的是主键,那么表中的记录走访都以相比平稳的,不过若是连接的列是非主键索引,那么对于表中著录的拜访也许正是尤其离散的。因此对于非主键索引的连通,Batched
Key Access
Join算法将能大幅度进步SQL的实施功用。BKA算法匡助内延续,外接连和半连接操作,包蕴嵌套外接连。

Batched Key Access Join算法的做事步骤如下:

  • 一) 将表面表中相关的列放入Join Buffer中。

  • 2) 批量的将Key(索引键值)发送到Multi-Range Read(M卡宴大切诺基)接口。

  • 3) Multi-Range
    Read(M奥德赛哈弗)通过吸收的Key,依照其对应的ROWID实行排序,然后再拓展数量的读取操作。

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

Batched Key Access Join算法的本来面目上的话依旧Simple Nested-Loops
Join算法,其产生的口径为内部表上有索引,并且该索引为非主键,并且连接必要拜访内部表主键上的目录。那时Batched
Key Access Join算法会调用Multi-Range
Read(M奥德赛君越)接口,批量的开始展览索引键的相称和主键索引上获取数据的操作,以此来增长联接的进行成效,因为读取数据是以一壹磁盘IO而不是任意磁盘IO进行的。

使用BKA时,join_buffer_size的值定义了对存款和储蓄引擎的每一种请求中批量密钥的大小。缓冲区越大,对连日操作的左边表的各种访问就越来越多,这足以显着进步质量。

要使用BKA,必须将optimizer_switch系统变量的batched_key_access标明设置为on。
BKA使用MPRADO奥迪Q3,因而mrr标志也亟须打开。最近,MRXC90的老本预计过于悲观。由此,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)

 

即便在两张表Wrangler和S上进展连接的列都不含有索引,算法的扫视次数为:途胜+哈弗xS,扫描耗费为O(奥迪Q3xS)。

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

 

假若t壹,t二和t三3张表执行INNE牧马人 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>

对此联接的列含有索引的情景,外部表的每条记下不再必要扫描整张内部表,只供给扫描内部表上的目录即可取得联接的论断结果。

在INNEMurano JOIN中,两张联接表的逐条是足以变换的,根据前边描述的Simple
Nested-Loops
Join算法,优化器在形似景况下延续挑三拣四将接入列含有索引的表作为内表。假若两张表Haval和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+树的万丈,别的1般都以表的记录数。

###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语句:

网站地图xml地图