MySQL8.0 新特性 Hash Join「建议收藏」

MySQL8.0 新特性 Hash Join「建议收藏」概述&背景 MySQL一直被人诟病没有实现HashJoin,最新发布的8.0.18已经带上了这个功能,令人欣喜。有时候在想,MySQL为什么一直不支持HashJoin呢?我想可能是因为MySQ

概述&背景

MySQL一直被人诟病没有实现HashJoin,最新发布的8.0.18已经带上了这个功能,令人欣喜。有时候在想,MySQL为什么一直不支持HashJoin呢?我想可能是因为MySQL多用于简单的OLTP场景,并且在互联网应用居多,需求没那么紧急。另一方面可能是因为以前完全靠社区,这种演进速度毕竟有限,Oracle收购MySQL后,MySQL的发版演进速度明显加快了很多。

HashJoin本身算法实现并不复杂,要说复杂,可能是优化器配套选择执行计划时,是否选择HashJoin,选择外表,内表可能更复杂一点。不管怎样现在已经有了HashJoin,优化器在选择Join算法时又多了一个选择。MySQL本着实用主义,相信这个功能增强也回应了一些质疑,有些功能不是没有能力做好,而是有它的优先级。

在8.0.18之前,MySQL只支持NestLoopJoin算法,最简单的就是Simple NestLoop Join,MySQL针对这个算法做了若干优化,实现了Block NestLoop Join,Index NestLoop Join和Batched Key Access等,有了这些优化,在一定程度上能缓解对HashJoin的迫切程度。下文会单独拿一个章节讲MySQL的这些Join优化,下面先讲HashJoin。

Hash Join算法

NestLoopJoin算法简单来说,就是双重循环,遍历外表(驱动表),对于外表的每一行记录,然后遍历内表,然后判断join条件是否符合,进而确定是否将记录吐出给上一个执行节点。从算法角度来说,这是一个M*N的复杂度。HashJoin是针对equal-join场景的优化,基本思想是,将外表数据load到内存,并建立hash表,这样只需要遍历一遍内表,就可以完成join操作,输出匹配的记录。如果数据能全部load到内存当然好,逻辑也简单,一般称这种join为CHJ(Classic Hash Join),之前MariaDB就已经实现了这种HashJoin算法。如果数据不能全部load到内存,就需要分批load进内存,然后分批join,下面具体介绍这几种join算法的实现。

In-Memory Join(CHJ)

HashJoin一般包括两个过程,创建hash表的build过程和探测hash表的probe过程。

1).build phase

遍历外表,以join条件为key,查询需要的列作为value创建hash表。这里涉及到一个选择外表的依据,主要是评估参与join的两个表(结果集)的大小来判断,谁小就选择谁,这样有限的内存更容易放下hash表。

2).probe phase

hash表build完成后,然后逐行遍历内表,对于内表的每个记录,对join条件计算hash值,并在hash表中查找,如果匹配,则输出,否则跳过。所有内表记录遍历完,则整个过程就结束了。过程参照下图,来源于MySQL官方博客

MySQL8.0 新特性 Hash Join「建议收藏」    MySQL8.0 新特性 Hash Join「建议收藏」

左侧是build过程,右侧是probe过程,country_id是equal_join条件,countries表是外表,persons表是内表。

On-Disk Hash Join

CHJ的限制条件在于,要求内存能装下整个外表。在MySQL中,Join可以使用的内存通过参数join_buffer_size控制。如果join需要的内存超出了join_buffer_size,那么CHJ将无能为力,只能对外表分成若干段,每个分段逐一进行build过程,然后遍历内表对每个分段再进行一次probe过程。假设外表分成了N片,那么将扫描内表N次。这种方式当然是比较弱的。在MySQL8.0中,如果join需要内存超过了join_buffer_size,build阶段会首先利用hash算将外表进行分区,并产生临时分片写到磁盘上;然后在probe阶段,对于内表使用同样的hash算法进行分区。由于使用分片hash函数相同,那么key相同(join条件相同)必然在同一个分片编号中。接下来,再对外表和内表中相同分片编号的数据进行CHJ的过程,所有分片的CHJ做完,整个join过程就结束了。这种算法的代价是,对外表和内表分别进行了两次读IO,一次写IO。相对于之之前需要N次扫描内表IO,现在的处理方式更好。

MySQL8.0 新特性 Hash Join「建议收藏」                     MySQL8.0 新特性 Hash Join「建议收藏」

                                   MySQL8.0 新特性 Hash Join「建议收藏」

左上侧图是外表的分片过程,右上侧图是内表的分片过程,最下面的图是对分片进行build+probe过程。

Grace Hash Join

主流的数据库Oracle,SQLServer,PostgreSQL早就支持了HashJoin。Join算法都类似,这里介绍下Oracle使用的Grace Hash Join算法。其实整个过程与MySQL的HashJoin类似,主要有一点区别。当出现join_buffer_size不足时,MySQL会对外表进行分片,然后再进行CHJ过程。但是,极端情况下,如果数据分布不均匀,导致大量的数据hash后都分布在一个分桶中,导致分片后,join_buffer_size仍然不够,MySQL的处理方式是一次读分片读若干记录构建hash表,然后probe对应的外表分片。处理完一批后,清理hash表,重复上述过程,直到这个分片的所有数据处理完为止。这个过程与CHJ在join_buffer_size不足时,处理逻辑相同。

GraceHash在遇到这种情况时,会继续分片进行二次Hash,直到内存足够放下一个hash表为止。但是,这里仍然有极端情况,如果输入join条件都相同,那么无论进行多少次Hash,都没法分开,那么这个时候GraceHashJoin也退化成和MySQL的处理方式一样。

hybrid hash join

与GraceHashJoin的区别在于,如果缓存能缓存足够多的分片数据,会尽量缓存,那么就不必像GraceHash那样,严格地将所有分片都先读进内存,然后写到外存,然后再读进内存去走build过程。这个是在内存相对于分片比较充裕的情况下的一种优化,目的是为了减少磁盘的读写IO。目前Oceanbase的HashJoin采用的是这种join方式。

MySQL-Join算法优化

在MySQL8.0.18之前,也就是在很长一段时间内,MySQL数据库并没有HashJoin,主要的Join算法是NestLoopJoin。SimpleNestLoopJoin显然是很低效的,对内表需要进行N次全表扫描,实际复杂度是N*M,N是外表的记录数目,M是记录数,代表一次扫描内表的代价。为此,MySQL针对SimpleNestLoopJoin做了若干优化,下面贴的图片均来自网络

BlockNestLoopJoin(BNLJ)

MySQL采用了批量技术,即一次利用join_buffer_size缓存足够多的记录,每次遍历内表时,每条内表记录与这一批数据进行条件判断,这样就减少了扫描内表的次数,如果内表比较大,间接就缓解了IO的读压力。

                                                  MySQL8.0 新特性 Hash Join「建议收藏」

IndexNestLoopJoin(INLJ)

如果我们能对内表的join条件建立索引,那么对于外表的每条记录,无需再进行全表扫描内表,只需要一次Btree-Lookup即可,整体时间复杂度降低为N*O(logM)。对比HashJoin,对于外表每条记录,HashJoin是一次HashTable的search,当然HashTable也有build时间,还需要处理内存不足的情况,不一定比INLJ好。

Batched Key Access

IndexNestLoopJoin利用join条件的索引,通过Btree-Lookup去匹配减少了遍历内表的代价。如果join条件是非主键列,那么意味着大量的回表和随机IO。BKA优化的做法是,将满足条件的一批数据按主键排序,这样回表时,从主键的角度来说就相对有序,缓解随机IO的代价。BKA实际上是利用了MRR特性(MultiRangeRead),访问数据之前,先将主键排序,然后再访问。主键排序的缓存大小通过参数read_rnd_buffer_size控制。

MySQL8.0 新特性 Hash Join「建议收藏」      MySQL8.0 新特性 Hash Join「建议收藏」

总结

MySQL8.0以后,Server层代码做了大量的重构,虽然优化器相对于Oracle还有很大差距,但一直在进步。HashJoin的支持使得MySQL优化器有更多选择,SQL的执行路径也能做到更优,尤其是对于等值join的场景。虽然MySQL之前对于Join做过若干优化,比如NBLJ,INLJ以及BKA等,但这些代替不了HashJoin的作用。一个好用的数据库就应该具备丰富的基础能力,利用优化器分析出合适场景,然后拿出对应的基础能力以最高效的方式响应请求。

参考文档

https://en.wikipedia.org/wiki/Hash_join

https://mysqlserverteam.com/hash-join-in-mysql-8/

https://dev.mysql.com/worklog/task/?id=2241

https://www.cnblogs.com/qixinbo/p/10524142.html

https://zhuanlan.zhihu.com/p/35040231

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
转载请注明出处: https://daima100.com/10671.html

(0)
上一篇 2022-12-23
下一篇 2022-12-23

相关推荐

  • vertica 如何实现存储过程?「终于解决」

    vertica 如何实现存储过程?「终于解决」JAVA 等通用语言缺乏结构化计算类库,即使最简单的结构化算法,比如查询、排序、聚合,也要从零开始硬编码。对于很常用的算法,比如分组汇总、关联查询,则要编写大篇幅的代码。对于复杂些的算法,甚至要设计…

    2023-03-03
    107
  • python数据增强三种方法(常用的数据增强方法)

    python数据增强三种方法(常用的数据增强方法)1 什么是数据增强?

    2023-10-25
    82
  • 打造个性化手机保护壳——Python正则表达式实战

    打造个性化手机保护壳——Python正则表达式实战在手机成为我们日常生活中不可或缺的工具的同时,保护它的重要性也逐渐凸显出来。而保护壳恰恰是最廉价、简单的选择之一,更何况定制一个个性化的保护壳也能彰显个人的品味。那么,如何用Python正则表达式来定制个性化手机保护壳呢?下面将从图片选取、文字添加以及图像处理三个方面来阐述。

    2024-02-21
    76
  • MySQL学习指南

    MySQL学习指南MySQL是一个关系型数据库管理系统,由瑞典MySQL AB 公司开发,属于 Oracle 旗下产品。MySQL 是最流行的关系型数据库管理系统之一,在 WEB 应用方面,MySQL是最好的 RDBM

    2023-04-17
    128
  • MySQL8功能详解——角色[通俗易懂]

    MySQL8功能详解——角色[通俗易懂]以下文章来源于MySQL解决方案工程师,作者徐轶韬 角色功能对于Oracle的DBA来说,不是什么特殊功能,但对于MySQL而言,这是一个人心所盼的功能。 MySQL的DBA现在可以创建角色、对其赋…

    2023-01-28
    103
  • mysql学习笔记第二节 日志系统 redolog与binlog「建议收藏」

    mysql学习笔记第二节 日志系统 redolog与binlog「建议收藏」第二节 日志系统 一条update语句的更新过程 首先让与这个表有关的所有缓存全都失效 其余与查询流程基本相似,但是还涉及到两个重要的日志模块-redo log和binlog redo log(重做日

    2023-04-17
    102
  • mysql零基础入门教程完整_MySQL入门

    mysql零基础入门教程完整_MySQL入门最开始入门学习MySQL的时候,连数据库是什么都不知道,后来在网上各种搜MySQL数据库的学习教程,才开始慢慢了解它。 MySQL 是最流行的关系型数据库管理系统,在 WEB 应用方面 MySQL 是

    2023-04-21
    102
  • Python中的__str__方法及其应用

    Python中的__str__方法及其应用在Python中,每个类都包含一些特殊方法,其中__str__便是其中一个。当我们调用print方法时,通常会输出该对象的一些信息。但是如果没有定义__str__方法,输出的信息不一定是我们需要的,这时就需要使用__str__特殊方法来自定义输出的格式。

    2024-02-24
    68

发表回复

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