一背景

在MySQL中我们为了实现业务逻辑会进行多表关联查询.也就是我们常说的各种join.那么我们怎么使用join才会获得好的执行效果呢?

二 Nested-Loop Join 又称SNL

什么是SNL呢?借用官网上的一段伪代码:

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

比如:

select a.* from test a join test1 b on a.c=b.c;
其中test表没有索引所以会全表扫描,test1表的c列有索引.所以test1表将会使用索引.

那么SNL的执行逻辑是什么样的呢?

对test表的c列进行全表扫描然一个一个的去test1表(test1使用索引)获取对应的值.然后再回表test获取所有记录.然后返回给客户端.

执行计划查看:

    "nested_loop": [
      {
        "table": {
          "table_name": "a",   --test表
          "access_type": "ALL",   --可以看到test表进行了全表扫描
          "rows_examined_per_scan": 986400,
          "rows_produced_per_join": 986400,
          "filtered": "100.00",
          "cost_info": {
            "read_cost": "13741.00",
            "eval_cost": "197280.00",
            "prefix_cost": "211021.00",
            "data_read_per_join": "180M"
          },
          "used_columns": [
            "id",
            "k",
            "c",
            "pad"
          ]
        }
      },
      {
        "table": {
          "table_name": "b",    --test1表
          "access_type": "ref",  --使用了非唯一索引的等值查询
          "possible_keys": [
            "idx_c"
          ],
          "key": "idx_c",
          "used_key_parts": [
            "c"
          ],
          "key_length": "120",
          "ref": [
            "increment.a.c"
          ],
          "rows_examined_per_scan": 1,
          "rows_produced_per_join": 986400,
          "filtered": "100.00",
          "using_index": true,
          "cost_info": {
            "read_cost": "986400.00",
            "eval_cost": "197280.00",
            "prefix_cost": "1394701.00",
            "data_read_per_join": "180M"
          },
          "used_columns": [
            "c"

通过对SNL的实现逻辑及执行计划分析发现:

驱动表test越小.那么执行效率就越高

三 Block Nested-Loop Join 又称BNL

伪代码如下:

for block row in a matching range {
?for each row in b {
??a.x = b.y ，send to client
?}
}

语句还是:

select a.* from test a join test1 b on a.c=b.c;
现在不同的是,test表和test1表的相关列都没有索引

BNL的实现逻辑:

批量的从test表取数据放入join buffer如果一次性能放到join buffer则全部放入,然后一次性匹配test1中满足条件的c列,然后返回客户端.如果一次性不能把test中的数据全部放入join buffer则循环上边的流程.直到全部全完为止.

执行计划分析

  "nested_loop": [
      {
        "table": {
          "table_name": "b",    --test1表
          "access_type": "ALL",  --可以看到是全表扫描
          "rows_examined_per_scan": 9680,
          "rows_produced_per_join": 9680,
          "filtered": "100.00",
          "cost_info": {
            "read_cost": "161.00",
            "eval_cost": "1936.00",
            "prefix_cost": "2097.00",
            "data_read_per_join": "1M"
          },
          "used_columns": [
            "c"     --可以看到只使用了c列和join buffer中的test进行对比
          ]
        }
      },
      {
        "table": {
          "table_name": "a",   --test表
          "access_type": "ALL",   --也是全表扫描
          "rows_examined_per_scan": 986400,
          "rows_produced_per_join": 954835214,
          "filtered": "10.00",
          "using_join_buffer": "Block Nested Loop",    --可以看到使用了BNL
          "cost_info": {
            "read_cost": "21352.06",
            "eval_cost": "190967042.85",
            "prefix_cost": "1909693849.06",
            "data_read_per_join": "170G"
          },
          "used_columns": [
            "id",
            "k",
            "c",
            "pad"
          ],
          "attached_condition": "(`increment`.`a`.`c` = `increment`.`b`.`c`)"

同样.可以看到驱动表test越小的话.效率就会越高.

注意:从MySQL的8020版本开始.将废弃BNL.因为从MySQL8018版本开始就加入了hash join默认都会使用hash join

同样.我们在此看一下mysql8020版本的hash join的执行计划

    "nested_loop": [
      {
        "table": {
          "table_name": "b",
          "access_type": "ALL",
          "rows_examined_per_scan": 1000,
          "rows_produced_per_join": 1000,
          "filtered": "100.00",
          "cost_info": {
            "read_cost": "0.25",
            "eval_cost": "100.00",
            "prefix_cost": "100.25",
            "data_read_per_join": "718K"
          },
          "used_columns": [
            "c"
          ]
        }
      },
      {
        "table": {
          "table_name": "a",
          "access_type": "ALL",
          "rows_examined_per_scan": 9936,
          "rows_produced_per_join": 993600,
          "filtered": "10.00",
          "using_join_buffer": "hash join",   --可以看到这里使用了hash join
          "cost_info": {
            "read_cost": "113.95",
            "eval_cost": "99360.00",
            "prefix_cost": "993814.20",
            "data_read_per_join": "697M"
          },
          "used_columns": [
            "id",
            "k",
            "c",
            "pad"
          ],
          "attached_condition": "(`world`.`a`.`c` = `world`.`b`.`c`)"

同时在上边的BNL和hash join我展示的两个例子中.不知道大家注意到没有.优化器默认选择了表数据量小的表作为了驱动表.上边的BNL展示中的test表是100万的数据,test1是1万的数据.hash join展示使用的test表是1万数据.test1是1千的数据量.

最后.不管哪种算法.都最好使用驱动表结果集小的作为驱动表.优化器也会自己去选择.

三优化算法MRR(Multi-Range Read Optimization)

在此提到MRR算法是为了下边的BKA算法提供铺垫.大家看看MRR的实现原理就好了.不要单独开启MRR.因为实际压测显示单独开启MRR的效果不理想.

MRR是为了实现什么呢?

实验环境准备:

mysql> desc test1;
+-------+-----------+------+-----+---------+----------------+
| Field | Type      | Null | Key | Default | Extra          |
+-------+-----------+------+-----+---------+----------------+
| id    | int       | NO   | PRI | NULL    | auto_increment |
| k     | int       | NO   | MUL | 0       |                |
| c     | char(120) | NO   |     |         |                |
| pad   | char(60)  | NO   |     |         |                |
+-------+-----------+------+-----+---------+----------------+
4 rows in set (0.00 sec)

mysql> show index from test1;
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| test1 |          0 | PRIMARY  |            1 | id          | A         |        1000 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| test1 |          1 | idx_k    |            1 | k           | A         |         311 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
2 rows in set (0.01 sec)

执行查询

在没有开启MRR的情况下.这条语句的执行逻辑是这样的

也就是说会范围扫描索引之后.会回表进行随机的磁盘读.

接下来我们开启MRR

mysql> set optimizer_switch="mrr_cost_based=off";

接下来再执行上边的查询查看执行计划:

在这里我们看到使用到了MRR.那么我们看看使用了MRR之后的执行逻辑是什么样的

在这里我们看到开启MRR之后.索引范围扫描获取到的数据先存储到buffer中进行排序.然后使用主键顺序的回表取数据.减少了随机读的时间浪费.

四 Batched Key Access Joins(BKA)算法

BKA算法可以被inner join和outer join及semi join使用.BKA场景和SNL算法的应用条件差不多.就是test1表对应列有索引.不同的是BKA会使用到MRR算法.同时还会使用到join buffer

开启BKA

mysql> SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

环境准备:

执行查询并查看执行计划:

 "nested_loop": [
      {
        "table": {
          "table_name": "test",
          "access_type": "ALL",
          "rows_examined_per_scan": 986400,
          "rows_produced_per_join": 986400,
          "filtered": "100.00",
          "cost_info": {
            "read_cost": "13741.00",
            "eval_cost": "197280.00",
            "prefix_cost": "211021.00",
            "data_read_per_join": "180M"
          },
          "used_columns": [
            "id",
            "k",
            "c",
            "pad"
          ]
        }
      },
      {
        "table": {
          "table_name": "test1",
          "access_type": "ref",
          "possible_keys": [
            "idx_c"
          ],
          "key": "idx_c",
          "used_key_parts": [
            "c"
          ],
          "key_length": "120",
          "ref": [
            "increment.test.c"
          ],
          "rows_examined_per_scan": 1,
          "rows_produced_per_join": 986400,
          "filtered": "100.00",
          "using_join_buffer": "Batched Key Access",   --在这里可以看到.使用到了BKA和join buffer
          "cost_info": {
            "read_cost": "986400.00",
            "eval_cost": "197280.00",
            "prefix_cost": "1394701.00",
            "data_read_per_join": "180M"
          },
          "used_columns": [
            "id",
            "k",
            "c",
            "pad"

那么BKA的执行逻辑是什么样的呢?

在这里我们可以和前边的SNL的图对比发现.BKA先从test表取出数据和test1中的的c列对比取出并集.然后在join buffer中排序.再一次性去test中顺序取出数据.这里使用到了MRR的排序算法.

五总结

本篇文章主要介绍了MySQL中的join算法.

MySQL中关于join的算法详解

一背景

二 Nested-Loop Join 又称SNL

三 Block Nested-Loop Join 又称BNL

三优化算法MRR(Multi-Range Read Optimization)

四 Batched Key Access Joins(BKA)算法

五总结

相关推荐

程序员的开源月刊《HelloGitHub》第 71 期

如何将AI助手接入微信（打开ai手机助手）

SparkSQL——DataFrame的创建与使用

使用过 Redis 分布式锁么，它是什么回事?

VUE循环语句的使用(v-for)（vuefor循环的key）

HiveOs系统教程最细手把手教学（hiveos启动）

Python rembg 库去除图片背景

HIVE SQL基础语法（hive-sql）

Spring Boot 概述（spring boot干嘛的）

《循环(for/while)》（循环while语句）

MySQL中关于join的算法详解

一 背景

二 Nested-Loop Join 又称SNL

三 Block Nested-Loop Join 又称BNL

三 优化算法MRR(Multi-Range Read Optimization)

四 Batched Key Access Joins(BKA)算法

五 总结

相关推荐

程序员的开源月刊《HelloGitHub》第 71 期

如何将AI助手接入微信（打开ai手机助手）

SparkSQL——DataFrame的创建与使用

使用过 Redis 分布式锁么，它是什么回事?

VUE循环语句的使用(v-for)（vuefor循环的key）

HiveOs系统教程最细手把手教学（hiveos启动）

Python rembg 库去除图片背景

HIVE SQL基础语法（hive-sql）

Spring Boot 概述（spring boot干嘛的）

《循环(for/while)》（循环while语句）

一背景

三优化算法MRR(Multi-Range Read Optimization)

五总结