专栏首页性能与架构MySQL8 的 Hash join 算法

MySQL8 的 Hash join 算法

以前 MySQL 的 join 算法只有 nested loop 这一种,在 MySQL8 中推出了一种新的算法 hash join,比 nested loop 更加高效。

下面我就看看它是怎么工作的。

用这个SQL作为例子:

hash join 工作过程分为2个阶段:

  • build 构建阶段
  • probe 探测阶段

1. 构建阶段

从参与join的2个表中选一个,选择占空间小的那个表,不是行数少的,这里假设选择了 countries 表。

countries 表中每行的 join 字段值进行 hash 计算:

hash(countries.country_id)

计算后放入内存中 hash table 的相应位置。

所有行都存放到 hash table 之后,构建阶段完成。

2. 探测阶段

persons 表中每行中的 join 字段的值进行 hash 计算:

hash(persons.country_id)

拿着计算结果到内存 hash table 中进行查找匹配,找到一行就发给 client。

这样就完成了整个 join 操作,每个表只扫描一次就可以了,扫描匹配时间也是恒定的,非常高效。

这个例子中,countries 表顺利的全部放入了内存,可用内存的大小是由 join_buffer_size 控制的。

实际环境中,肯定会有比较大的表,那么超过了可用内存时怎么办呢?

需要溢出到磁盘了。

3. 溢出到磁盘

在构建阶段过程中,如果内存满了,会把表中剩余数据写到磁盘上。

不会只写入一个文件,会分成多个块文件。

MySQL 会保证每个块文件的大小都是适合可用内存的。

怎么决定某一行记录写入哪个块文件呢?也是通过hash计算join字段决定的:

hash_2(countries.country_id)

可以看到,对于大表,构建阶段分为了2步:

  • 写入内存 hash table
  • 写入块文件

然后是探测阶段,首先还是会走一遍和之前一样的流程,就是扫描一遍 persons 表的每一行,和内存中的 hash table 进行匹配。

但因为内存中的 hash table 不是全部数据,所以需要额外的处理:

persons 表的数据也写入多个块文件中。

怎么决定某一行记录写入哪个块文件呢?和构建阶段写入块文件的思路相同,这样,构建阶段的块文件和此处的块文件就是一一对应的关系了。

在正常的探测流程走完之后,开始处理这些块文件中的内容了。

逐一加载构建阶段的块文件到内存中,加载过程和正常的构建过程一致,对块文件中的每行数据进行 hash 计算,放入内存的 hash table 中。

构建好一个块文件之后,选择与其对应的探测块文件开始探测。

例如构建的是第0个构建块文件,那么就选择第0个探测块文件。

就这样一对一对的块文件进行处理,直到全部完成。

小结

hash join 算法先选一个小表,放入内存的 hash table,然后扫描另一个表,与 hash table 匹配出结果数据。

当表太大,无法一次放入内存时,就分而治之,写入块文件,再对每个块文件走一遍正常时的流程。

参考资料:

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

本文分享自微信公众号 - 性能与架构(yogoup),作者:杜亦舒

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Redis 内存优化案例

    在Redis的配置文件中有这么两项配置: hash-max-ziplist-entries 512 hash-max-ziplist-value 64 其中...

    dys
  • Mysql Query Cache的负面影响

    Query Cache确实是以比较简单的实现带来巨大性能收益的功能。但可能很多人都忽略了使用QueryCache之后所带来的负面影响 (1)Query的hash...

    dys
  • 开发平台meteor体验

    需要注意 meteor不支持windows系统,需要在linux或mac ox下运行 meteor是基于nodejs的,所以系统中需安装好nodejs 我的...

    dys
  • 2020-6-1-理解webpack的hash,contenthash,chunkhash

    对于浏览器来说,一方面期望每次请求页面资源时,获得的都是最新的资源;一方面期望在资源没有发生变化时,能够复用缓存对象。

    黄腾霄
  • 区块链基础之哈希函数

    hash函数的作用hash算法的安全性 常见的Hash算法 MD5 SHA1 SHA256 哈希碰撞钱包的...

    efonfighting
  • hash散列 introduction

    hash散列是在记录的存储位置与他的关键字之间建立的对应关系f, 使得每个key都对应一个存储位置, 查找时根据key的hash去查找.

    CoffeeLand
  • djb2 hash算法

    Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就...

    李小白是一只喵
  • 教你如何迅速秒杀掉:99%的海量数据处理面试题

       一般而言,标题含有“秒杀”,“99%”,“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌,但进一步来讲,如果读者读罢此文,却无任何收获,那么,我也甘愿...

    bear_fish
  • 面试题,如何在千万级的数据中判断一个值是否存在?

    当你看到这个标题的时候,你也许会想我可以使用hashmap之类的来存储值,然后get就是了。又或者把数据存在数据库里然后去判断就可以了。

    ImportSource
  • 纸上谈兵: 哈希表 (hash table)

    HASH 哈希表(hash table)是从一个集合A到另一个集合B的映射(mapping)。映射是一种对应关系,而且集合A的某个元素只能对应集合B中的一个元素...

    Vamei

扫码关注云+社区

领取腾讯云代金券