文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

一文详解MySQL—Join的使用优化

2023-04-21 10:45

关注

MySQL JOIN类型

MySQL支持多种JOIN类型,下面是每种JOIN类型的简要概述:

MySQL JOIN 算法

在了解完 MySQL JOIN类型概念之后,我们来了解 MySQL JOIN 算法,在之前的版本只支持Nested Loop Join这一种算法,在 MySQL 8.0.18之后支持 Hash Join算法。

Nested-Loop Join 算法

执行流程

假设两个表一个 user 用户表,一个 order 订单表,需要查询用户的所有订单信息,表结构如下:

CREATE TABLE `user` (
  `id` int(11) NOT NULL COMMENT '主键id',
  `name` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL COMMENT '用户名称',
  `age` int(255) DEFAULT NULL COMMENT '年龄',
  `user_code` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL COMMENT '用户编号',
  PRIMARY KEY (`id`),
  KEY `idx_user_code` (`user_code`) USING BTREE COMMENT '用户编号索引'
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='用户表';

CREATE TABLE `order` (
  `id` int(11) NOT NULL AUTO_INCREMENT COMMENT '主键id',
  `order_name` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL COMMENT '订单名称',
  `user_code` varchar(11) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL COMMENT '用户编号',
  PRIMARY KEY (`id`),
  KEY `idx_user_code` (`user_code`) USING BTREE COMMENT '用户编号索引'
) ENGINE=InnoDB AUTO_INCREMENT=10 DEFAULT CHARSET=utf8 COMMENT='订单表';

其中 user_code是连接字段,也是索引。SQL 如下:

mysql> SELECT
	u.`name`,
	u.user_code,
	o.order_name 
FROM
	`user` u
	JOIN `order` o ON u.user_code = o.user_code;
+------+-----------+------------+
| name | user_code | order_name |
+------+-----------+------------+
| 李   | 002       | 订单1      |
| 李   | 002       | 订单2      |
| 李   | 002       | 订单3      |
| 李   | 002       | 订单4      |
| 李   | 002       | 订单5      |
| 李   | 002       | 订单6      |
| 李   | 002       | 订单7      |
| 李   | 002       | 订单8      |
| 李   | 002       | 订单9      |
+------+-----------+------------+
9 rows in set (0.08 sec)

看一下这条语句的explain结果

一文详解MySQL—Join的使用优化

这个语句的执行流程如下:

工作原理

这个过程就跟我们写程序时的嵌套查询,一般称为Nested-Loop Join (NLJ),是一种最基本的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
    }
  }
}

时间复杂度分析

这个过程将会对每一行进行一次比较,因此它的时间复杂度为:O(m∗n)O(m*n)O(m∗n),其中 mn 分别是两个表的行数。

假设被驱动表的行数是M。 每次在被驱动表查一行数据, 要先搜索索引a, 再搜索主键索引。每次搜索一棵树近似复杂度是logMlog MlogM, 所以在被驱动表上查一行的时间复杂度是 2∗logM2*log M2∗logM。

假设驱动表的行数是N, 执行过程就要扫描驱动表N行, 然后对于每一行, 到被驱动表上匹配一次。因此整个执行过程, 近似复杂度是 N+N∗2∗logMN + N*2*log MN+N∗2∗logM。 N对扫描行数的影响更大, 因此应该让小表来做驱动表。对于大型数据集来说,它的性能会变得非常慢,因为它需要对一个表的每一行都扫描另一个表。

Block Nested-Loop Join 算法

执行流程

接下来, 我们删除掉索引,再看看被驱动表用不上索引的情况

ALTER TABLE `user` DROP INDEX `idx_user_code`;
EXPLAIN SELECT
	u.`name`,
	u.user_code,
	o.order_name 
FROM
	`user` u
	JOIN `order` o ON u.user_code = o.user_code

再看一下这条语句的explain结果,多了一个 Using join buffer (Block Nested Loop

一文详解MySQL—Join的使用优化

这个时候语句的执行流程如下:

工作原理

Join Buffer是一种内存缓存,并在查询完成后释放,它可以在执行时缓存Join的中间结果。join_buffer 的大小是由参数join_buffer_size设定的, 默认值是256k。

mysql> show variables like '%join_buffer_size%';
+------------------+---------+
| Variable_name    | Value   |
+------------------+---------+
| join_buffer_size | 1048576 |
+------------------+---------+
1 row in set (0.10 sec)

那如果Join Buffer中放不下表user的所有数据话会怎么处理呢? 策略很简单, 就是分段 ,每次清空join_buffer

for each row in t1 matching range {
    store used columns from t1 in join buffer
    ## 如果buffer满了
	if buffer is full {
      for each row in t2 {
        for each t1 combination in join buffer {
		  ## 如果行满足连接条件,则发送到客户端
          if row satisfies join conditions, send to client
        }
      }
	  ## 清空buffer
      empty join buffer
    }
 
}

if buffer is not empty {
  for each row in t2 {
    for each t1 combination in join buffer {
      if row satisfies join conditions, send to client
    }
  }
}

时间复杂度分析

可以看到,在这个过程中, 对表userorder都做了一次全表扫描。 因此它的时间复杂度为:O(M+N)O(M+N)O(M+N)。由于join_buffer是以无序数组的方式组织的, 因此对表order中的每一行, 都要做判断。假设小表的行数是N, 大表的行数是M, 那么在这个算法里:

Block Nested-Loop Join(BNL)是一种优化的NLJ算法,BNL 通过将一个表分成多个块(block),然后逐个块与另一个表进行Join操作,从而减少了不必要的重复扫描和比较。它可以提高NLJ在处理大数据集时的性能,但是会占用过多的CPU资源。会多次扫描被驱动表,占用磁盘IO资源。

Hash Join 算法

Beginning with MySQL 8.0.20, support for block nested loop is removed, and the server employs a hash join wherever a block nested loop would have been used previously.(dev.mysql.com/doc/refman/…)

  从 MySQL 8.0.20 开始,删除了BNL算法,使用了Hash Join 算法替代。

执行流程

我们以下面官方例子为准:

SELECT 
	given_name,country_name 
FROMpersons
JOIN countries 
ON persons.country_id = countries.country_id;

hash join 分为两个阶段; build 构建阶段和 probe 探测阶段。

build 构建

在构建阶段,MySQL使用Join字段作为哈希表Key,在内存中构建Hash 表。

一文详解MySQL—Join的使用优化

正常情况MySQL会选择结果集较小(以字节为单位,而不是行数)的去构建。比如上面会对 countries.country_id 进行 hash 计算:hash(countries.country_id) 然后将值放入内存中 hash table 的相应位置。将所有行存储在哈希表中后,构建阶段就完成了。

probe 探测阶段

在探测阶段,MySQL逐行遍历被驱动表,然后计算join条件的hash值,并在hash表中查找,如果匹配,则输出给客户端,否则跳过。所有内表记录遍历完,则整个过程就结束了。

一文详解MySQL—Join的使用优化

比如上面遍历persons 表中每行数据,然后取出Join字段的值进行 hash 计算;hash(persons.country_id),然后去内存中 hash table 中进行查找,匹配成功会发送给客户端。

内存中hash表的大小是由参数join_buffer_size 控制的,但是,如果构建hash table 内存大于可用内存,会发生什么情况?

  当内存在build构建阶段变满时,服务器会将其余的构建写入磁盘上的多个文件中。同时会设置文件的数量,确保最大的文件的大小与join_buffer_size一致。

每行数据写入哪个块文件是通过计算 join 属性的哈希来确定的。请注意,在下图中,使用的哈希函数与内存中生成阶段使用的哈希函数不同。我们稍后会明白为什么

一文详解MySQL—Join的使用优化

在探测阶段,服务器对于persons 表每一行数据使用同样的hash算法进行分区。这样,我们就可以确定两个输入之间的匹配行将位于同一对文件中。

一文详解MySQL—Join的使用优化

探测阶段完成后,开始从磁盘读取文件。首先会将build构建阶段的第一个文件,也就是下图中的左边的文件,加载到内存中哈希表中。这就解释了为什么希望最大的文件大小与内存一致,接着读取在探测阶段生成的文件,下图中右边的文件,在内存哈希表中进行匹配,就像之前内存操作一样。处理第一个文件后,移动到下一块文件,继续,直到处理完所有文件。

一文详解MySQL—Join的使用优化

到这里也明白了,如果我们对两个操作使用相同的哈希函数,那么在将构建文件加载到哈希表中时,我们会得到一个非常糟糕的哈希表,因为同一个文件中的所有行都将哈希为相同的值。

如何使用

MySQL 8.0.20之前,使用 EXPLAIN FORMAT=tree 来查看是否将使用Hash Join算法。

mysql> EXPLAIN   FORMAT=tree  SELECT
	u.`name`,
	u.user_code,
	o.order_name 
FROM
	`user` u
	JOIN `order` o ON u.user_code = o.user_code;
+-------------------------------------------------------------+
| EXPLAIN                                                           
+-------------------------------------------------+
| -> Inner hash join (u.user_code = o.user_code)  (cost=7.50 rows=7)
    -> Table scan on o  (cost=0.05 rows=9)
    -> Hash
        -> Table scan on u  (cost=0.95 rows=7)
+-----------------------------------------------------------+
1 row in set (0.04 sec)

时间复杂度分析

整体上对驱动表遍历1次(驱动表有M行记录),被驱动表遍历1次(被驱动表有N行记录)。 因此它的时间复杂度为:O(M+N)O(M+N)O(M+N)。它通常比嵌套循环算法(NLJ)更有效,尤其是在其中一个结果集可以完全放入join_buffer内存的情况下。

NLJ算法优化

为了优化Nested-Loop Join的性能,尽可能减少 Join 语句中的 Nested Loop 的循环总次数,就是让驱动表的结果集尽可能的小。对于很多表的关联通过应用层拆分成多个语句然后再拼接查询结果更方便, 而且性能也不会差。

join的时候明确知道哪张表是小表的时候,可以用straight_join写法固定连接驱动方式

BNL算法优化

使用Block Nested-Loop Join(BNL)算法时,可能会对被驱动表做多次扫描,占用磁盘IO资源,并且需要执行M∗NM*NM∗N次对比但是会占用过多的CPU资源。

优化的常见做法是,给被驱动表的join字段加上索引,把BNL算法转成NLJ算法。

无法设置索引的情况可以通过设置join_buffer_size参数来控制Join Buffer的大小,以减少分段查询次数

Hash Join算法优化

Hash Join算法在从 MySQL 8.0.18 以后才会用到,也是为了替代上面的BNJ算法。

当哈希表所需的内存量超过join_buffer_size大小,会使用磁盘的文件进行处理,所以增加 join_buffer_size值避免生成文件可以极大提升查询速度。

以上就是一文详解MySQL—Join的使用优化的详细内容,更多关于MySQL Join使用优化的资料请关注我们其它相关文章!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-数据库
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯