Grace Hash Join：JOIN 如何使用磁盘

做的事：同样撞爆内存的JOIN，真实换成grace_hash算法

代码-- 上一篇验证过：这条JOIN默认(hash算法)真实要用约352MB内存 -- 本文把内存上限设到200MB，分别真实测hash和grace_hash两种算法 SELECT count() FROM demo.jleft INNER JOIN demo.jbig ON jleft.k=jbig.k SETTINGS join_algorithm='hash', max_memory_usage=200000000; SELECT count() FROM demo.jleft INNER JOIN demo.jbig ON jleft.k=jbig.k SETTINGS join_algorithm='grace_hash', max_memory_usage=200000000, grace_hash_join_initial_buckets=8;

验证：200MB上限下，hash真实失败，grace_hash真实成功

实测 · 本机执行输出（同一条JOIN，同样200MB内存上限）

join_algorithm='hash'：
→ DB::Exception: Query memory limit exceeded: would use 357.25 MiB
  (attempt to allocate chunk of 257.50 MiB), maximum: 190.73 MiB:
  While executing FillingRightJoinSide. (MEMORY_LIMIT_EXCEEDED)   ← 真实失败

join_algorithm='grace_hash'：
→ 真实成功返回结果
  memory_usage: 184297549 字节（约184MB）
  query_duration_ms: 210

同一条JOIN、同样500万行的大右表、同样200MB的内存上限，hash算法真实还是老样子要把整个右表一次性构建进内存(需要357MB，超限)；grace_hash算法真实用不到200MB就跑完了整条查询。

grace_hash真实是怎么用更少内存做完同一件事的

Grace Hash Join真实的思路借用了经典数据库教科书里的"Grace Hash Join"算法：不再要求整个右表一次性放进一个巨大的哈希表，而是先真实按JOIN key的哈希值把左右两表各自分成若干个桶（本文用grace_hash_join_initial_buckets=8设置了初始8个桶）——因为JOIN key的哈希值相同的行，一定会被分到左右两边相同编号的桶里，所以只需要每次只处理一对编号相同的桶，桶内的数据量比整个右表小得多，构建哈希表的内存需求也就跟着小了一个数量级。本文测出来的184MB相比hash算法需要的357MB，降了差不多一半——这跟本系列《External Group By》验证过的思路是同一类："化整为零"，把一次性需要的大内存需求拆成多次可控的小块。不过grace_hash不是免费的：分桶意味着数据真实可能需要写到磁盘上再读回来（桶数不够、单个桶还是装不下时会继续细分），比一次性在内存里搞定的hash join要多付出一些IO和调度开销，本文测出来它的耗时(210ms)比之前hash算法在内存充裕时的表现(89.5MB内存/31ms，见本系列《ClickHouse JOIN的几种算法》)要慢不少——这是用时间换内存的真实取舍，只有当内存真的不够、hash join会失败的场景下，才值得为了grace_hash多付出的这部分时间成本。

分步演示：从hash失败到grace_hash分桶成功

每一步都是本文上面用真实两种JOIN算法跑出来的原始结果。

hash失败的地方，grace_hash真实分桶跑成功了

这一步新验证的算法

本文用到的工具

本机 ClickHouse 26.9.4（单节点），真实对比 join_algorithm='hash' 与 'grace_hash'
真实的 grace_hash_join_initial_buckets 分桶设置

下一篇 · CLICKHOUSE 内部原理 41

字典 JOIN：为什么有时比普通 JOIN 更快