选择正确的连接算法

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

• ClickHouse 支持的连接类型
• ClickHouse 连接的内部机制 - 哈希连接、并行哈希连接、Grace 哈希连接
• ClickHouse 连接的内部机制 - 全排序合并连接、部分合并连接
• ClickHouse 连接的内部机制 - 直接连接

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

到目前为止，ClickHouse 为其开发了以下 6 种连接算法：

• 直接连接
• 哈希连接
• 并行哈希连接
• Grace 哈希连接
• 全排序合并连接
• 部分合并连接

这些算法决定了连接查询的规划和执行方式。默认情况下，ClickHouse 使用直接连接或哈希连接算法，具体取决于使用的连接类型和严格性设置以及连接表的引擎。或者，ClickHouse 可以配置为自适应地选择并在运行时动态更改要使用的连接算法，具体取决于资源的可用性和使用情况：当 join_algorithm 设置为 auto 时，ClickHouse 首先尝试哈希连接算法，如果该算法的内存限制被违反，则算法会动态切换到部分合并连接。您可以通过跟踪日志观察选择了哪种算法。ClickHouse 还允许用户自己指定所需的连接算法。该图表根据其相对内存消耗和执行时间概述了 ClickHouse 连接算法：

直接连接是 ClickHouse 最快的连接算法，适用于右侧表的底层存储支持低延迟键值请求，并且 LEFT ANY JOIN 语义足够时。尤其是对于大型右侧表，直接连接在执行时间方面明显优于所有其他 ClickHouse 连接算法。

三种 ClickHouse 连接算法基于内存中哈希表

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

ClickHouse 提供了两种额外的非内存绑定连接算法，基于外部排序

• 全排序合并连接基于内存中或外部排序，可以利用连接表的物理行顺序和跳过排序阶段。在这种情况下，连接性能可以与上面图表中的一些哈希连接算法相媲美，而通常需要的内存明显更少。
• 部分合并连接针对大型表连接时最小化内存使用进行了优化，始终首先通过外部排序对右侧表进行完全排序。左侧表也总是按块方式在内存中排序。如果左侧表的物理行顺序与连接键排序顺序匹配，则连接匹配过程会更高效。

连接算法的选择主要取决于三个因素：

• 性能
• 内存
• 连接类型支持

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

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

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

② 如果您表的物理行顺序与联接键排序顺序匹配，则取决于情况。在这种情况下，完全排序合并联接跳过排序阶段，从而显着减少内存使用量，并且根据数据大小和联接键值分布，更快执行时间比一些哈希联接算法。但是，如果③右表适合内存，即使有额外的内存使用开销并行哈希联接，那么此算法或哈希联接可能会更快。这取决于数据大小、数据类型和联接键列的值分布。

④ 如果右表不适合内存，则再次取决于情况。ClickHouse 提供三种非内存绑定联接算法。所有这三种算法都会将数据临时溢出到磁盘。完全排序合并联接和部分合并联接需要先对数据进行排序。Grace 哈希联接则是在数据中构建哈希表。根据数据量、数据类型和联接键列的值分布，可能存在从数据中构建哈希表比排序数据更快的场景。反之亦然。

部分合并联接针对在联接大型表时最大限度地减少内存使用量进行了优化，但以联接速度非常慢为代价。当左表的物理行顺序与联接键排序顺序不匹配时，尤其如此。

Grace 哈希联接是三种非内存绑定联接算法中最灵活的算法，它通过其grace_hash_join_initial_buckets设置提供了对内存使用量与联接速度的良好控制。根据数据量，grace 哈希可以更快或更慢比部分合并算法，当桶的数量选择得当，以使两种算法的内存使用量大致对齐时。当 grace 哈希联接的内存使用量配置为与完全排序合并的内存使用量大致对齐时，在我们的测试运行中，完全排序合并始终更快。

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

如果您想优化联接以实现最低内存使用量而不是最快的执行时间，则可以使用此决策树：

① 如果您表的物理行顺序与联接键排序顺序匹配，那么完全排序合并联接的内存使用量是尽可能低的。此外，由于排序阶段已禁用，因此具有良好的联接速度。

② Grace 哈希联接可以通过配置大量桶来调整为非常低的内存使用量，但以联接速度为代价。部分合并联接故意使用少量主内存。启用外部排序的完全排序合并联接通常使用更多内存比部分合并联接（假设行顺序与键排序顺序不匹配），但具有显着更好的联接执行时间。

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

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

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

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

我们使用不同的联接算法设置运行相同的联接查询，其中较大的表位于联接的右侧。

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          │
└────────┴────────────────┴───────────────────┘

为了进一步比较联接算法，我们生成了一个更大的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         │
└────────┴────────────────┴───────────────────┘

在下一节中，我们将展示图表，比较使用每个联接算法在两个数据库的表上运行示例查询的结果。

请注意，我们对直接联接算法使用单独的图表，因为它只有与类似的、内存绑定的非排序算法（如哈希和并行哈希）进行比较才有意义。如上一篇文章中所述，使用字典支持的右侧表进行的直接联接实际上也是一个 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表进行相同的示例联接查询的峰值内存使用量和执行时间，其中

• 较大的表位于联接的右侧
• 使用不同的联接算法设置
• 一个具有30 个 CPU 内核的节点，max_threads的默认设置为 30

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

对于我们的示例表，最快的联接算法（见①和②）使用最多的内存。完全排序合并是一个显著的例外。当排序阶段可以跳过，因为表在磁盘上的物理行顺序与联接键排序顺序匹配时，完全排序合并的执行时间将变得具有竞争力（或更好 - 请参见下面的下一张图表），同时需要明显更少的内存。在这种情况下，由于来自两个表的数据通过查询引擎分块并按顺序进行流式传输，因此一次只有少数数据块处于内存中以进行合并。

对于④对两个联接表的内存内排序，完全排序合并联接具有更高的内存消耗。对于⑤外部排序（排序数据溢出到磁盘而不是内存内排序），内存消耗会降低，但以执行速度为代价。

Grace 哈希是三种非内存绑定联接算法之一，它们会将数据临时溢出到磁盘以减少内存消耗。与另外两种算法（完全排序合并和部分合并）不同，grace 哈希允许您根据配置的桶数量来控制其内存使用量。我们有兴趣比较 grace 哈希在使用与另外两种非内存绑定算法相同和更少内存量时的联接速度。为此，我们使用三种不同的桶数量来运行 grace 哈希。在使用 4 个桶的运行⑥中，我们使 grace 哈希内存使用量与完全排序合并运行⑤对齐。在这种情况下，对于联接我们的两个示例表，grace 哈希比完全排序合并慢。在使用 8 个桶的运行⑦中，我们使内存使用量与部分合并运行⑨大致对齐。在这里，grace 哈希运行速度快了两倍。使用 32 个桶的额外运行⑧将内存使用量降低到低于部分合并运行，同时仍然运行得更快。

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

通常，我们可以看到，在确定联接匹配之前显式排序表比仅从其中一个表构建哈希表在执行时间方面更昂贵。

但是，请记住，我们只对一个特定的 IMDB 数据集进行了联接基准测试。根据数据量、数据类型和联接键列的值分布，可能存在数据块排序比构建哈希表更快的场景。例如，请参见以下图表。

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

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

当grace 哈希运行⑥（使用 8 个桶）的内存使用量与完全排序合并运行④（使用外部排序）的内存使用量大致对齐时，与上一个图表一样，对于联接我们的两个示例表，grace 哈希比完全排序合并慢。当内存使用量与部分合并运行（见⑦和⑨）的内存使用量在运行⑧（使用 64 个桶）中大致对齐时，这次，与上一个图表相反，部分合并联接比 grace 哈希联接快。对于我们的示例右侧表（包含 10 亿行），构建和溢出排序后的块以及基于最小-最大索引的扫描（部分合并）比构建和溢出以及扫描 64 个哈希表（使用 64 个桶的 grace 哈希）快。部分合并还受益于左表按联接键排序，这使得能够高效地基于最小-最大索引扫描我们非常大的右侧表的排序后的块。

然而，当左表中的物理行顺序不匹配运行⑨中的连接键排序顺序时，右表中排序块的最小值-最大值索引的帮助作用就不那么大了，在最坏情况下，实际上，会在两个表的块之间创建交叉积：对于左表的每个块，都会从磁盘加载右表中的一组很大的排序块。显然，会导致非常高的执行时间，尤其是在处理非常大的表时。

下表汇总了相同示例LEFT ANY JOIN 查询 在imdb_large 数据库上的峰值内存使用率和执行时间，

• 较大的表位于联接的右侧
• 使用不同的联接算法设置
• 使用一个具有30 个 CPU 内核的节点，并使用默认设置将max_threads设置为 30，

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

direct 连接的速度已经足够快了。① 当右侧表由具有flat 内存布局的字典支持时，该算法比④ hash 连接快约 25 倍，比③ parallel hash 快约 15 倍，比② 使用具有hashed 内存布局的字典支持的右侧表的直接连接快约 2.5 倍。无论字典布局类型如何，与哈希算法运行相比，总的峰值内存消耗都更低。

下表汇总了连接表来自imdb_xlarge 数据库时的直接连接算法比较运行结果：

① 使用具有flat 内存布局的字典支持的右侧表的direct 连接算法在约 1 秒内连接了左侧表的 1 亿行。这很快！这比④ hash 算法快约 32 倍，比③ parallel hash 算法快约 22 倍，比② 使用具有hashed 内存布局的字典支持的右侧表的直接连接快 4 倍。与上一张图表一样，直接连接运行的总的峰值内存消耗与哈希算法运行相比更低。

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

在我们接下来的连接系列中，我们将探索 ClickHouse 中的分布式连接执行，敬请关注！