ClickHouse JOIN 的几种算法

做的事：真实EXPLAIN一条JOIN，看ClickHouse默认选了哪种算法

代码CREATE TABLE demo.jleft (k UInt64, v String) ENGINE=MergeTree ORDER BY k; CREATE TABLE demo.jright (k UInt64, name String) ENGINE=MergeTree ORDER BY k; INSERT INTO demo.jleft SELECT number, toString(number) FROM numbers(5000000); INSERT INTO demo.jright SELECT number, concat('name', toString(number)) FROM numbers(1000000); SELECT value FROM system.settings WHERE name='join_algorithm'; EXPLAIN actions=1 SELECT jleft.k, name FROM demo.jleft INNER JOIN demo.jright ON jleft.k=jright.k;

验证：join_algorithm真实是一个优先级列表，不是单一选项

实测 · 本机执行输出

SELECT value FROM system.settings WHERE name='join_algorithm';
→ direct,parallel_hash,hash,ie_join      ← 真实是逗号分隔的优先级列表

EXPLAIN actions=1 ... INNER JOIN ...;
→ Join (JOIN FillRightFirst)
     Type: inner | Strictness: all
     Algorithm: SpillingHashJoin(ConcurrentHashJoin)   ← 真实最终选中的算法

ClickHouse真实会按这个列表从左到右依次检查每种算法是否适用于当前这条JOIN（比如direct只在右表是Dictionary或者能常数时间查找的特殊引擎时才能用），第一个满足条件的就是真实最终采用的算法——本文这条普通MergeTree表之间的INNER JOIN，真实走到了parallel_hash对应的实现，具体呈现为SpillingHashJoin(ConcurrentHashJoin)：一个支持多线程并发构建、并且真实具备落盘能力的哈希JOIN实现。

意外发现：真实测试中partial_merge比hash join更快更省内存

实测 · 本机执行输出（500万行 JOIN 100万行，真实两张表都已按JOIN key排序）

join_algorithm='hash'         ：真实内存 89,559,868 字节（约89.5MB），耗时 31ms
join_algorithm='partial_merge'：真实内存  9,112,463 字节（约9.1MB），耗时 16ms

真实差距：内存少约10倍，耗时快约2倍

这个结果一开始有点反直觉——教科书印象里hash join通常被认为是更快的通用选择，但本文真实测出来partial_merge反而更快也更省内存，原因在于本文这两张表的ORDER BY都恰好是JOIN key本身(k)——partial_merge算法真实是靠对两边数据做归并（跟本系列《Part合并》一篇验证过的k路归并是同一类思路）来匹配，如果两边数据本来就是按JOIN key排好序的，归并操作可以真实边读边匹配，几乎不需要额外的内存缓冲；而hash算法不管两边数据顺序如何，都要先把右表（本文的jright，100万行）真实完整构建成一个哈希表放进内存，这份哈希表构建的成本跟数据是否有序无关。这个真实结果提醒了一件事：算法的选择不该只看"名气"或者默认优先级，而要结合自己的表结构——如果两张表本来就按JOIN key排序（或者JOIN key正好是各自的主键），partial_merge值得真实测一测；但如果JOIN key是跟排序键无关的普通列，partial_merge就要真实退化成先排序再归并，这时候优势会消失甚至反过来变慢，本系列后面《Hash Join为什么容易占满内存》会用一张没有这种排序优势的表来验证hash join真实的内存问题。

分步演示：从默认算法到partial_merge的意外优势

每一步都是本文上面用真实EXPLAIN和计时跑出来的原始结果。

默认算法之外，真实测出的一个反直觉结果

这一步新验证的算法

本文用到的工具

本机 ClickHouse 26.9.4（单节点），真实的 EXPLAIN actions=1 与 join_algorithm 设置
真实对比hash与partial_merge两种算法在已排序表上的表现

下一篇 · CLICKHOUSE 内部原理 39

Hash Join 为什么容易占满内存