Post Jobs

澳门新葡亰平台游戏查询优化之,MySql联接算法

澳门新葡亰平台游戏 2

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

网站地图xml地图