MySQL的几种表关联算法

2021-08-22 03:51:23

一、Multi-Range Read（MRR）

1、MRR优化原理

1）在没有使用MRR时，MySQL处理思路的伪代码

#SQL
select * from tb  where key_column=xx ;

#伪代码
for each row r in R do
    if r satisfy the where condition
        then output the tuple <r>

#处理流程        
1.根据索引过滤，获取到满足条件的记录的结果集<r>
2.遍历结果集通过主键进行回表,此时为离散扫描，返回客户端需要的字段信息

2）MRR算法实现伪代码处理流程

#SQL
select * from tb where key_column=xx ;

#伪代码
for each row r in R do
    if r satisfy the where condition
        then output the tuple <r> order by rowid


#处理流程
1.根据索引过滤获取到满足条件的记录<r>
2.将满足条件的记录放至read_rnd_buffer_size，并根据rowid进行排序，得到一个有序的结果集<r> order by rowid
3.遍历结果集通过主键进行回表查询，此时为顺序扫描，返回客户端满足条件的记录

2、MRR的特点

1）MRR算法主要是针对基于二级索引的过滤查询的优化，若过滤条件无索引则进行全表扫描。

2）MRR的特点就是将通过索引获取到满足条件的结果集(二级索引，主键索引)按照主键索引进行排序，将随机IO转换为顺序IO，从而再后续回表查询时带来性能上的提升。

3、MRR参数控制

mysql> show variables like 'optimizer_switch'\G

mrr=on                       //mrr优化，默认打开
mrr_cost_based=on            //mrr基于代价评估是否使用mrr算法，默认打开。MySQL优化器CBO一般会认为mrr资源消耗较大而放弃使用mrr，若需要使用mrr，可以将该参数打开。

mysql> set optimizer_switch='mrr=on,mrr_cost_based=off';   //开启mrr

4、示例

root@mysql57 15:39:  [db2]> explain select * from sbtest1 where k<10000 ;
+----+-------------+---------+------------+-------+---------------+-------+---------+------+------+----------+-----------------------+
| id | select_type | table   | partitions | type  | possible_keys | key   | key_len | ref  | rows | filtered | Extra                 |
+----+-------------+---------+------------+-------+---------------+-------+---------+------+------+----------+-----------------------+
|  1 | SIMPLE      | sbtest1 | NULL       | range | idx_k         | idx_k | 4       | NULL |  194 |   100.00 | Using index condition |
+----+-------------+---------+------------+-------+---------------+-------+---------+------+------+----------+-----------------------+
1 row in set, 1 warning (0.00 sec)

root@mysql57 15:39:  [db2]> set session optimizer_switch='mrr=on,mrr_cost_based=off';
Query OK, 0 rows affected (0.00 sec)

root@mysql57 15:39:  [db2]> explain select * from sbtest1 where k<10000 ;
+----+-------------+---------+------------+-------+---------------+-------+---------+------+------+----------+----------------------------------+
| id | select_type | table   | partitions | type  | possible_keys | key   | key_len | ref  | rows | filtered | Extra                            |
+----+-------------+---------+------------+-------+---------------+-------+---------+------+------+----------+----------------------------------+
|  1 | SIMPLE      | sbtest1 | NULL       | range | idx_k         | idx_k | 4       | NULL |  194 |   100.00 | Using index condition; Using MRR |
+----+-------------+---------+------------+-------+---------------+-------+---------+------+------+----------+----------------------------------+
1 row in set, 1 warning (0.00 sec)

二、Simple Nested-Loop Join（SNLJ）

1、SNLJ原理

1）伪代码

##SQL
select * from tb_r join tb_s on tb_r.r=tb_s.s 

##伪代码
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>

2）处理流程

1.遍历驱动表满足条件的所有记录
2.对于驱动表的每一行记录，对被驱动表进行遍历，获取到满足join条件的所有记录<r,s>
3.根据满足join条件的结果集，通过主键回表扫描，获取需要字段

2、SNLJ特点

1）该算法下SQL执行资源消耗最大，对于扫描次数来讲，驱动表扫描1次，被驱动表扫描次数取决于驱动表记录数（对于驱动表中每行记录都要遍历被驱动表一次）；对于SQL扫描记录数来讲，SQL执行扫描行数 = 驱动表行数 + 驱动表记录数 * 被驱动表记录数（笛卡尔积）

2）该算法主要是针对被驱动表关联字段无索引的情况，但是MySQL对该情况做了优化，利用join buffer并通过BNL算法减少对被驱动表的扫描次数

3、示例

##手动关闭BNL，数据库会使用SNLJ算法
root@mysql57 15:55:  [db2]> set session optimizer_switch='block_nested_loop=off';
Query OK, 0 rows affected (0.00 sec)

root@mysql57 15:55:  [db2]> explain select * from sbtest1 r join sbtest2 s on r.k=s.k;
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | r     | NULL       | ALL  | NULL          | NULL | NULL    | NULL |  100 |   100.00 | NULL        |
|  1 | SIMPLE      | s     | NULL       | ALL  | NULL          | NULL | NULL    | NULL |  200 |    10.00 | Using where |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
2 rows in set, 1 warning (0.00 sec)

##可以看到SQL扫描记录数=100+100*200=20100
# Time: 2020-04-14T16:02:13.707953+08:00
# User@Host: root[root] @ localhost []  Id:    24
# Query_time: 0.007069  Lock_time: 0.000140 Rows_sent: 47  Rows_examined: 20100
SET timestamp=1586851333;
select * from sbtest1 r join sbtest2 s on r.k=s.k;

三、Index Nested-Loop Join

1、INLJ原理

1）伪代码实现

##SQL
select * from tb_r join tb_s on tb_r.r=tb_s.s 

##伪代码
for each row r in R do
    lookupr in S index
    if found s == r
    then output the tuple <r,s>

2）处理流程

1.遍历满足过滤条件的驱动表中所有的记录
2.对于驱动表中每一条记录，通过索引进行关联查询，找到所有满足join条件的记录<r,s>
3.遍历结果集，通过主键回表扫描，获取需要的字段信息

2、INLJ特点

1）该算法主要针对被驱动表关联列有索引的情况

2）该算法基本上是MySQL在进行表关联时使用最多的算法，对SQL的扫描数据来讲，驱动表扫描次数为1，被驱动表扫描次数为0；对于SQL的扫描记录数来讲，SQL执行扫描行数 = 驱动表记录数 + 驱动表的记录 * 索引关联满足条件记录数

3、示例

##对于驱动表关联字段有索引的情况，默认使用IBLJ算法
root@mysql57 16:04:  [db2]> explain select * from sbtest1 r join sbtest2 s on r.k=s.k;
+----+-------------+-------+------------+------+---------------+-------+---------+---------+------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key   | key_len | ref     | rows | filtered | Extra |
+----+-------------+-------+------------+------+---------------+-------+---------+---------+------+----------+-------+
|  1 | SIMPLE      | r     | NULL       | ALL  | NULL          | NULL  | NULL    | NULL    |  100 |   100.00 | NULL  |
|  1 | SIMPLE      | s     | NULL       | ref  | idx_k         | idx_k | 4       | db2.r.k |    1 |   100.00 | NULL  |
+----+-------------+-------+------------+------+---------------+-------+---------+---------+------+----------+-------+
2 rows in set, 1 warning (0.00 sec)

##可以看到该算法下SQL扫描记录数=100+47(满足join条件记录数)
# Time: 2020-04-14T16:05:29.890558+08:00
# User@Host: root[root] @ localhost []  Id:    24
# Query_time: 0.000714  Lock_time: 0.000144 Rows_sent: 47  Rows_examined: 147
SET timestamp=1586851529;
select * from sbtest1 r join sbtest2 s on r.k=s.k;

四、Block Nested-Loop Join（BNL）

1、BNL原理

1）伪代码

##SQL
select * from tb_r join tb_s on tb_r.r=tb_s.s 

##伪代码
for each tuple r in R do
    store used columns as p from R in join buffer
    for each tuple s in S do
        if p and s satisfy the join condition
            then output the tuple <p,s>

2）处理流程

1.遍历满足过滤条件的驱动表中所有的记录(SQL查询的所有字段)，并放入至join buffer
2.若所有驱动表满足条件记录放入join buffer，遍历被驱动表所有记录，获取满足join条件的记录结果集
3.若join buffer无法一次性存储全部驱动表记录，可分批读取记录至join buff，重复2步骤

2、BNL特点

1）BNL主要是针对被驱动表关联字段无索引时的优化，如果我们在执行计划中看到“Using join buffer (Block Nested Loop)”说明被驱动表表表关联字段缺少索引或索引失效无法有效利用索引。

2）该算法是对SNLJ算法的优化，并且可将该算法BNL提升至INLJ进行优化。对SQL的扫描数据来讲，驱动表扫描次数为1，被驱动表扫描次数为驱动表记录大小 / join_buffer_size ；对于SQL的扫描记录数来讲，SQL执行扫描行数 = 驱动表记录数 + (驱动表记录/join_buffer_size) * 被驱动表记录数

3）在一定的程度上，提高join_buffer_size的大小是可以提高使用BNL算法SQL的执行效率，但是join_buffer_size是会话连接上去就会提前进行分配的，若SQL为N个表join，那其分配的join buffer大小为 join_buffer_size * (N-1)，所以生产环境中我们不可对该参数设置过大。

3、相关参数

mysql> show variables like 'optimizer_switch'\G
block_nested_loop=on                       //BNL优化，默认打开
mysql> set optimizer_switch='block_nested_loop=on';   //开启BNL

4、示例

##打开BNL算法
root@mysql57 16:07:  [db2]> set session optimizer_switch='block_nested_loop=on';
Query OK, 0 rows affected (0.00 sec)

##可以看到执行计划中使用了BNL算法
root@mysql57 16:07:  [db2]> explain select * from sbtest1 r join sbtest2 s on r.k=s.k;
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+----------------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                              |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+----------------------------------------------------+
|  1 | SIMPLE      | r     | NULL       | ALL  | NULL          | NULL | NULL    | NULL |  100 |   100.00 | NULL                                               |
|  1 | SIMPLE      | s     | NULL       | ALL  | NULL          | NULL | NULL    | NULL |  200 |    10.00 | Using where; Using join buffer (Block Nested Loop) |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+----------------------------------------------------+
2 rows in set, 1 warning (0.00 sec)

##该算法下SQL扫描记录数=100+1*200
# Time: 2020-04-14T16:08:33.345173+08:00
# User@Host: root[root] @ localhost []  Id:    24
# Query_time: 0.002777  Lock_time: 0.000144 Rows_sent: 47  Rows_examined: 300
SET timestamp=1586851713;
select * from sbtest1 r join sbtest2 s on r.k=s.k;


##手动调整join_buffer_size的大小
root@mysql57 16:08:  [db2]> show variables like '%join_buffer_size%';
+------------------+--------+
| Variable_name    | Value  |
+------------------+--------+
| join_buffer_size | 262144 |
+------------------+--------+
1 row in set (0.00 sec)

root@mysql57 16:11:  [db2]> set session join_buffer_size=1024;
Query OK, 0 rows affected (0.00 sec)

##缩小join_buffer_size大小后，可以发现SQL扫描记录数上涨,10100=100+5*200
# Time: 2020-04-14T16:11:33.191980+08:00
# User@Host: root[root] @ localhost []  Id:    24
# Query_time: 0.005209  Lock_time: 0.000148 Rows_sent: 47  Rows_examined: 10100
SET timestamp=1586851893;
select * from sbtest1 r join sbtest2 s on r.k=s.k;

五、Batched Key Access Join（BKA）

1、BKA原理

1）伪代码

for each row r in R do
    lookupr in S index
    if found s == r
    then get the tuple <r,s>
    use mrr interface output the <r,s> order by rowid

2）处理流程

1.遍历满足过滤条件的驱动表中所有的记录
2.对于驱动表中每一条记录，通过索引进行关联查询，找到所有满足join条件的记录<r,s>
3.通过mrr结果对以上结果集的rowid进行排序
4.遍历结果集，通过主键回表扫描（顺序读），获取需要的字段信息

2、BKA特点

1）BKA算法是对INLJ算法的一个优化，其区别就是在获取到满足join条件记录的结果集后，通过MRR接口对rowid进行排序，以保证后续的回表操作为顺序读来提高

2）BKA算法算法默认关闭。BKA算法的优化基于MRR，所以若需要打开BKA算法，需要打开MRR并关闭mrr_cost_based。

3、相关参数

mysql> show variables like 'optimizer_switch'\G
batched_key_access=off                       //BKA优化，默认关闭
mysql> set optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';   //开启BKA

4、示例

root@mysql57 16:19:  [db2]> set session optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';
Query OK, 0 rows affected (0.00 sec)

root@mysql57 16:19:  [db2]> explain select * from sbtest1 r join sbtest2 s on r.k=s.k;
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+----------------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                              |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+----------------------------------------------------+
|  1 | SIMPLE      | r     | NULL       | ALL  | NULL          | NULL | NULL    | NULL |  100 |   100.00 | NULL                                               |
|  1 | SIMPLE      | s     | NULL       | ALL  | NULL          | NULL | NULL    | NULL |  200 |    10.00 | Using where; Using join buffer (Block Nested Loop) |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+----------------------------------------------------+
2 rows in set, 1 warning (0.00 sec)

root@mysql57 16:20:  [db2]> alter table sbtest2 add index idx_k(k);
Query OK, 0 rows affected (0.05 sec)
Records: 0  Duplicates: 0  Warnings: 0

root@mysql57 16:20:  [db2]> explain select * from sbtest1 r join sbtest2 s on r.k=s.k;
+----+-------------+-------+------------+------+---------------+-------+---------+---------+------+----------+----------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key   | key_len | ref     | rows | filtered | Extra                                  |
+----+-------------+-------+------------+------+---------------+-------+---------+---------+------+----------+----------------------------------------+
|  1 | SIMPLE      | r     | NULL       | ALL  | NULL          | NULL  | NULL    | NULL    |  100 |   100.00 | NULL                                   |
|  1 | SIMPLE      | s     | NULL       | ref  | idx_k         | idx_k | 4       | db2.r.k |    1 |   100.00 | Using join buffer (Batched Key Access) |
+----+-------------+-------+------------+------+---------------+-------+---------+---------+------+----------+----------------------------------------+
2 rows in set, 1 warning (0.00 sec)


##BKA算法是对INLJ算法的优化，其SQL扫描记录数只是驱动表的记录数？
# Time: 2020-04-14T16:20:49.212383+08:00
# User@Host: root[root] @ localhost []  Id:    24
# Query_time: 0.000680  Lock_time: 0.000145 Rows_sent: 47  Rows_examined: 100
SET timestamp=1586852449;
select * from sbtest1 r join sbtest2 s on r.k=s.k;

六、Hashjoin

Hashjoin从MySQL8.0.18后才开始支持，M一SQL 8.0.18之前只支持NLP相关的算法。Hashjoin主要是针对表关联字段无有效索引可利用时进行的一种优化算法。

1、In-Memory Join（CHJ）原理及特点

1）构建阶段，遍历驱动表，以join条件为key，查询需要的列作为value创建hash表。

2）探测阶段，根据驱动表构建出来的hash表，对被驱动表的关联列进行遍历，并计算关联列的hash值判断是否满足join条件，获取到满足条件的所有记录的结果集

3）CHJ主要适用于被驱动表关联字段无索引，切驱动表可一次性读取到join_buffer_size的情况，该情况下只需要对驱动表扫描1次，被驱动表扫描1次。

2、On-Disk Hash Join原理及特点

1）如果驱动表的记录无法一次性存储到join_buffer_size中，构建阶段会首先利用hash算将驱动表进行分区，并产生临时分片写到磁盘上；

2）在探测阶段，对被驱动表使用同样的hash算法进行分区，保证相同的分区中，驱动表和被驱动表满足表关联的等值条件的情况下，其hash算法将其分配到相同的分区中。

3）On-Disk Hash Join是基于CHJ，对join_buffer_size无法满足一次性存储所有的驱动表记录情况下的优化

4）当驱动表记录超过内存时，MySQL通过hash算法对其进行分区处理，若分区后部分分区数据仍然超出join_buffer_size的大小，则MySQL会分批次读取该分区的记录，每次处理完后清理hash表，重复以上操作直到处理完所有分区数据。

5）该算法下驱动表扫描次数为1，被驱动表扫描次数与hash算法分区个数以及每个分区下驱动表记录大小/join_buffer_size个数相关，驱动表数据越大其被驱动表扫描次数越多

3、示例

## MySQL 8.0.19默认开启hashjoin，可以使用explain format=tree查看SQL执行计划
root@mysql57 17:16:  [db2]> explain format=tree select * from sbtest1 r join sbtest2 s on r.k=s.k;
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                                                                                               |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Inner hash join (s.k = r.k)  (cost=9661.47 rows=2000)
    -> Table scan on s  (cost=76.21 rows=200)
    -> Hash
        -> Table scan on r  (cost=42.50 rows=100)
 |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)


##可以看到hashjoin算法下，SQL扫描记录数为100+1*200，该算法相对于SNLJ和BNL都有所提高
# Time: 2020-04-14T17:16:34.857120+08:00
# User@Host: root[root] @ localhost []  Id:    17
# Query_time: 0.001235  Lock_time: 0.000206 Rows_sent: 47  Rows_examined: 300
SET timestamp=1586855794;
select * from sbtest1 r join sbtest2 s on r.k=s.k;

文章参考：

姜承尧大佬公众号：https://mp.weixin.qq.com/s?__biz=MjM5MjIxNDA4NA==&mid=205923864&idx=1&sn=63b97a02def11c3e4fceb67d25c79628&scene=21#wechat_redirect
【mysql】关于ICP、MRR、BKA等特性：https://www.cnblogs.com/chenpingzhao/p/6720531.html
MySQL8.0 新特性 Hash Join：https://www.cnblogs.com/cchust/p/11961851.html

码农公寓

一、Multi-Range Read（MRR）

1、MRR优化原理

2、MRR的特点

3、MRR参数控制

4、示例

二、Simple Nested-Loop Join（SNLJ）

1、SNLJ原理

2、SNLJ特点

3、示例

三、Index Nested-Loop Join

1、INLJ原理

2、INLJ特点

3、示例

四、Block Nested-Loop Join（BNL）

1、BNL原理

2、BNL特点

3、相关参数

4、示例

五、Batched Key Access Join（BKA）

1、BKA原理

2、BKA特点

3、相关参数

4、示例

六、Hashjoin

1、In-Memory Join（CHJ）原理及特点

2、On-Disk Hash Join原理及特点

3、示例

相关文章