博主历时三年精心创作的《大数据平台架构与原型实现:数据中台建设实战》一书现已由知名IT图书品牌电子工业出版社博文视点出版发行,点击《重磅推荐:建大数据平台太难了!给我发个工程原型吧!》了解图书详情,京东购书链接:https://item.jd.com/12677623.html,扫描左侧二维码进入京东手机购书页面。 |
我们可能在一些介绍数据库 Join 档中看到 Build 和 Probe,分别代表着 Join 操作中的 右表 和 左表,为什么会有这样的称呼呢?原来它们都出自于一种叫 ”Hash Join“ 的 join 算法(常见的 Join 算法有:Hash Join、Loop Join、Merge Join)。先看一下名词解释:
-
Hash Join:一种实现 Join 的算法,它通过在 Join 的一侧构建 Hash Table 并在另一侧不断匹配 Hash Table 来得到 Join 的结果。
-
Build Side (构建端 / 右表):Hash Join 中用于构建 Hash Table 的一侧,称为 Build Side。多数引擎默认以 Join 的右表作为 Build Side。
-
Probe Side(探查端 / 左表):Hash Join 中用于不断匹配 Hash Table 的一侧,称为 Probe Side。多数引擎默认以 Join 的左表作为 Probe Side。
下面,简答介绍一下 Hash Join 的原理,我们基于 Hash join in MySQL 8 一文给出的解释展开,讲解使用的 SQL 示例为:
SELECTgiven_name, country_name
FROMpersons JOIN countries ON persons.country_id = countries.country_id;
Hash Join 的实现分为:构建和探查两个阶段,以下是详细介绍。
Hash Join 原理:构建阶段
在 Hash Join 算法下,当两张表要 Join 时,SQL 引擎会在内存中创建一张哈希表,然后选择将其中一张较小的表(按字节度量而不是行数)的数据加载到这张哈希表中,并以 Join 列的值作哈希的 Key。既然是要将表的数据加载到内存中,所以,不难理解算法为什么要选择加载小表而不是大表。
在上面的 SQL 示例中,countries
表肯定是一张小表,所以它会被加载到内存的哈希表中,也就是成为 Build Side,而 Join 列 country_id
的值经 hash 后的值会作为哈希表中 Key。
❖ 至于为什么现在都将右表称为 Build Side,左表称为 Probe Side,我并没有找到比较主流的有说服力的观点,可能是因为算法在最初提出时就是这样约定的:选择右表作 Build Side, 左表作 Probe Side,后来随着 SQL 引擎的优化,虽然能自动选择小表作为 Build Side 了,但这种称谓习惯被保留了下来。欢迎了解其中原委的读者补充
下图形象地展示了构建阶段的工作原理:
Hash Join 原理:探查阶段
构建阶段完成后,SQL 引擎就从 探测端 逐行读取记录,然后用 Join 列的 Hash 值去内存中的哈希表中查找是否有对应记录,有就是匹配到了 构建端 的记录,然后联合两端的数据作为结果输出。
同样以上面的示例 SQL 为例,SQL 引擎逐行读取 persons
表中的记录,取出它的 country_id
列进行 hash 处理,以得到的哈希值为 Key 去哈希表中查找,找同相同哈希值的记录就意味着和 countries
表中的一条记录 Join 上了。
下图展示了探查阶段的工作原理:
不过,上图并不算好,没有把“探查”动作描述出来,下图相对更加形象一些:
Hash Join 的限制
最后,提醒一下 Hash Join 的限制,其实从上面的原理介绍中你大概能推测出来:由于 Hash Join 是使用 join 列的哈希值进行匹配的,所以,关联条件中必须包含至少一个 equi join(=)
!
参考资料:
https://www.zhihu.com/question/35906621
https://dev.mysql.com/blog-archive/hash-join-in-mysql-8/