此博客文章是系列的一部分
- ClickHouse 支持的联接类型
- ClickHouse 联接的幕后 - 哈希联接、并行哈希联接、Grace 哈希联接
- ClickHouse 联接的幕后 - 全排序合并联接、部分合并联接
- 选择正确的联接算法
这篇文章将结束我们对为 ClickHouse 开发的 6 种不同联接算法的探索。作为提醒：这些算法决定联接查询的计划和执行方式。ClickHouse 可以配置为 自适应 地选择和动态更改在运行时使用的联接算法，具体取决于资源可用性和使用情况。但是，ClickHouse 也允许用户 指定 他们自己想要的联接算法。此图表概述了这些算法，基于它们的相对内存消耗和执行时间：
在我们的 第二篇文章 中，我们详细描述并 比较 了上面图表中基于内存中 哈希表 的三种 ClickHouse 联接算法。
作为提醒：**哈希联接** 和 **并行哈希联接** 速度快，但内存受限。来自右侧表中的联接数据需要适合内存。**Grace 哈希联接** 是一个非内存受限版本，它将数据临时溢出到磁盘，而无需对数据进行任何排序。这克服了其他联接算法的性能挑战，这些算法将数据溢出到磁盘，并需要对数据进行预先排序。
在 第三篇文章 中，我们探索并 比较 了上面图表中基于 外部排序 的两种算法。
作为提醒：**全排序合并联接** 是非内存受限的，基于内存或外部排序，可以利用联接表的 物理行顺序 并跳过排序阶段。在这种情况下，联接性能可以与上面图表中的一些 哈希联接算法 相媲美，同时通常只需要少得多的主内存。**部分合并联接** 针对在联接大型表时最大限度地减少内存使用进行了优化，并且始终首先通过外部排序对右侧表进行完全排序。左侧表也始终按块进行内存中排序。如果左侧表的物理行顺序与联接键排序顺序匹配，则联接匹配过程将更加高效地运行。
我们将最好的留到最后，并将通过描述上面图表中 ClickHouse 最快的联接算法来结束我们对 ClickHouse 联接算法的探索。
- 直接联接
当右侧表的底层 存储 支持低延迟 键值 请求时，可以直接应用直接联接算法。特别是对于大型右侧表，直接联接以显着改进的执行时间击败了所有其他 ClickHouse 联接算法。
测试设置
我们使用与我们在 第二篇文章 中介绍的相同的两个表和相同的 ClickHouse Cloud 服务实例。
对于所有示例查询运行，我们使用 max_threads 的默认设置。执行查询的节点有 30 个 CPU 内核，因此默认的 max_threads 设置为 30。对于所有 查询管道 可视化，为了简洁和易读，我们使用 max_threads = 2 设置人工限制了 ClickHouse 查询管道中使用的并行级别。
直接联接
描述
当右侧表的底层存储支持低延迟键值请求时，可以直接应用直接联接算法。ClickHouse 有三个提供此功能的 表引擎：Join（基本上是一个预先计算的 哈希表）、EmbeddedRocksDB 和 Dictionary。我们将在本文中基于字典描述直接联接算法，但所有三个引擎的机制都是相同的。
字典 是 ClickHouse 的一个 关键功能，它提供了来自各种内部和外部 来源 的数据的内存中 键值 表示，针对超低延迟查找查询进行了优化。
这在各种场景中非常有用，例如，为了在不减慢摄取过程的情况下动态丰富摄取的数据，以及为了提高查询的整体性能，特别是 JOIN 的性能会得到提升。
我们在下面草拟了直接联接算法的 查询管道：
直接联接算法要求右侧表由字典支持，以便来自该表的要联接的数据以低延迟键值数据结构的形式已存在于内存中。然后，① 所有来自左侧表的数据通过 2 个流（因为 max_threads = 2）并行流入查询引擎，并且行通过两个联接阶段通过对右侧表的基础字典进行查找来并行联接 ②。
支持的联接类型
仅支持 LEFT ANY 联接 类型。请注意，联接键需要与底层键值存储的键属性匹配。
示例
为了演示直接连接，我们需要首先创建一个字典。为此，我们需要选择一个布局，它决定了字典内容在内存中的存储方式。我们将使用flat选项，为了比较，也使用hashed布局。两种布局都需要关键属性的数据类型与UInt64类型兼容。flat布局在所有布局选项中提供最佳性能，并分配一个内存中的数组，该数组的大小与关键属性的最大值一样大。例如，如果最大值为 100k，那么数组将有 100k 个条目。这种数据布局允许使用 O(1) 时间复杂度 进行极快的键值查找，因为只需要简单的数组偏移量查找。偏移量仅仅是提供键的值，数组中该偏移量位置的条目包含相应的数值。这非常适合我们的演员和角色数据，在源表中（分别为 id 和 actor_id），关键列的值是密集且单调递增的，从 0 开始。因此，每个分配的数组条目都会被使用。使用 hashed 布局，字典内容存储在哈希表中。hashed 布局的适用性更广。例如，对于非密集的关键属性值（不从 0 开始），不会在内存中分配不必要的空间。然而，正如我们稍后会看到的，访问速度会慢 2 到 5 倍。
我们创建一个具有 flat 布局的字典，它将角色表的内容完全加载到内存中，以便进行低延迟的键值查找。我们使用 actor_id 作为关键属性。请注意，我们使用 max_array_size 设置来指定初始和最大数组大小（默认值为 500,000 太小了）。我们还通过将 LIFETIME 设置为 0 来禁用字典内容更新
CREATE DICTIONARY imdb_large.roles_dict_flat
(
created_at DateTime,
actor_id UInt32,
movie_id UInt32,
role String
)
PRIMARY KEY actor_id
SOURCE(CLICKHOUSE(db 'imdb_large' table 'roles'))
LIFETIME(0)
LAYOUT(FLAT(INITIAL_ARRAY_SIZE 1_000_000 MAX_ARRAY_SIZE 1_000_000));
接下来，我们创建一个具有 hashed 布局的类似字典
CREATE DICTIONARY imdb_large.roles_dict_hashed
(
created_at DateTime,
actor_id UInt32,
movie_id UInt32,
role String
)
PRIMARY KEY actor_id
SOURCE(CLICKHOUSE(db 'imdb_large' table 'roles'))
LIFETIME(0)
LAYOUT(hashed());
请注意，在ClickHouse Cloud 中，字典将自动在所有节点上创建。对于 OSS，如果使用Replicated 数据库，则可以实现此行为。其他配置需要手动在所有节点上创建字典，或者使用ON CLUSTER 子句。
我们查询dictionaries 系统表 以检查一些指标
SELECT
name,
status,
formatReadableSize(bytes_allocated) AS memory_allocated,
formatReadableTimeDelta(loading_duration) AS loading_duration
FROM system.dictionaries
WHERE startsWith(name, 'roles_dict_')
ORDER BY name;
┌─name──────────────┬─status─┬─memory_allocated─┬─loading_duration─┐
│ roles_dict_flat │ LOADED │ 1.52 GiB │ 12 seconds │
│ roles_dict_hashed │ LOADED │ 128.00 MiB │ 6 seconds │
└───────────────────┴────────┴──────────────────┴──────────────────┘
loading_duration 列显示将源表内容加载到字典的内存布局中所需的时间。status 表示加载已完成。我们可以看到为字典分配了多少主内存空间。
使用上述字典 DDL 创建字典会自动创建一个表，该表使用字典表引擎，由字典支持。我们可以通过查询tables 系统表来验证这一点
SELECT
name,
engine
FROM system.tables
WHERE startsWith(name, 'roles_dict_')
ORDER BY name;
┌─name──────────────┬─engine─────┐
│ roles_dict_flat │ Dictionary │
│ roles_dict_hashed │ Dictionary │
└───────────────────┴────────────┘
使用此表，字典可以作为一流的表实体进行处理，并且可以使用熟悉的 SELECT 子句直接读取数据。
请注意，与普通的 (MergeTree 引擎系列) ClickHouse 表不同，关键属性在字典中是（自动）唯一的。例如，角色表包含许多具有相同 actor_id 值的行，因为通常演员/女演员会扮演多个角色。当这些行加载到字典中，使用 actor_id 作为关键属性时，具有相同键值的行会相互覆盖。实际上，只有为特定 actor_id 插入的最后一行数据包含在字典中。
我们可以通过从字典的 roles 源表和自动创建的字典表中选择计数来验证这一点
SELECT formatReadableQuantity(count()) as count FROM roles;
┌─count──────────┐
│ 100.00 million │
└────────────────┘
SELECT formatReadableQuantity(count()) as count FROM roles_dict_flat;
┌─count────────┐
│ 1.00 million │
└──────────────┘
100 万正是 actors 表中唯一演员的数量。这意味着角色字典包含每个演员/女演员的一个角色的数据
SELECT formatReadableQuantity(count()) as count FROM actors;
┌─count────────┐
│ 1.00 million │
└──────────────┘
现在，我们使用字典来用 roles 表中的信息丰富 actors 表中的行。请注意，我们使用dictGet 函数来执行低延迟的键值查找。对于 actors 表中的每一行，我们使用 id 列的值在字典中进行查找，并请求 created_at、movie_id 和 role 值，以元组的形式
WITH T1 AS (
SELECT
id,
first_name,
last_name,
gender,
dictGet('roles_dict_flat', ('created_at', 'movie_id', 'role'), id) as t
FROM actors)
SELECT
id,
first_name,
last_name,
gender,
id AS actor_id,
t.1 AS created_at,
t.2 AS movie_id,
t.3 AS role
FROM T1
LIMIT 1
FORMAT Vertical;
Row 1:
──────
id: 393216
first_name: Wissia
last_name: Breitenreiter
gender: F
actor_id: 393216
created_at: 2023-05-12 13:03:09
movie_id: 373614
role: Gaston Binet
1 row in set. Elapsed: 0.019 sec. Processed 327.68 thousand rows, 12.74 MB (17.63 million rows/s., 685.25 MB/s.)
请注意，如果字典不包含特定演员 id 值的键条目，则会返回为请求的属性配置的默认值。此外，正如上面提到的，字典根据 actor_id 列对加载的数据进行去重，实际上只返回第一个找到的匹配项。因此，上述查询的行为等同于LEFT ANY JOIN.
在 ClickHouse 中，有一种更简单、更紧凑的方式来表达上述查询。我们之前已经展示过，当创建具有特定名称的字典时，ClickHouse 会自动创建一个同名表，该表通过字典表引擎由字典支持。此表允许我们使用带有 direct 连接算法的连接查询来表达与上述查询相同的逻辑
SELECT *
FROM actors AS a
JOIN roles_dict_flat AS r ON a.id = r.actor_id
LIMIT 1
SETTINGS join_algorithm='direct'
FORMAT Vertical;
Row 1:
──────
id: 393216
first_name: Wissia
last_name: Breitenreiter
gender: F
actor_id: 393216
created_at: 2023-05-12 13:03:09
movie_id: 373614
role: Gaston Binet
1 row in set. Elapsed: 0.023 sec. Processed 327.68 thousand rows, 12.74 MB (14.28 million rows/s., 555.30 MB/s.)
在内部，ClickHouse 使用高效的键值查找来实现连接，这些查找指向支持右侧表的字典。这类似于上面使用 dictGet 函数进行查找的查询。我们可以通过内省连接查询的查询计划来验证这一点，使用EXPLAIN PLAN 子句
EXPLAIN PLAN
SELECT *
FROM actors AS a
JOIN roles_dict_flat AS r ON a.id = r.actor_id
SETTINGS join_algorithm='direct';
┌─explain───────────────────────────────────────────────┐
│ Expression ((Projection + Before ORDER BY)) │
│ FilledJoin (JOIN) │
│ Expression ((Convert JOIN columns + Before JOIN)) │
│ ReadFromMergeTree (imdb_large.actors) │
└───────────────────────────────────────────────────────┘
我们可以看到，ClickHouse 使用了一个特殊的FilledJoin 步骤，表示不需要执行任何操作来准备或加载右侧表，因为它的内容已经以非常快的键值查找数据结构的形式存在于内存中。准备好并非常适合执行连接。
为了比较，我们可以内省使用哈希算法的相同连接查询的查询计划
EXPLAIN PLAN
SELECT *
FROM actors AS a
JOIN roles AS r ON a.id = r.actor_id
SETTINGS join_algorithm='hash';
┌─explain──────────────────────────────────────────────────────────────────────────────────────┐
│ Expression ((Projection + Before ORDER BY)) │
│ Join (JOIN FillRightFirst) │
│ Expression (Before JOIN) │
│ ReadFromMergeTree (imdb_large.actors) │
│ Expression ((Joined actions + (Rename joined columns + (Projection + Before ORDER BY)))) │
│ ReadFromMergeTree (imdb_large.roles) │
└──────────────────────────────────────────────────────────────────────────────────────────────
现在，我们看到一个 JOIN FillRightFirst 步骤，表示在执行哈希连接之前，将首先将右侧表的数据加载到内存（到哈希表）中。
现在，我们将比较使用以下方法执行相同连接查询的执行时间：
请注意，如上所述，带有字典支持的右侧表的直接连接实际上是一个LEFT ANY JOIN。为了公平比较，因此，我们将使用这种连接类型来进行使用哈希算法的查询运行。
我们运行哈希连接
SELECT *
FROM actors AS a
LEFT ANY JOIN roles AS r ON a.id = r.actor_id
SETTINGS join_algorithm='hash'
FORMAT Null;
0 rows in set. Elapsed: 1.133 sec. Processed 101.00 million rows, 3.67 GB (89.13 million rows/s., 3.24 GB/s.)
我们运行并行哈希连接
SELECT *
FROM actors AS a
LEFT ANY JOIN roles AS r ON a.id = r.actor_id
SETTINGS join_algorithm='parallel_hash'
FORMAT Null;
0 rows in set. Elapsed: 0.690 sec. Processed 101.00 million rows, 3.67 GB (146.38 million rows/s., 5.31 GB/s.)
我们运行直接连接，右侧表具有底层字典，该字典具有 hashed 内存布局
SELECT *
FROM actors AS a
JOIN roles_dict_hashed AS r ON a.id = r.actor_id
SETTINGS join_algorithm='direct'
FORMAT Null;
0 rows in set. Elapsed: 0.113 sec. Processed 1.00 million rows, 38.87 MB (8.87 million rows/s., 344.76 MB/s.)
最后，我们运行直接连接，右侧表具有底层字典，该字典具有 flat 内存布局
SELECT *
FROM actors AS a
JOIN roles_dict_flat AS r ON a.id = r.actor_id
SETTINGS join_algorithm='direct'
FORMAT Null;
0 rows in set. Elapsed: 0.044 sec. Processed 1.00 million rows, 38.87 MB (22.97 million rows/s., 892.85 MB/s.)
现在，让我们检查最后四次查询运行的运行时统计信息
SELECT
query,
query_duration_ms,
(query_duration_ms / 1000)::String || ' s' AS query_duration_s,
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']) OR arrayExists(t -> startsWith(t, 'imdb_large.roles_dict_'), tables))
ORDER BY initial_query_start_time DESC
LIMIT 4
FORMAT Vertical;
Row 1:
──────
query: SELECT *
FROM actors AS a
JOIN roles_dict_flat AS r ON a.id = r.actor_id
SETTINGS join_algorithm='direct'
FORMAT Null;
query_duration_ms: 44
query_duration_s: 0.044 s
memory_usage: 83.66 MiB
read_rows: 1.00 million
read_data: 37.07 MiB
Row 2:
──────
query: SELECT *
FROM actors AS a
JOIN roles_dict_hashed AS r ON a.id = r.actor_id
SETTINGS join_algorithm='direct'
FORMAT Null;
query_duration_ms: 113
query_duration_s: 0.113 s
memory_usage: 102.90 MiB
read_rows: 1.00 million
read_data: 37.07 MiB
Row 3:
──────
query: SELECT *
FROM actors AS a
LEFT ANY JOIN roles AS r ON a.id = r.actor_id
SETTINGS join_algorithm='parallel_hash'
FORMAT Null;
query_duration_ms: 689
query_duration_s: 0.689 s
memory_usage: 4.78 GiB
read_rows: 101.00 million
read_data: 3.41 GiB
Row 4:
──────
query: SELECT *
FROM actors AS a
LEFT ANY JOIN roles AS r ON a.id = r.actor_id
SETTINGS join_algorithm='hash'
FORMAT Null;
query_duration_ms: 1084
query_duration_s: 1.084 s
memory_usage: 4.44 GiB
read_rows: 101.00 million
read_data: 3.41 GiB
来自第 1 行的直接连接运行，其中右侧表由具有 flat 内存布局的字典支持，比来自第 3 行的并行哈希连接运行快约 15 倍，比来自第 4 行的哈希连接运行快约 25 倍，比来自第 2 行的直接连接运行快约 2.5 倍，其中右侧表由具有 hashed 内存布局的字典支持。非常快！
造成这种情况的主要原因是，右侧表的数据已经存在于内存中。相反，哈希和并行哈希算法需要先将数据加载到内存中。此外，如前所述，具有 flat 布局的字典的内存中数组允许使用 O(1) 时间复杂度进行极快的键值查找，因为只需要简单的数组偏移量查找。
请注意，query_log 系统表中的memory_usage 列不包含字典本身分配的内存。因此，为了进行公平的峰值内存消耗比较，我们需要将字典系统表中的bytes_allocated 列中的相应值添加到直接连接运行的 memory_usage 中 - 请参阅我们对该系统表的查询。我们将在本文的总结部分中进行进一步说明。正如您将看到的，即使将字典的 bytes_allocated 添加到直接连接运行的 memory_usage 中，峰值内存消耗与哈希和并行哈希连接运行相比仍然明显更低。
查询管道
让我们内省具有 max_threads 设置为 2 的直接连接查询的实际查询管道
clickhouse client --host ekyyw56ard.us-west-2.aws.clickhouse.cloud --secure --port 9440 --password <PASSWORD> --database=imdb_large --query "
EXPLAIN pipeline graph=1, compact=0
SELECT *
FROM actors AS a
JOIN roles_dict_flat AS r ON a.id = r.actor_id
SETTINGS max_threads = 2, join_algorithm = 'direct';" | dot -Tpdf > pipeline.pdf
我们使用上述抽象图表中的相同圆圈数字对管道进行了注释，稍微简化了主要阶段的名称，并添加了字典和左侧表，以使两个图表保持一致：
我们可以看到，实际的查询管道与我们上面的抽象版本相匹配。
总结
本文介绍了 ClickHouse 最快的连接算法：**直接连接**。当右侧表的底层存储支持低延迟键值请求时，此算法适用。特别是对于大型右侧表，直接连接在执行时间方面明显优于所有其他 ClickHouse 连接算法。
下表总结并比较了本文中连接查询运行的内存使用情况和执行时间。为此，我们始终在具有 30 个 CPU 内核（因此 max_threads 设置为 30）的节点上运行相同的查询，连接相同的数据，其中较大的表位于右侧：
上面的图表非常清楚。direct 连接的速度是最快的。① 对于由具有 flat 内存布局的字典支持的右侧表，该算法比 hash 连接快约 25 倍，比 parallel hash 快约 15 倍，比 ② 由具有 hashed 内存布局的字典支持的右侧表的直接连接快约 2.5 倍。无论字典布局类型如何，总体峰值内存消耗（其中包括bytes_allocated，用于将字典添加到直接连接运行的memory_usage 中）与哈希算法运行相比更低。
这结束了我们对 6 种 ClickHouse 连接算法的三部分深入探讨。
在本系列的下一篇文章中，我们将总结并直接比较所有 6 种 ClickHouse 连接算法。我们还将提供一个方便的决策树 + 连接类型支持概述，您可以使用它来决定哪种连接算法最适合您的特定场景。
敬请关注！
