DoubleCloud 即将停止运营。通过有限时间免费迁移服务迁移到 ClickHouse。立即联系我们 ->->

博客 / 工程

ClickHouse 内部联接 - 哈希联接、并行哈希联接、Grace 哈希联接

Tom Schreiber

2023年4月20日

立即开始使用 ClickHouse Cloud 并获得 300 美元的积分。要了解有关我们基于用量的折扣的更多信息，请联系我们或访问我们的定价页面。

此博文是系列文章的一部分

在我们之前的博文中，我们回顾了 ClickHouse 中可用的 SQL 联接类型。提醒一下：ClickHouse 提供完整的 SQL 联接支持。

在本博文中，我们将开始探索 ClickHouse 中联接执行的内部机制，以便您可以优化应用程序使用的查询中的联接。在这里，您将了解 ClickHouse 如何将这些经典的联接算法集成到其查询管道中，以便尽可能快地执行联接类型。

ClickHouse旨在快速。ClickHouse 中的查询以高度并行的方式处理，利用当前服务器上可用的所有必要资源，并且在许多情况下，将硬件利用到其理论极限。服务器的 CPU 内核和主内存越多，查询并行执行带来的性能提升就越大。

该查询管道确定每个查询执行阶段的并行级别。

下图显示了 ClickHouse 查询管道如何在具有 4 个 CPU 内核的服务器上处理查询：查询的表数据在 4 个独立且并行的流阶段之间动态分布，这些阶段流式传输数据块方式进入 ClickHouse。由于服务器有 4 个 CPU 内核，因此查询管道的大多数查询处理阶段都由 4 个线程并行执行。

使用的线程数量取决于max_threads设置，默认情况下，该设置设置为 ClickHouse 在其运行的机器上看到的 CPU 内核数。

对于所有查询（包括联接），查询管道确保以高度并行且可扩展的方式处理表数据。

为了确保最大程度地利用资源，ClickHouse 开发了 6 种不同的联接算法。这些算法规定了联接查询的计划和执行方式。ClickHouse 可以配置为自适应地选择并在运行时动态更改要使用的联接算法。具体取决于资源的可用性和使用情况。但是，ClickHouse 也允许用户指定他们自己所需的联接算法。此图表根据其相对内存消耗和执行时间概述了这些算法：

此博文将详细描述和比较上面图表中基于内存中哈希表的三种 ClickHouse 联接算法。

我们将在本博文中探讨**哈希联接**算法为何快速且最通用。对于大型右侧表，**并行哈希联接**算法可能更快，但需要更多内存。哈希联接和并行哈希联接都受内存限制。而**Grace 哈希联接**则是非内存限制版本，它会将数据临时溢出到磁盘。Grace 哈希联接不需要对数据进行任何排序，因此克服了其他将数据溢出到磁盘的联接算法（如（部分）合并联接算法（我们将在第二部分中介绍））的一些性能挑战。

在下一篇文章中，我们将看看上面图表中基于外部排序的两种算法。

我们将把最好的留到最后，并在另一篇博文中完成对 ClickHouse 联接算法的探索，在该博文中，我们将描述上面图表中 ClickHouse 最快的联接算法。

直接联接

对于所有示例查询，我们将使用我们在上一篇博文中介绍的规范化IMDB数据集中的两个表：

为了获得大量可测试数据，我们生成了这些表在新的数据库 imdb_large 中的大版本。

此查询列出了示例表中的行数和未压缩数据量。


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

为了使所有可视化简洁易读，我们使用设置max_threads = 2人为地限制了 ClickHouse 查询管道中使用的并行级别。

但是，对于所有示例查询运行，我们使用max_threads的默认设置。

如上所述，默认情况下，max_threads设置为 ClickHouse 在其运行的机器上看到的 CPU 内核数。这些示例使用ClickHouse Cloud服务，其中单个节点有 30 个 CPU 内核。


SELECT getSetting('max_threads');

┌─getSetting('max_threads')─┐
│                        30 │
└───────────────────────────┘

现在让我们开始探索 ClickHouse 联接算法。我们从最通用的哈希联接算法开始。

内存中的哈希表可以每秒处理2.5亿个完全随机的请求（如果适合CPU缓存，则可以处理超过10亿个请求）。这种非常快速的查找能力使得内存中的哈希表成为ClickHouse中实现连接的自然通用选择，当无法或不切实际地利用表排序时。

哈希连接算法是ClickHouse中可用连接实现中最通用的算法。我们在下面说明了集成到ClickHouse查询管道中的哈希连接算法。

我们可以看到

①来自右侧表的所有数据都被流式传输（由于max_threads=2，因此由2个线程并行），然后ClickHouse用这些数据填充内存中的哈希表。

②来自左侧表的数据被流式传输（由于max_threads=2，因此由2个线程并行），并且③通过在哈希表中查找进行连接。

请注意，因为ClickHouse获取右侧表并为其在RAM中创建哈希表，所以将较小的表放在JOIN的右侧在内存效率上更高。我们将在下面演示这一点。

还要注意，哈希表是ClickHouse中的关键数据结构。根据每个特定的查询，以及对于连接查询，根据连接键列类型和连接严格性，ClickHouse会自动选择30多种变体之一。

所有连接类型和严格性设置都受支持。此外，目前只有哈希连接支持在ON子句中用OR组合的多个连接键。

对于希望更深入研究的读者，源代码包含了关于这些类型和设置如何由哈希连接算法实现的非常详细的描述。

我们使用两次查询运行演示哈希连接算法。

右侧较小的表


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

0 rows in set. Elapsed: 0.817 sec. Processed 101.00 million rows, 3.67 GB (123.57 million rows/s., 4.49 GB/s.)

右侧较大的表


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

0 rows in set. Elapsed: 5.063 sec. Processed 101.00 million rows, 3.67 GB (19.95 million rows/s., 724.03 MB/s.)

我们可以查询query_log 系统表以检查最后两次查询运行的运行时统计信息。


SELECT
    query,
    formatReadableTimeDelta(query_duration_ms / 1000) AS query_duration,
    formatReadableSize(memory_usage) AS memory_usage,
    formatReadableQuantity(read_rows) AS read_rows,
    formatReadableSize(read_bytes) AS read_data
FROM clusterAllReplicas(default, system.query_log)
WHERE (type = 'QueryFinish') AND hasAll(tables, ['imdb_large.actors', 'imdb_large.roles'])
ORDER BY initial_query_start_time DESC
LIMIT 2
FORMAT Vertical;

Row 1:
──────
query:          SELECT *
                FROM actors AS a
                JOIN roles AS r ON a.id = r.actor_id
                FORMAT `Null`
                SETTINGS join_algorithm = 'hash'
query_duration: 5 seconds
memory_usage:   8.95 GiB
read_rows:      101.00 million
read_data:      3.41 GiB

Row 2:
──────
query:          SELECT *
                FROM roles AS r
                JOIN actors AS a ON r.actor_id = a.id
                FORMAT `Null`
                SETTINGS join_algorithm = 'hash'
query_duration: 0 seconds
memory_usage:   716.44 MiB
read_rows:      101.00 million
read_data:      3.41 GiB

正如预期的那样，将较小的actors表放在右侧的连接查询比将较大的roles表放在右侧的连接查询消耗的内存少得多。

请注意，指示的峰值内存使用量为8.95 GiB和716.44 MiB，大于两次查询运行中相应右侧表的未压缩大小2.63 GiB和21.81 MiB。造成这种情况的原因是，哈希表的大小最初是根据连接键列的类型以及特定内部哈希表缓冲区大小的倍数来选择和动态增加的。memory_usage指标计算为哈希表保留的总内存，尽管它可能没有完全填充。

对于两个查询的执行，ClickHouse读取相同数量的总行数（和数据）：来自roles表的1亿行+来自actors表的100万行。但是，将较大的roles表放在右侧的连接查询慢了五倍。这是因为默认的哈希连接对于将右侧表的行插入哈希表不是线程安全的。因此，哈希表的填充阶段以单线程运行。我们可以通过检查实际的查询管道来再次确认这一点。

我们可以使用ClickHouse命令行客户端（快速安装说明在这里）来检查哈希连接查询的ClickHouse查询管道。我们使用EXPLAIN语句打印以DOT图形描述语言描述的查询管道的图形，并使用Graphviz dot以pdf格式渲染图形。


./clickhouse client --host ekyyw56ard.us-west-2.aws.clickhouse.cloud --secure --port 9440 --password  --database=imdb_large --query "
EXPLAIN pipeline graph=1, compact=0
SELECT *
FROM actors a
JOIN roles r ON a.id = r.actor_id
SETTINGS max_threads = 2, join_algorithm = 'hash';" | dot -Tpdf > pipeline.pdf

我们在管道上添加了与上面抽象图中使用的相同圆圈编号，稍微简化了主要阶段的名称，并添加了两个连接的表以使这两个图对齐。

我们可以看到查询管道①以两个并行流式传输阶段（因为max_threads设置为2）开始，用于从右侧表流式传输数据，然后是一个用于填充哈希表的单个填充阶段。另外两个并行流式传输阶段②和两个并行连接阶段③用于从左侧表流式传输和连接数据。

如上所述，默认的哈希连接算法对于将右侧表的行插入哈希表不是线程安全的。因此，在上面的管道中使用了一个调整大小阶段，用于将两个从右侧表流式传输数据的线程减少到一个单线程填充阶段。这可能会成为查询运行时的瓶颈。如果右侧表很大——请参阅我们上面的两次查询运行，其中将大型roles表放在连接右侧的查询慢了五倍。

但是，自从ClickHouse 22.7版本以来，对于大型表，可以通过使用并行哈希算法显著加快从右侧表构建哈希表的过程。

并行哈希连接算法是哈希连接的一种变体，它将输入数据拆分为多个部分以同时构建多个哈希表，从而以更高的内存开销为代价加快连接速度。我们在下面概述了该算法的查询管道。

上图显示了

①来自右侧表的所有数据都被流式传输（由于max_threads = 2，因此由2个线程并行）到内存中。数据被分块流式传输。来自每个流式传输块的行通过对每行的连接键应用哈希函数被拆分为2个桶（max_threads = 2）。我们在上图中用橙色和蓝色表示了这一点。并行地，每个桶使用单个线程填充一个内存中的哈希表。请注意，用于将行拆分为桶的哈希函数与哈希表内部使用的哈希函数不同。

②来自左侧表的数据被流式传输（由于max_threads = 2，因此由2个线程并行），并且步骤①中相同的“桶哈希函数”被应用于每行的连接键以确定相应的哈希表，并且行③通过在相应的哈希表中查找进行连接。

请注意，max_threads设置决定了并发哈希表的数量。我们稍后将通过检查具体的查询管道来演示这一点。

INNER和LEFT连接类型以及除ASOF之外的所有严格性设置都受支持。

我们现在将比较相同查询的哈希算法和并行哈希算法的运行时间和峰值内存消耗。

右侧有较大表的哈希连接


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

0 rows in set. Elapsed: 5.385 sec. Processed 101.00 million rows, 3.67 GB (18.76 million rows/s., 680.77 MB/s.)

右侧有较大表的并行哈希连接


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

0 rows in set. Elapsed: 2.639 sec. Processed 101.00 million rows, 3.67 GB (38.28 million rows/s., 1.39 GB/s.)

我们检查最后两次查询运行的运行时统计信息。


SELECT
    query,
    formatReadableTimeDelta(query_duration_ms / 1000) AS query_duration,
    formatReadableSize(memory_usage) AS memory_usage,
    formatReadableQuantity(read_rows) AS read_rows,
    formatReadableSize(read_bytes) AS read_data
FROM clusterAllReplicas(default, system.query_log)
WHERE (type = 'QueryFinish') AND hasAll(tables, ['imdb_large.actors', 'imdb_large.roles'])
ORDER BY initial_query_start_time DESC
LIMIT 2
FORMAT Vertical;

Row 1:
──────
query:          SELECT *
                FROM actors AS a
                JOIN roles AS r ON a.id = r.actor_id
                FORMAT `Null`
                SETTINGS join_algorithm = 'parallel_hash'
query_duration: 2 seconds
memory_usage:   18.29 GiB
read_rows:      101.00 million
read_data:      3.41 GiB

Row 2:
──────
query:          SELECT *
                FROM actors AS a
                JOIN roles AS r ON a.id = r.actor_id
                FORMAT `Null`
                SETTINGS join_algorithm = 'hash'
query_duration: 5 seconds
memory_usage:   8.86 GiB
read_rows:      101.00 million
read_data:      3.41 GiB

并行哈希连接的速度大约比标准哈希连接快100%，但峰值内存消耗超过了两倍，尽管两个查询读取的行数和数据量以及右侧表的大小相同。

这种更高的内存消耗的原因是查询是在一个具有30个CPU内核的节点上运行的，因此max_threads设置为30。这意味着，正如我们将在下面演示的那样，使用了30个并发哈希表。如前所述，每个哈希表的大小最初是根据连接键列的类型以及特定内部哈希表缓冲区大小的倍数来选择和动态增加的。哈希表很可能没有完全填充，但是memory_usage指标计算为哈希表保留的总内存。

我们提到过max_threads设置决定了并发哈希表的数量。我们可以通过检查具体的查询管道来验证这一点。

首先，我们检查max_threads设置为2的并行哈希连接查询的查询管道。


./clickhouse client --host ekyyw56ard.us-west-2.aws.clickhouse.cloud --secure --port 9440 --password  --database=imdb_large --query "
EXPLAIN pipeline graph=1, compact=0
SELECT *
FROM actors a
JOIN roles r ON a.id = r.actor_id
SETTINGS max_threads = 2, join_algorithm = 'parallel_hash';" | dot -Tpdf > pipeline.pdf

像往常一样，我们在管道上添加了与上面抽象图中使用的相同圆圈编号，稍微简化了主要阶段的名称，并添加了两个连接的表以使这两个图对齐。

我们可以看到，存在两个并发填充阶段，用于并行地用来自右侧表的数据填充两个哈希表。此外，两个并发连接阶段用于连接（以哈希表查找的形式）来自左侧表的数据。

请注意，在上面的查询管道中使用了调整大小阶段，用于定义所有填充阶段和所有连接阶段之间的明确连接：所有连接阶段都应该等到所有填充阶段完成后才能开始。

接下来，我们检查max_threads设置为4的并行哈希连接查询的查询管道。


./clickhouse client --host ekyyw56ard.us-west-2.aws.clickhouse.cloud --secure --port 9440 --password  --database=imdb_large --query "
EXPLAIN pipeline graph=1, compact=0
SELECT *
FROM actors a
JOIN roles r ON a.id = r.actor_id
SETTINGS max_threads = 4, join_algorithm = 'parallel_hash';" | dot -Tpdf > pipeline.pdf

现在，四个并发填充阶段用于并行地用来自右侧表的数据填充四个哈希表。并且四个并发连接阶段用于连接来自左侧表的数据。

原始PR中的测量结果表明，加速与并行度几乎呈线性相关。

上面描述的哈希和并行哈希连接算法都很快，但受内存限制。如果右侧表不适合主内存，ClickHouse将引发OOM异常。在这种情况下，ClickHouse用户可以牺牲性能并使用（部分）合并算法（在下一篇文章中描述），该算法在合并之前将表的(部分)数据排序到外部存储中。

幸运的是，ClickHouse 22.12 引入了另一种称为“grace hash”的连接算法，该算法不受内存限制，但基于哈希表，因此不需要对数据进行任何排序。这克服了（部分）合并算法的一些性能挑战。

该算法利用两阶段方法连接数据。我们的实现与经典算法描述略有不同，以便适应我们的查询管道。下图显示了第一阶段。

① 右表中的所有数据都以块为单位流式传输到内存中（由于max_threads = 2，因此由 2 个线程并行执行）。每个流式传输块中的行通过对每行的连接键应用哈希函数，被分成 3 个桶（因为grace_hash_join_initial_buckets = 3）。我们在上图中用橙色、蓝色和绿色表示了这一点。一个内存中的哈希表用来自第一个（橙色）桶的行填充。右表中另外两个（绿色和蓝色）桶的连接被延迟，并将它们保存到临时存储中。

请注意，如果内存中的哈希表大小超过内存限制（由max_bytes_in_join设置），ClickHouse会动态增加桶的数量并重新计算每行分配的桶。任何不属于当前桶的行都会被刷新并重新分配。

另请注意，ClickHouse将grace_hash_join_initial_buckets的设置值向上取整到最接近的 2 的幂。因此，3 将向上取整为 4，并使用 4 个初始桶。为了便于阅读，我们在图中使用了 3 个桶，并且与使用 4 个桶相比，内部工作原理没有本质区别。

② 左表中的数据由 2 个线程（max_threads = 2）并行流式传输，并对每行的连接键应用与步骤 ① 中相同的“桶哈希函数”来确定相应的桶。与第一个桶对应的行将被③连接（因为相应的哈希表在内存中）。其他桶的连接被延迟，并将它们保存到临时存储中。

步骤 ① 和 ② 的关键在于，“桶哈希函数”将始终将值分配到同一个桶，从而有效地对数据进行分区，并通过分解解决问题。

在第二阶段，ClickHouse处理磁盘上剩余的桶。剩余的桶按顺序处理。以下两个图显示了这一点。第一个图显示了蓝色桶如何首先被处理。第二个图显示了最终绿色桶的处理过程。

① ClickHouse为右侧表数据中的每个桶构建哈希表。

同样，如果 ClickHouse 内存不足，它会动态增加桶的数量。

② 一旦从右侧表桶构建了哈希表，ClickHouse就会流式传输来自相应左侧表桶的数据，并③完成这对数据的连接。

请注意，在此阶段，可能有一些行属于除当前桶之外的其他桶，因为它们是在动态增加桶的数量之前保存到临时存储中的。在这种情况下，ClickHouse会将它们保存到新的实际桶中，并进一步处理它们。

此过程对所有剩余的桶重复进行。

INNER 和 LEFT 连接类型以及除 ASOF 之外的所有严格性设置都受支持。

下面我们比较使用哈希连接和 Grace 哈希连接算法运行相同连接查询的运行时间和峰值内存消耗。

右侧表较大的哈希连接


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

0 rows in set. Elapsed: 5.038 sec. Processed 101.00 million rows, 3.67 GB (20.05 million rows/s., 727.61 MB/s.)

右侧表较大的 Grace 哈希连接


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

0 rows in set. Elapsed: 13.117 sec. Processed 101.00 million rows, 3.67 GB (7.70 million rows/s., 279.48 MB/s.)

我们获取最后两次查询运行的运行时统计信息


SELECT
    query,
    formatReadableTimeDelta(query_duration_ms / 1000) AS query_duration,
    formatReadableSize(memory_usage) AS memory_usage,
    formatReadableQuantity(read_rows) AS read_rows,
    formatReadableSize(read_bytes) AS read_data
FROM clusterAllReplicas(default, system.query_log)
WHERE (type = 'QueryFinish') AND hasAll(tables, ['imdb_large.actors', 'imdb_large.roles'])
ORDER BY initial_query_start_time DESC
LIMIT 2
FORMAT Vertical;

Row 1:
──────
query:          SELECT *
                FROM actors AS a
                JOIN roles AS r ON a.id = r.actor_id
                FORMAT `Null`
                SETTINGS join_algorithm = 'grace_hash', grace_hash_join_initial_buckets = 3
query_duration: 13 seconds
memory_usage:   3.72 GiB
read_rows:      101.00 million
read_data:      3.41 GiB

Row 2:
──────
query:          SELECT *
                FROM actors AS a
                JOIN roles AS r ON a.id = r.actor_id
                FORMAT `Null`
                SETTINGS join_algorithm = 'hash'
query_duration: 5 seconds
memory_usage:   8.96 GiB
read_rows:      101.00 million
read_data:      3.41 GiB

正如预期的那样，哈希连接更快。但是，Grace 哈希连接仅消耗了一半的峰值主内存。

通过增加grace_hash_join_initial_buckets设置，可以进一步降低 Grace 哈希连接的主内存消耗。我们通过使用grace_hash_join_initial_buckets设置为 8 的值重新运行查询来演示这一点。


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

0 rows in set. Elapsed: 16.366 sec. Processed 101.00 million rows, 3.67 GB (6.17 million rows/s., 224.00 MB/s.)

让我们检查最后两次查询运行的运行时统计信息


SELECT
    query,
    formatReadableTimeDelta(query_duration_ms / 1000) AS query_duration,
    formatReadableSize(memory_usage) AS memory_usage,
    formatReadableQuantity(read_rows) AS read_rows,
    formatReadableSize(read_bytes) AS read_data
FROM clusterAllReplicas(default, system.query_log)
WHERE (type = 'QueryFinish') AND hasAll(tables, ['imdb_large.actors', 'imdb_large.roles'])
ORDER BY initial_query_start_time DESC
LIMIT 2
FORMAT Vertical;

Row 1:
──────
query:          SELECT *
                FROM actors AS a
                JOIN roles AS r ON a.id = r.actor_id
                FORMAT `Null`
                SETTINGS join_algorithm = 'grace_hash', grace_hash_join_initial_buckets = 8
query_duration: 16 seconds
memory_usage:   2.10 GiB
read_rows:      101.00 million
read_data:      3.41 GiB

Row 2:
──────
query:          SELECT *
                FROM actors AS a
                JOIN roles AS r ON a.id = r.actor_id
                FORMAT `Null`
                SETTINGS join_algorithm = 'grace_hash', grace_hash_join_initial_buckets = 3
query_duration: 13 seconds
memory_usage:   3.72 GiB
read_rows:      101.00 million
read_data:      3.41 GiB

使用 8 个初始桶运行的 Grace 哈希连接消耗的主内存大约比使用 3 个初始桶运行的 Grace 哈希连接少 70%。为了牺牲更高的执行时间，可以通过增加桶的数量来线性地减少内存消耗。

请注意，如前所述并在下面演示的那样，ClickHouse始终将grace_hash_join_initial_buckets的设置值向上取整到最接近的 2 的幂。因此，grace_hash_join_initial_buckets设置为 3 的查询实际上使用了 4 个初始桶。

我们检查max_threads设置为 2 且grace_hash_join_initial_buckets设置为 3 的 Grace 哈希连接查询的查询管道。


./clickhouse client --host ekyyw56ard.us-west-2.aws.clickhouse.cloud --secure --port 9440 --password  --database=imdb_large --query "
EXPLAIN pipeline graph=1, compact=0
SELECT *
FROM actors AS a
JOIN roles AS r ON a.id = r.actor_id
FORMAT `Null`
SETTINGS max_threads = 2, join_algorithm = 'grace_hash', grace_hash_join_initial_buckets = 3';" | dot -Tpdf > pipeline.pdf

添加的圆圈数字和主要阶段的略微简化的名称以及添加的两个连接表用于与上图中的抽象图保持一致。

我们看到①有两个并行流式传输阶段（max_threads=2），来自右侧表的数据被流式传输到内存中。我们还看到两个并行填充阶段用于填充内存中的哈希表。另外两个并行流式传输阶段②和两个并行连接阶段③用于流式传输和连接来自左侧表的数据。延迟阶段表示某些连接阶段被推迟。

但是，我们无法在查询管道中看到桶的数量，因为桶的创建是动态的，并且取决于内存压力，ClickHouse 会根据需要动态增加桶的数量。所有桶都在Delayed…Transform阶段处理。

为了检查创建和处理的桶的数量，我们需要检查 Grace 哈希连接查询的实际执行，通过要求 ClickHouse 在执行期间将跟踪级日志发送到 ClickHouse 命令行客户端。

我们执行max_threads设置为 2 且grace_hash_join_initial_buckets值为 3 的 Grace 哈希连接查询（注意send_logs_level='trace'设置）。


./clickhouse client --host ea3kq2u4fm.eu-west-1.aws.clickhouse.cloud --secure --password  --database=imdb_large --send_logs_level='trace' --query "
SELECT *
FROM actors AS a
JOIN roles AS r ON a.id = r.actor_id
FORMAT Null
SETTINGS max_threads = 2, join_algorithm = 'grace_hash', grace_hash_join_initial_buckets = 3;"

    ...
... GraceHashJoin: Initialize 4 buckets
... GraceHashJoin: Joining file bucket 0
    ...
... imdb_large.actors ...: Reading approx. 1000000 rows with 2 streams
    ...
... imdb_large.roles ...: Reading approx. 100000000 rows with 2 streams
    ...
... GraceHashJoin: Joining file bucket 1
... GraceHashJoin: Loaded bucket 1 with 250000(/25000823) rows
    ...
... GraceHashJoin: Joining file bucket 2
... GraceHashJoin: Loaded bucket 2 with 250000(/24996460) rows
    ...
... GraceHashJoin: Joining file bucket 3
... GraceHashJoin: Loaded bucket 3 with 250000(/25000742) rows
    ...
... GraceHashJoin: Finished loading all 4 buckets
    ...

现在我们可以看到创建了 4 个（而不是 3 个）初始桶。因为，如前所述，ClickHouse始终将grace_hash_join_initial_buckets的设置值向上取整到最接近的 2 的幂。我们还看到了每个表如何使用 2 个并行流式传输阶段来读取表的行。两个表的第一个对应桶（上述跟踪日志消息中的桶 0）立即连接。

其他 3 个桶被写入磁盘，然后按顺序加载以进行连接。我们看到来自两个表的 100 万行和 1 亿行被均匀地拆分——每个桶分别为 25 万行和约 2500 万行。

为了进行比较，我们执行max_threads设置为 4 且grace_hash_join_initial_buckets值为 8 的 Grace 哈希连接查询。


./clickhouse client --host ea3kq2u4fm.eu-west-1.aws.clickhouse.cloud --secure --password  --database=imdb_large --send_logs_level='trace' --query "
SELECT *
FROM actors AS a
JOIN roles AS r ON a.id = r.actor_id
FORMAT Null
SETTINGS max_threads = 4, join_algorithm = 'grace_hash', grace_hash_join_initial_buckets = 8;"

    ...
... GraceHashJoin: Initialize 8 buckets
... GraceHashJoin: Joining file bucket 0
    ...
... imdb_large.actors ...: Reading approx. 1000000 rows with 4 streams
    ...
... imdb_large.roles ...: Reading approx. 100000000 rows with 4 streams
    ...
...  GraceHashJoin: Joining file bucket 1
...  GraceHashJoin: Loaded bucket 1 with 125000(/12502068) rows
    ...
...  GraceHashJoin: Joining file bucket 2
...  GraceHashJoin: Loaded bucket 2 with 125000(/12498406) rows
    ...
...  GraceHashJoin: Joining file bucket 3
...  GraceHashJoin: Loaded bucket 3 with 125000(/12502699) rows
    ...
...  GraceHashJoin: Joining file bucket 4
...  GraceHashJoin: Loaded bucket 4 with 125000(/12498074) rows
    ...
...  GraceHashJoin: Joining file bucket 5
...  GraceHashJoin: Loaded bucket 5 with 125000(/12498755) rows
    ...
...  GraceHashJoin: Joining file bucket 6
...  GraceHashJoin: Loaded bucket 6 with 125000(/12498054) rows
    ...
...  GraceHashJoin: Joining file bucket 7
...  GraceHashJoin: Loaded bucket 7 with 125000(/12498043) rows
    ...
...  GraceHashJoin: Finished loading all 8 buckets
    ...

我们可以看到创建了 8 个初始桶，并且每个表都使用 4 个并行流式传输阶段来读取表的行。

这篇博文详细描述并比较了 3 种基于内存中哈希表的 ClickHouse 连接算法。

哈希连接算法速度快且最通用，支持所有连接类型和严格性设置，但内存中哈希表的创建是单线程的，如果右侧表非常大，可能会成为瓶颈。

并行哈希连接算法可以通过同时构建多个哈希表来加快右侧表较大的情况下的速度，但需要更多内存。

Grace 哈希连接算法是一种非内存受限版本，它将输入数据分成多个桶，其中一些桶在内存中按顺序处理之前被卸载到磁盘上。

下图总结了所有连接查询运行（max_threads设置为 30 且右侧表较大）的内存消耗和执行时间，这些数据来自本文。