数据库哈希连接详解（MySQL新特性）

概述

很长一段时间，MySQL 执行 连接 的唯一算法是 嵌套循环算法 ( nested loop algorithm) 的变体 ，但是 嵌套循环算法 在某些场景下非常低效，也是 MySQL 一直被诟病的一个问题。

随着 MySQL 8.0.18 的发布，MySQL Server 可以使用哈希连接（hash join），这篇文章将会简单介绍下哈希连接如何实现，看看在 MySQL 中它是如何工作的，何时使用它，有什么限制。

推荐学习：MySQL教程

哈希连接简介

什么是哈希连接？

哈希连接是一种用于关系型数据库中的连接算法，只能用于有等连接条件的连接中（on a.b = c.b）。它通常比 嵌套循环 算法 更高效（探测端非常非常小除外），尤其是在没有命中索引的情况下。

简单来说，哈希连接算法就是先把一张小表加载到内存哈希表里，然后遍历大表的数据，逐行去哈希表中匹配符合条件的数据，返回到客户端。

（哈希表只是示例，方面理解，实际 hash 的 key 是连接的值，value 是数据行链表）

通常将 哈希连接 分为两个阶段，构建阶段（build phase）和探测阶段（probe phase）。在构建阶段，先选择合适的表作为「构建输入」，构建哈希表，然后再依次遍历另一个「探测输入」表记录去探测哈希表查找符合连接条件的记录。

以上图为例，查询城市对应的省份。我们假设 city 为 构建输入，在构建阶段，服务器构建一个 city 哈希 表 ，遍历 city 表，将行依次放进 哈希表，键为 hash(province_id)，值为对应的 城市行。`

在探测阶段，服务器开始从 探测输入（province） 读取行。对于每一行都使用 hash(province.province_id) 值作为查找键探测哈希表以匹配行。

也就是，构建输入能全部被加载到内存的情况下，仅扫每个探测行一次，使用常数时间查找就可以查找到两个输入之间匹配的行。

数据太多不能放入内存怎么办？

将 构建输入 全部加载到内存中无疑是效率最高的，但在有些情况下，内存不足以将整张表加载到内存中，就需要分批来处理。

常见的做法有两种：

分批加载到内存处理

1.读取最大内存可以容纳的记录创建哈希表 构建输入 生成哈希表；

2.遍历 探测输入 对这部分哈希表进行一次全量探测；

3.清理掉哈希表重新进行这个流程，直至全部处理完成。

这种方式会导致探测输入全表被扫描多次。

写到文件处理

1.当在构建哈希表阶段内存用完时，服务器将会把剩余的构建输入写到磁盘上的许多小文件中，小文件块经过计算可以全部被读入内存并创建哈希表（避免文件块太大后续无法加载到内存还需要再次分隔）；

2.在探测阶段，由于探测行可能与写入磁盘的构建输入的某行匹配，所以也需要将探测输入写入到磁盘中；

3.探测阶段完成后，从磁盘读取块文件并加载到内存散列表中，再从探测输入读取响应的块文件并探测匹配项；

4.处理完后，移动到下一对块文件，直至全部处理完成。

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 什么情况下不会使用哈希连接？

1.目前 MySQL 哈希连接只支持内连接，反连接、半连接和外连接仍然使用块嵌套循环执行。

2.如果索引可用，MySQL 会更倾向于使用索引查找来支持嵌套循环；

3.当不存在等值查询时，会使用嵌套循环。

如下：

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 查看 哈希连接 信息。

fa8fd94cc4b4d9671e4ee513ae2a31d1 以上基于 MySQL community Server 8.0.18。

Atas ialah kandungan terperinci 数据库哈希连接详解（MySQL新特性）. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!