MySQL新特性之哈希连接
概述
很长一段时间,MySQL 执行 连接 的唯一算法是
嵌套循环算法
( nested loop algorithm) 的变体 ,但是嵌套循环算法
在某些场景下非常低效,也是 MySQL 一直被诟病的一个问题。
随着 MySQL 8.0.18 的发布,MySQL Server 可以使用哈希连接
(hash join),这篇文章将会简单介绍下哈希连接
如何实现,看看在 MySQL 中它是如何工作的,何时使用它,有什么限制。
哈希连接简介
什么是哈希连接?
哈希连接是一种用于关系型数据库中的连接算法,只能用于有等连接条件的连接中(on a.b = c.b)。它通常比 嵌套循环 算法 更高效(探测端非常非常小除外),尤其是在没有命中索引的情况下。
简单来说,哈希连接算法就是先把一张小表加载到内存哈希表里,然后遍历大表的数据,逐行去哈希表中匹配符合条件的数据,返回到客户端。
(哈希表只是示例,方面理解,实际 hash 的 key 是连接的值,value 是数据行链表)
通常将 哈希连接 分为两个阶段,构建阶段(build phase)和探测阶段(probe phase)。在构建阶段,先选择合适的表作为「构建输入」,构建哈希表,然后再依次遍历另一个「探测输入」表记录去探测哈希表查找符合连接条件的记录。
以上图为例,查询城市对应的省份。我们假设 city 为 构建输入,在构建阶段,服务器构建一个 city 哈希 表 ,遍历 city 表,将行依次放进 哈希表,键为 hash(province_id),值为对应的 城市行。`
在探测阶段,服务器开始从 探测输入(province) 读取行。对于每一行都使用 hash(province.province_id) 值作为查找键探测哈希表以匹配行。
也就是,构建输入能全部被加载到内存的情况下,仅扫每个探测行一次,使用常数时间查找就可以查找到两个输入之间匹配的行。
数据太多不能放入内存怎么办?
将 构建输入 全部加载到内存中无疑是效率最高的,但在有些情况下,内存不足以将整张表加载到内存中,就需要分批来处理。
常见的做法有两种:
分批加载到内存处理
- 读取最大内存可以容纳的记录创建哈希表 构建输入 生成哈希表;
- 遍历 探测输入 对这部分哈希表进行一次全量探测;
- 清理掉哈希表重新进行这个流程,直至全部处理完成。
这种方式会导致探测输入全表被扫描多次。
写到文件处理
- 当在构建哈希表阶段内存用完时,服务器将会把剩余的构建输入写到磁盘上的许多小文件中,小文件块经过计算可以全部被读入内存并创建哈希表(避免文件块太大后续无法加载到内存还需要再次分隔);
- 在探测阶段,由于探测行可能与写入磁盘的构建输入的某行匹配,所以也需要将探测输入写入到磁盘中;
- 探测阶段完成后,从磁盘读取块文件并加载到内存散列表中,再从探测输入读取响应的块文件并探测匹配项;
- 处理完后,移动到下一对块文件,直至全部处理完成。
MySQL 中的哈希连接实现
MySQL 会选择两个输入中较小的一个作为构建输入(以字节计算),在内存足够的情况下将构建输入加载到内存处理,不够的情况下使用写入文件的方式处理。
可以使用 join_buffer_size
系统变量控制 哈希连接 的内存使用,哈希连接 使用的内存不能超过这个数量,当超过这个数量时,MySQL 将使用文件来处理。
如果内存超过 join_buffer_size
,并且文件超过 open_files_limit
,执行可能失败。
可以使用如下两个解决方案:
- 增大
join_buffer_size
来避免 哈希连接 溢出到磁盘 - 增大
open_files_limit
MySQL 什么情况下会使用哈希连接?
在 MySQL 8.0.18 版本中,如果使用一个或多个等连接条件将表连接在一起,并且没有可用于连接条件的索引,将使用哈希连接。如果索引可用,MySQL 倾向于使用索引查找来支持嵌套循环。
默认情况下,MySQL 会尽可能使用哈希连接 ,可以通过以下两种方式启用或关闭:
-
设置全局或 session 变量 (hash_join = on or hash_join = off);
SET optimizer_switch="hash_join=off";
-
使用 hints (HASH_JOIN or NO_HASH_JOIN)。
我们将使用以下查询作为示例:
EXPLAIN FORMAT = tree SELECT city.name AS city_name, province.name AS province_name FROM city JOIN province ON city.province_id = province.province_id;
输出为:
| -> Inner hash join (city.province_id = province.province_id) (cost=1333.82 rows=1329) -> Table scan on city (cost=0.14 rows=391) -> Hash -> Table scan on province (cost=3.65 rows=34)
哈希连接 也可以用到多个 join 的查询中,只要存在等值连接,就可以使用哈希连接。
例如以下查询:
EXPLAIN FORMAT= TREE SELECT city.name AS city_name, province.name AS province_name, country.name AS country_name FROM city JOIN province ON city.province_id = province.province_id AND city.id < 50 JOIN country ON province.province_id = country.id
输出为:
| -> Inner hash join (city.province_id = country.id) (cost=23.27 rows=2) -> Filter: (city.id < 50) (cost=5.32 rows=5) -> Index range scan on city using PRIMARY (cost=5.32 rows=49) -> Hash -> Inner hash join (province.province_id = country.id) (cost=4.00 rows=3) -> Table scan on province (cost=0.59 rows=34) -> Hash -> Table scan on country (cost=0.35 rows=1)
哈希连接也同样适用于 「笛卡尔积」,即没有指定查询条件,如下:
EXPLAIN FORMAT= TREE SELECT * FROM city JOIN province;
输出为:
| -> Inner hash join (cost=1333.82 rows=13294) -> Table scan on city (cost=1.17 rows=391) -> Hash -> Table scan on province (cost=3.65 rows=34)
MySQL 什么情况下不会使用哈希连接?
-
目前 MySQL 哈希连接只支持内连接,反连接、半连接和外连接仍然使用块嵌套循环执行。
-
如果索引可用,MySQL 会更倾向于使用索引查找来支持嵌套循环;
-
当不存在等值查询时,会使用嵌套循环。
如下:
EXPLAIN FORMAT=TREE SELECT * FROM city JOIN province ON city.province_id < province.province_id;
输出为:
| <not executable by iterator executor>
如何查看语句执行是否使用哈希连接?
EXPLAIN FORMAT= TREE
在 MySQL 8.0.16 及之后的版本可以使用,TREE 提供了类似于树的输出,对查询处理的描述比传统格式更加精确,它是唯一显示 哈希连接 用法的格式。
除此之外,也可以使用 EXPLAIN ANALYZE
查看 哈希连接 信息。
<hr/> 以上基于 MySQL community Server 8.0.18。
参考
欢迎对 MySQL 有兴趣的朋友一起学习交流。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
MySQL 8.0发布,你熟悉又陌生的Hash Join?
昨天下午在查资料的时候,无意间点到了MySQL的官网。发现MySQL发布了一个新版本。 Mysql这个数据库有没有人不熟悉?不用的?没有吧。 2019年末,MySQL发布的8.0.18 GA版本,带来了一些新特性和增强功能。其中最引人注目的莫过于多表连接查询支持Hash Join。 还是老样子,建议英文好的同学直接看这里: https://dev.mysql.com/doc/refman/8.0/en/hash-joins.html 关于MySQL Hash Join的特性介绍: 1、对于大数据量的表关联,HJ(Hash Join)速度将明显比NL(Nested Loop)快很多 2、在内存中处理 3、必要情况下,会使用磁盘空间 4、用于内连接,可扩展到外连接、半连接和反连接 5、替换查询计划中的Block Nested Loop 6、可以通过HINT强制SQL走HJ或者NL 有的同学可能已经懵逼了。什么是Hash Join?什么是NL?HINT又是什么鬼? 第一部分先做一个简单的科普 首先,在多表联合查询的时候,如果我们查看它的执行计划,就会发现里面有多表之间的连接方式。多表之间的连...
- 下一篇
InnoDB 事务加锁分析
本文首发于 vivo互联网技术 微信公众号 链接:https://mp.weixin.qq.com/s/S7MhlsZveBHRSQhq5aTIJA 作者:何志创 一般大家对数据库事务的了解可能停留在事务的ACID特性以及事务4种不同的隔离级别层面上,而对于事务 4 种不同隔离级别如何实现了解相对较少。 本文以 MySQL 数据库InnoDB引擎为例,为大家分析InnoDB数据库引擎对默认的隔离级别可重复读(RR)的具体实现。 整文知识点介绍:事务4种隔离级别、不同隔离级别解决的问题、MVCC、锁的类型、加锁案例分析;阅读完整文相信大家对事务隔离级别的具体实现有了一定的认识。 一、事务的隔离级别 1、4 种隔离级别 (1)未提交读(Read uncommitted):一个事务读取到其他事务未提交的数据,是级别最低的隔离机制; (2)提交读(Read committed):一个事务读取到其他事务提交后的数据; (3)可重复读(Repeatable read):一个事务对同一份数据读取到的相同,不在乎其他事务对数据的修改; (4)序列化(Serializable) :事务串行化执行,隔离级...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- SpringBoot2初体验,简单认识spring boot2并且搭建基础工程
- Linux系统CentOS6、CentOS7手动修改IP地址
- SpringBoot2全家桶,快速入门学习开发网站教程
- CentOS8编译安装MySQL8.0.19
- CentOS7,CentOS8安装Elasticsearch6.8.6
- SpringBoot2整合Redis,开启缓存,提高访问速度
- Red5直播服务器,属于Java语言的直播服务器
- CentOS6,CentOS7官方镜像安装Oracle11G
- Windows10,CentOS7,CentOS8安装Nodejs环境
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池