MySQL Hash Join前世今生
* GreatSQL社区原创内容未经授权不得随意使用,转载请联系小编并注明来源。
因工作需要,对MySQL Hash Join的内部实现做了一些探索和实践,对这个由8.0.18开始引入的连接算法有了一定的了解,写文总结与各位大佬分享,欢迎大家指教。因篇幅较长,这份总结分成若干部分,我们今天先一起来看一下MySQL Hash join的变迁史。
爬了一下 MySQL worklog[1]
,并结合源码及各版本的实际使用,个人认为比较重要的 worklogs 为如下几个, 其它的变更一般围绕这些 worklogs 做的小调整或 bugfixes ,这里我们就不一一列举。
1. WL#2241: Hash join (变更版本:8.0.18)
主要内容:
- 新增执行类 HashJoinIterator ,实现 hash join 算法原型 (支持on-disk hash)
- HASH JOIN 仅支持 INNER JOIN ,并对使用 hash join 做了限制:关联表连接条件必须至少包含一条等值条件(equi-join condition, 如
t1.a = t2.a
),且join条件中的列不包含索引
注:这里我认为官网的 Release Notes[2]
描述是不太准确的,以如下例子为例,虽然该查询包含了非等值连接条件(non-equi-join condition, 如 t1.a <> t2.a
,t1.a = 1
, t2.a > 1
等),但实际查询中还是使用hash join的, 因为查询语句在解析执行过程中,可能会经历语句重写、sql优化等步骤,与表象上会有所不同,建议借助 explain 工具,查看实际上查询语句选择的 join 算法。
-- 版本:8.0.18
-- 在创建iterator时,t1.a > 1 会被当成表的过滤条件,而非inner join的join条件
-- 此查询仍使用了hash join(join 条件为空)
EXPLAIN FORMAT=tree SELECT * FROM t1 JOIN t2 ON t1.i > 1;
-> Inner hash join (cost=1.17 rows=3)
-> Table scan on t2 (cost=0.34 rows=2)
-> Hash
-> Filter: (t1.i > 1) (cost=0.65 rows=1)
-> Table scan on t1 (cost=0.65 rows=4)
- (尽量)使用HASH JOIN算法替换BNL(Blocked Nested-Loop)连接算法
2. WL#13377: Add support for hash outer, anti and semi join( 变更版本:8.0.20)
主要内容:
- HASH INNER JOIN改进
INNER JOIN中的
non-equi-join conditions
, 会被附为hash join的过滤条件:
-- 版本:8.0.20
EXPLAIN FORMAT=tree SELECT * FROM t1 JOIN t2 ON t1.i <> t2.i;
-> Filter: (t1.i <> t2.i) (cost=1.10 rows=2)
-> Inner hash join (no condition) (cost=1.10 rows=2)
-> Table scan on t2 (cost=0.18 rows=2)
-> Hash
-> Table scan on t1 (cost=0.45 rows=2)
- HAH JOIN支持outer join/anti join/semi join
-- 版本:8.0.20
-- Left outer join
EXPLAIN FORMAT=tree SELECT * FROM t1 LEFT JOIN t2 ON t1.i=t2.i;
-> Left hash join (t2.i = t1.i) (cost=0.88 rows=4)
-> Table scan on t1 (cost=0.45 rows=2)
-> Hash
-> Table scan on t2 (cost=0.23 rows=2)
-- Right outer join(注:MySQL在parser阶段会将所有的right join改写为left join
-- 所以我们这里看到的explain为Left hash join
EXPLAIN FORMAT=tree SELECT * FROM t1 RIGHT JOIN t2 ON t1.i=t2.i;
-> Left hash join (t1.i = t2.i) (cost=0.88 rows=4)
-> Table scan on t2 (cost=0.45 rows=2)
-> Hash
-> Table scan on t1 (cost=0.23 rows=2)
-- Semijoin
EXPLAIN FORMAT=tree SELECT * FROM t1 WHERE (t1.i) IN (SELECT t2.i FROM t2);
-> Hash semijoin (t2.i = t1.i) (cost=0.83 rows=2)
-> Table scan on t1 (cost=0.45 rows=2)
-> Hash
-> Table scan on t2 (cost=0.18 rows=2)
-- Antijoin
EXPLAIN FORMAT=tree
SELECT * FROM t2 WHERE NOT EXISTS (SELECT * FROM t1 WHERE t1.i = t2.i);
-> Hash antijoin (t1.i = t2.i) (cost=1.10 rows=4)
-> Table scan on t2 (cost=0.45 rows=2)
-> Hash
-> Table scan on t1 (cost=0.45 rows=2)
- 所有使用BNL的连接,都将被转为使用HASH JOIN
- non-equi-join conditions 处理
Hash join iterator引入
"extra" condition
的概念,部分non-equi-join conditions
会被当成Hash join iterator
的extra condition
, 在建hash table时,join key的计算不依赖这些条件,但会在hash查找到匹配项后,作为附加的过滤条件:
-- 版本: 8.0.20
-- 注: t1.i > 1 会被放到hash join的 extra conditions中
EXPLAIN FORMAT=tree SELECT * FROM t1 LEFT JOIN t2 ON t1.i=t2.i AND t1.i > 1;
-> Left hash join (t2.i = t1.i), extra conditions: (t1.i > 1) (cost=0.88 rows=4)
-> Table scan on t1 (cost=0.45 rows=2)
-> Hash
-> Table scan on t2 (cost=0.23 rows=2)
相关源码:
// 代码版本:8.0.20 HEAD: commit 91a17cedb1ee880fe7915fb14cfd74c04e8d6588
// 文件名:sql/hash_join_iterator.cc
int HashJoinIterator::ReadNextJoinedRowFromHashTable() {
int res;
bool passes_extra_conditions = false;
do { // 所有匹配行都需要多做一个extra condition的判定,因为有可能存在不同行的记录
// 映射在同一个join key的情况,因此需要通过遍历逐条读取出符合extra conditions
// 的数据
res = ReadJoinedRow(); // 读取通过join key查找已经得到的匹配行(单行记录)
DBUG_ASSERT(res == 0 || res == -1);
if (res == 0) {
passes_extra_conditions = JoinedRowPassesExtraConditions();
if (thd()->is_error()) {
// Evaluation of extra conditions raised an error, so abort the join.
return 1;
}
if (!passes_extra_conditions) {
++m_hash_map_iterator;
}
}
} while (res == 0 && !passes_extra_conditions);
}
3. WL#13459: Optimize hash table in hash join (变更版本:8.0.23)
主要内容:
- 优化hash join table的创建方法
这里MySQL所说的“优化”, 实际上会更激进一点,这个版本中,MySQL直接使用了一个基于
robin hood hashing[3]
实现的开源hash table[4]
,更换了原先的hash join table实现( from mem_root_unordered_multimap to robin_hood::unordered_flat_map) - 优化内存管理和使用,降低了 on-disk hash 的频率,提高了内存有效使用率等(其他的改进内容及提升的效果可以参考MySQL 8.0.23的
release notes[5]
以及worklog #13459[6]
的Low Level Design页面)
本篇我们对MySQL hash join的3个重要变更做了简要的总结,算是对它的前世今生有了印象,谢谢各位阅读;之后让我们会结合具体的sql查询样例,去跟踪一下对应的代码执行流程,不日更新,敬请期待。
参考文档
[1] MySQL worklog: https://dev.mysql.com/worklog/ [2] MySQL 8.0.18 release notes#optimizer: https://dev.mysql.com/doc/relnotes/mysql/8.0/en/news-8-0-18.html#mysqld-8-0-18-optimizer [3] robin hood hashing 算法介绍: https://programming.guide/robin-hood-hashing.html [4] robin hood hasing 开源实现: https://github.com/martinus/robin-hood-hashing [5] MySQL 8.0.23 release notes#optimizer: https://dev.mysql.com/doc/relnotes/mysql/8.0/en/news-8-0-23.html#mysqld-8-0-23-optimizer [6] MySQL worklog #13459: https://dev.mysql.com/worklog/task/?id=13459
Enjoy GreatSQL :)
《零基础学习MySQL》视频课程
戳此小程序即可直达B站
https://www.bilibili.com/video/BV1Da411W7Va?spm_id_from=333.999.0.0&vd_source=ae1951b64ea7b9e6ba11f1d0bbcff0e4
文章推荐:
关于 GreatSQL
GreatSQL是由万里数据库维护的MySQL分支,专注于提升MGR可靠性及性能,支持InnoDB并行查询特性,是适用于金融级应用的MySQL分支版本。
GreatSQL社区官网: https://greatsql.cn/
Gitee: https://gitee.com/GreatSQL/GreatSQL
GitHub: https://github.com/GreatSQL/GreatSQL
Bilibili:
https://space.bilibili.com/1363850082/video
相关文章
- MySQL 自定义函数_mysql随机时间函数
- 【踩坑实录】- ERROR: Row of size 966.66 KB could not be materialized by Hash Join Builder (join_node_id=6)
- 【MySQL高级】MySql中常用工具及Mysql 日志
- 新增MySQL表格列:一个步骤指南(mysql新增一列)
- 一键清空MySQL数据库的简单方法(mysql如何清空数据库)
- join探索MySQL中的Left Join功能(mysql中的left)
- MySQL单表最大记录:探讨其限制(mysql单表最大记录数)
- 文件夹MySQL进入Bin文件夹: 操作指南(mysql进入bin)
- MySQL 用户权限管理:构建安全的用户权限表(mysql用户权限表)
- MySQL中如何实现两个表的联系(mysql两个表如何关联)
- MySQL中处理换行符的技巧(mysql匹配换行符)
- 查看MySQL端口的步骤(mysql端口怎么查看)
- MySQL查询:掌握高效、简洁的结果(mysql查询软件)
- joinOracle强制Hash Join优化技术研究.(oracle强制hash)
- MySQL 内核优化:提升数据处理性能(mysql内核优化)
- MySQL分区之Hash法分析(mysql分区hash)
- MySQL中的多维数据库:令人兴奋的管理模式(mysql多维数据库)
- 使用Mysql把大表Hash分表(mysql分表hash)
- 提高效率!使用MySQL可视化工具,轻松管理数据——附图片(mysql可视化工具图片)
- 探究MySQL 数据匹配实现方法(mysql数据匹配)
- MySQL参数详解,让你更加了解Mysql参数定义及优化。(mysql参数定义)
- 如何有效地监控MySQL连接池?(mysql连接池监控)
- MySQL中使用Hash索引的优缺点(mysql hash索引)
- MySQL中JOIN的用法详解(mysql中jion用法)
- MySQL中JOIN语句的用法简介(mysql中jion)
- MySQL中ID字段类型详解(mysql中ID字段类型)
- 了解MySQL中Hash索引的特点和使用方法(mysql中hash索引)
- MySQL中的Cross Join用法(mysql中cross)
- 4核8G,MySQL数据库性能表现如何(4核8g mysql性能)
- MySQL轻松实现无需使用JOIN的查询(mysql 不用join)
- MySQL不支持Hash,如何优化数据加密方案(mysql不支持hash)