选择正确的Join算法

这篇博客文章是系列文章的一部分

• ClickHouse 中支持的 Join 类型
• ClickHouse Join 内幕 - Hash Join、Parallel Hash Join、Grace Hash Join
• ClickHouse Join 内幕 - Full Sorting Merge Join、Partial Merge Join
• ClickHouse Join 内幕 - Direct Join

在前三篇文章中，我们深入探讨了为 ClickHouse 开发的 6 种不同的 join 算法。在这最后一篇文章中，我们将总结并直接比较所有 ClickHouse join 算法的执行时间和内存使用情况。基于此，我们将提供决策树以及 join 类型支持概述，您可以根据这些信息决定哪种 join 算法最适合您的特定场景。

到目前为止，已经为 ClickHouse 开发了以下 6 种 join 算法

• Direct join
• Hash join
• Parallel hash join
• Grace hash join
• Full sorting merge join
• Partial merge join

这些算法决定了 join 查询的计划和执行方式。默认情况下，ClickHouse 根据使用的join 类型和严格性以及连接表的引擎，使用 direct 或 hash join 算法。或者，ClickHouse 可以配置为自适应选择并在运行时动态更改要使用的 join 算法，具体取决于资源可用性和使用情况：当join_algorithm设置为auto时，ClickHouse 首先尝试 hash join 算法，如果该算法的内存限制被违反，则算法会动态切换为 partial merge join。您可以通过trace logging观察选择了哪个算法。ClickHouse 还允许用户指定所需的 join 算法。此图表概述了 ClickHouse join 算法，基于它们的相对内存消耗和执行时间：

Direct join 是 ClickHouse 最快的 join 算法，适用于右侧表的底层存储支持低延迟键值请求，以及当LEFT ANY JOIN 语义足够时。特别是对于大型右侧表，direct join 在执行时间方面显著改进，击败了所有其他 ClickHouse join 算法。

ClickHouse join 算法中的三种基于内存哈希表

• Hash join 速度快但受内存限制，并且是最通用的 join 算法，支持所有join 类型和严格性设置。该算法可能会受到高内存使用量的限制。此外，从 join 的右侧表创建内存哈希表是单线程的，如果右侧表非常大，则可能成为 join 执行时间的瓶颈。
• Parallel hash join 通过并发构建多个哈希表，可以更快地处理大型右侧表，但它需要更多的内存。
• Grace hash join 是一个不受内存限制的版本，它将数据临时溢出到磁盘，而无需对数据进行任何排序。这克服了其他非内存限制的 ClickHouse join 算法的一些性能挑战，这些算法将数据临时溢出到磁盘，但需要事先对数据进行排序。

ClickHouse 提供了两种额外的基于外部排序的非内存限制的 join 算法

• Full sorting merge join 基于内存或外部排序，可以利用连接表的物理行顺序，并跳过排序阶段。在这种情况下，join 性能可以与上面图表中的一些 hash join 算法相媲美，同时通常需要显著更少的内存。
• Partial merge join 针对连接大型表时最小化内存使用而优化，并且始终首先通过外部排序完全排序右表。左表也始终进行排序，按块在内存中排序。如果左表的物理行顺序与 join 键排序顺序匹配，则 join 匹配过程将更有效率。

join 算法的选择主要取决于三个因素

• 性能
• 内存
• Join 类型支持

以下三个部分提供了关于这些因素的指导。

除了上面的概述图表外，当主要标准是以尽可能快的速度执行 join 时，您可以使用此决策树来选择正确的 join 算法：

① 如果可以将右侧表的数据预加载到内存中的低延迟键值数据结构中，例如字典，并且如果 join 键与底层键值存储的键属性匹配，并且如果LEFT ANY JOIN 语义足够 - 那么direct join是适用的，并且提供了最快的方法。

② 如果您的表的物理行顺序与 join 键排序顺序匹配，则取决于情况。在这种情况下，full sorting merge join跳过排序阶段，从而显著减少内存使用量，并且，根据数据大小和 join 键值分布，执行时间比某些 hash join 算法更快。但是，如果 ③ 右表可以放入内存，即使有 parallel hash join 的额外内存使用开销，那么此算法或 hash join 可能会更快。这取决于数据大小、数据类型和 join 键列的值分布。

④ 如果右表无法放入内存，则再次取决于情况。ClickHouse 提供了三种非内存限制的 join 算法。这三种算法都暂时将数据溢出到磁盘。Full sorting merge join 和 partial merge join 需要事先对数据进行排序。Grace hash join 从数据构建哈希表。根据数据量、数据类型和 join 键列的值分布，可能存在从数据构建哈希表比排序数据更快的情况。反之亦然。

Partial merge join 针对连接大型表时最小化内存使用而优化，但牺牲了 join 速度，join 速度相当慢。当左表的物理行顺序与 join 键排序顺序不匹配时，尤其如此。

Grace hash join 是三种非内存限制的 join 算法中最灵活的一种，通过其 grace_hash_join_initial_buckets 设置，可以在内存使用量和 join 速度之间实现良好的控制。根据数据量，当选择的buckets数量使得两种算法的内存使用量大致对齐时，grace hash 可能更快或更慢于 partial merge 算法。当 grace hash join 的内存使用量配置为与 full sorting merge 的内存使用量大致对齐时，在我们的测试运行中，full sorting merge 始终更快。

三种非内存限制算法中哪种最快取决于数据量、数据类型和 join 键列的值分布。始终最好使用真实数据量的真实数据运行一些基准测试，以确定哪种算法最快。

如果您想优化 join 以获得最低的内存使用量而不是最快的执行时间，那么您可以使用此决策树：

① 如果您的表的物理行顺序与 join 键排序顺序匹配，那么 full sorting merge join 的内存使用量是最低的。此外，由于排序阶段被禁用，因此还具有良好的 join 速度的额外好处。

② 可以通过配置大量的buckets来调整 grace hash join 以获得非常低的内存使用量，但会牺牲 join 速度。partial merge join 有意使用少量的内存。full sorting merge join 在启用外部排序的情况下，通常比 partial merge join 使用更多的内存（假设行顺序与键排序顺序不匹配），但 join 执行时间明显更好。

选择正确的 join 算法不仅要考虑执行速度和内存消耗因素。这还取决于您的所需join 类型是否受 join 算法支持。为此，我们创建了这个概述图表：

我们现在将比较所有 ClickHouse join 算法的执行时间和峰值内存消耗。

我们将使用我们在第二篇文章中介绍的表。

对于所有 join 查询运行，我们使用 max_threads 的默认设置。ClickHouse Cloud 节点执行查询具有 30 个 CPU 核心（和 120 GB 的主内存），因此 max_threads 默认设置为 30。用于查询运行的 ClickHouse 版本为 23.5.1。

我们使用不同的 join 算法设置，在 join 的右侧运行具有较大表的相同 join 查询

SELECT *
FROM actors AS a
JOIN roles AS r ON a.id = r.actor_id
FORMAT `Null`
SETTINGS join_algorithm = ...;

作为提醒，在之前的文章中，我们使用了 imdb_large 数据库中的 actors 和 roles 表。下面的查询列出了每个表中的行数和未压缩数据量

SELECT
    table,
    formatReadableQuantity(sum(rows)) AS rows,
    formatReadableSize(sum(data_uncompressed_bytes)) AS data_uncompressed
FROM system.parts
WHERE (database = 'imdb_large') AND active
GROUP BY table
ORDER BY table ASC;

┌─table──┬─rows───────────┬─data_uncompressed─┐
│ actors │ 1.00 million   │ 21.81 MiB         │
│ roles  │ 100.00 million │ 2.63 GiB          │
└────────┴────────────────┴───────────────────┘

为了进一步比较 join 算法，我们生成了一个更大的 imdb_xlarge 数据库

SELECT
    table,
    formatReadableQuantity(sum(rows)) AS rows,
    formatReadableSize(sum(data_uncompressed_bytes)) AS data_uncompressed
FROM system.parts
WHERE (database = 'imdb_xlarge') AND active
GROUP BY table
ORDER BY table ASC;

┌─table──┬─rows───────────┬─data_uncompressed─┐
│ actors │ 100.00 million │ 2.13 GiB          │
│ roles  │ 1.00 billion   │ 26.33 GiB         │
└────────┴────────────────┴───────────────────┘

在以下部分中，我们将展示图表，比较示例查询在两个数据库的表上使用每种 join 算法的运行情况。

请注意，我们对 direct join 算法使用单独的图表，因为它仅与类似的、内存限制的非排序算法（如 hash 和 parallel hash）进行比较才有意义。正如在之前的文章中提到的，使用字典支持的右侧表的 direct join 实际上也是 LEFT ANY JOIN

SELECT *
FROM actors AS a
LEFT ANY JOIN roles AS r ON a.id = r.actor_id
FORMAT `Null`
SETTINGS join_algorithm = ...;

下图总结了使用imdb_large 表的相同示例 join 查询的峰值内存使用量和执行时间，其中

• 较大的表在 join 的右侧
• 不同的 join 算法设置
• 具有 30 个 CPU 核心 的节点和 max_threads 的默认设置 30

请注意，10 次查询运行按执行时间排序，从图表左侧最快的查询运行开始：

对于我们的示例表，最快的 join 算法（参见 ① 和 ②）使用了最多的内存。③ full sorting merge 是一个明显的例外。当可以跳过排序阶段，因为表在磁盘上的物理行顺序与 join 键排序顺序匹配时，full sorting merge 的执行时间变得具有竞争力（或更好 - 请参见下面的下一个图表），与 hash join 算法相比，同时需要显著更少的内存。在这种情况下，因为来自两个表的数据是按块和按顺序流经查询引擎，所以只有少数数据块同时在内存中用于合并。

对于 ④ 两个连接表的内存排序，full sorting merge join 具有更高的内存消耗。对于 ⑤ 外部排序（排序数据溢出到磁盘而不是内存排序），内存消耗降低，但执行速度降低。

Grace hash 是三种非内存限制的 join 算法之一，它们暂时将数据溢出到磁盘以减少内存消耗。与其他两种算法 - full sorting merge 和 partial merge - 相比，grace hash 允许您根据配置的 buckets 数量来控制其内存使用量。我们有兴趣比较 grace hash 在使用与其他两种非内存限制算法大致相同和更少的内存量时的 join 速度。为此，我们使用三种不同的 bucket 数量运行 grace hash。在运行 ⑥ 中使用 4 个 buckets，我们将 grace hash 内存使用量与 full sorting merge 运行 ⑤ 对齐。在这种情况下，对于连接我们的两个示例表，grace hash 比 full sorting merge 慢。在运行 ⑦ 中使用 8 个 buckets，我们将内存使用量与 ⑨ 中的 partial merge 运行大致对齐。在这里，grace hash 运行速度快了两倍。额外的运行 ⑧ 使用 32 个 buckets 将内存使用量降低到 partial merge 运行以下，同时仍然运行得更快。

对于连接我们的示例表，partial merge 运行（参见 ⑨ 和 ⑩）是最慢的。请记住，partial merge join 完全排序右表，并将其排序后的块与最小-最大索引文件一起临时存储到磁盘中。然后，它排序并比较左表的每个块与磁盘上右表的排序块，同时利用最小-最大索引来跳过不匹配的块。对于我们的示例表，这在内存方面是高效的，但速度很慢。当左表的物理行顺序与 join 键排序顺序不匹配时，在运行 ⑩ 中尤其如此。

总的来说，我们可以看到，在识别 join 匹配之前显式排序表在执行时间方面比仅从其中一个表构建哈希表更昂贵。

但是，请记住，我们仅基准测试了在一个特定的 imdb 数据集上的 join。根据数据量、数据类型和 join 键列的值分布，可能存在数据块排序比构建哈希表更快的情况。例如，请参见下图。

下图总结了当连接的表来自 imdb_xlarge 数据库时的查询运行：

与上一个图表一样，parallel hash join 运行 ① 是最快的，但也使用了最多的内存。与上一个图表不同，当连接来自 imdb_xlarge 数据库的两个更大的表时，full sorting merge 运行 ②、③ 和 ④ 比 hash join 运行 ⑤ 更快，同时使用更少的峰值主内存。如前所述，从 hash join 的右侧表创建内存哈希表是单线程的，如果右侧表非常大，显然会成为瓶颈。

当 ⑥ 中具有 8 个 buckets 的 grace hash 运行的内存使用量与 ④ 中具有外部排序的 full sorting merge 运行大致对齐时，与上一个图表一样，对于连接我们的两个示例表，grace hash 比 full sorting merge 慢。在运行 ⑧ 中，内存使用量与 partial merge 运行（参见 ⑦ 和 ⑨）的内存使用量大致对齐，具有 64 个 buckets，这次与上一个图表相反，partial merge join 比 grace hash join 快。对于我们示例中具有 10 亿行的右侧表，排序块的构建和溢出以及基于最小-最大索引的扫描 (partial_merge) 比构建和溢出以及扫描 64 个哈希表 (具有 64 个 buckets 的 grace_hash) 快。partial merge 还受益于左表按 join 键排序的事实，这使得能够基于最小-最大索引有效地扫描我们非常大的右表的排序块。

但是，当左表的物理行顺序在运行 ⑨ 中与 join 键排序顺序不匹配时，来自右表的排序块的最小-最大索引帮助不大，并且在最坏的情况下，实际上，在两个表的块之间创建了笛卡尔积：对于左表的每个块，都从磁盘加载了右表的大量排序块。显然，这导致了非常高的执行时间，特别是对于非常大的表。

下图总结了 示例 LEFT ANY JOIN 查询在 imdb_large 数据库上的峰值内存使用量和执行时间，其中

• 较大的表在 join 的右侧
• 不同的 join 算法设置
• 具有 30 个 CPU 核心 的节点和 max_threads 的默认设置 30，以及

4 次查询运行按执行时间排序，从图表左侧最快的查询运行开始：

direct join 是最快的。① 对于由具有 flat 内存布局的字典支持的右侧表，该算法比 ④ hash join 快约 25 倍，比 ③ parallel hash 快约 15 倍，比 ② 使用由具有 hashed 内存布局的字典支持的右侧表的 direct join 快约 2.5 倍。无论字典布局类型如何，与 hash 算法运行相比，总体峰值内存消耗都更低。

下图总结了当连接的表来自 imdb_xlarge 数据库时，direct join 算法的比较运行：

① 由具有 flat 内存布局的字典支持的右侧表的 direct join 算法在约 1 秒内连接来自左表的 1 亿行。这真快！这比 ④ hash 算法快约 32 倍，比 ③ parallel hash 算法快约 22 倍，比 ② 使用由具有 hashed 内存布局的字典支持的右侧表的 direct join 快 4 倍。与上一个图表一样，direct join 运行的总体峰值内存消耗低于 hash 算法运行。

这结束了我们对 ClickHouse join 算法的探索。

在我们的下一个 join 系列中，我们将探索 ClickHouse 中的分布式 join 执行，敬请期待！