ClickHouse 倒排索引简介

经过长时间的制作，ClickHouse v23.1 发布了一项备受期待的功能——对倒排索引的实验性支持。在这篇博文中，我们不仅将探讨社区对倒排索引如此兴奋的原因，还将详细讨论倒排索引在 ClickHouse 中的工作原理。非常感谢 IBM，他们在过去六个月中开发并贡献了倒排索引的代码。

倒排索引是几十年前发明的，但正是由于像 Google 这样的搜索引擎，大多数人才会在一天中多次与倒排索引交互——通常是在不知情的情况下。倒排索引是核心数据结构，可以在大量文本文档集合中实现快速而强大的搜索。倒排索引背后的思想是编译一个术语数据库，其中包含指向包含这些术语的文档的指针。

让我们看一个小例子，包含四个文档，以便更好地理解倒排索引的工作原理。

CREATE TABLE docs
(
    `key` UInt64,
    `doc` String
)
ENGINE = MergeTree()
ORDER BY key;

INSERT INTO docs VALUES
    (0, 'Sail against the wind'),
    (1, 'Wait and see'),
    (2, 'Sail the seven seas'),
    (3, 'See how the wind blows');

要查找包含术语“wind”的所有文档，我们可以编写以下 SQL 查询

SELECT *
FROM docs
WHERE doc LIKE '%wind%';

┌─key─┬─doc────────────────────┐
│   0 │ Sail against the wind  │
│   3 │ See how the wind blows │
└─────┴────────────────────────┘

2 rows in set. Elapsed: 0.006 sec. 

正如预期的那样，此查询返回第一个和最后一个文档。但是，它很快变得昂贵：我们需要检查列“doc”的每一行是否与搜索词匹配。这意味着搜索的运行时与表大小成正比增长。为了避免这种情况，我们在列 doc 上创建一个倒排索引。由于倒排索引仍处于实验阶段，我们首先需要启用它。一旦倒排索引成为 GA，此步骤将变得多余。

SET allow_experimental_inverted_index = true;

ALTER TABLE docs ADD INDEX inv_idx(doc) TYPE inverted;

ALTER TABLE docs MATERIALIZE INDEX inv_idx;

创建索引时，ClickHouse 将“docs”列中的每个文档拆分为术语列表。默认情况下，拆分是沿着空格完成的，但也可以将文本标记化为 n-gram。生成的索引在概念上看起来像这样

字典（术语）	倒排列表
and	1
against	0
blows	3
how	3
Sail	0, 2
See	3
see	1
seas	1
seven	2
the	0, 2, 3
Wait	1
wind	0, 3

正如我们所看到的，倒排索引将每个术语与“倒排记录”相关联，即包含相应术语的文档的行位置。

倒排索引中的字典通常以可以快速找到术语的方式组织。实现此目的的最简单方法是以字母排序顺序存储术语，并使用二分搜索进行查找。与此相反，ClickHouse 将字典存储为有限状态转换器 (FST)。我们将在下面更详细地讨论 FST。它们的主要优点是可以轻松删除冗余，例如，相邻术语之间的共享前缀。这减少了字典的内存占用并提高了整体吞吐量。

目前不支持但将来可能会添加的字典的进一步有趣的扩展包括以下内容

• 删除不携带语义权重的停用词，如“a”、“and”、“the”等，以及
• 词形还原和词干提取作为特定于语言的技术，用于将单词减少到其语言词根，例如，“walking”变为“walk”，“went”变为“go”，“driving”变为“drive”等。

ClickHouse 还以压缩格式（更具体地说是“roaring bitmap”）存储倒排列表，目的是减少其内存消耗。我们将在下面更深入地探讨倒排列表压缩。在最初的倒排索引版本中，倒排列表引用包含相应术语的文档的行位置。将来可能会使用额外的元数据对其进行扩展，例如

• 与每个倒排记录一起存储的文档频率计数，指示术语在文档中出现的频率。此类信息将使我们能够计算术语频率/逆文档频率 (TF-IDF)，这对于对搜索结果进行排名很有用。
• 词级倒排记录，即术语在文档中的确切位置。此类数据允许回答短语查询，用户在其中搜索多个连续术语（“短语”），而不是单个术语。

如果我们重新运行查询，它将自动使用索引

SELECT * from docs WHERE doc LIKE '%wind%';

┌─key─┬─doc────────────────────┐
│   0 │ Sail against the wind  │
│   3 │ See how the wind blows │
└─────┴────────────────────────┘

2 rows in set. Elapsed: 0.007 sec. 

我们可以使用 EXPLAIN indexes = 1 来验证是否使用了索引

EXPLAIN indexes = 1
SELECT * from docs WHERE doc LIKE '%wind%';

┌─explain─────────────────────────────────────┐
│ Expression ((Projection + Before ORDER BY)) │
│   ReadFromMergeTree (default.docs)          │
│   Indexes:                                  │
│     PrimaryKey                              │
│       Condition: true                       │
│       Parts: 1/1                            │
│       Granules: 1/1                         │
│     Skip                                    │
│       Name: inv_idx                         │
│       Description: inverted GRANULARITY 1   │
│       Parts: 1/1                            │
│       Granules: 1/1                         │
└─────────────────────────────────────────────┘

12 rows in set. Elapsed: 0.006 sec.

让我们首先讨论如何存储倒排列表。正如您在上面的示例中看到的，倒排列表中的倒排记录是单调递增的。此外，现实世界数据中的术语通常以高度倾斜的方式分布。这意味着大多数术语通常只出现在少数文档中，而少数术语出现在许多文档中。倒排索引的传统实现通过结合 delta 编码 和 Golomb（或 Golomb-Rice）编码 来压缩其倒排列表，从而利用这两种属性。这种压缩实现了非常高的压缩率，但压缩和解压缩变得相当慢。

现代倒排列表压缩格式能够在压缩/解压缩性能和压缩率之间取得更好的平衡。ClickHouse 中的倒排索引利用最先进的 roaring bitmaps 格式来压缩倒排列表。此格式的主要思想是将倒排记录表示为位图（例如，[3, 4, 7] 变为 [00011001]），然后将其分成块并存储在专用容器中。

Roaring bitmaps 存储 32 位整数的排序列表，即最大值为约 42 亿。然后，所有可能的整数范围被分成大小相等的 2^16 个整数范围。一个块中的所有整数共享其 16 个最高有效位，而 16 个最低有效位保存在专用容器中，具体取决于该范围内值的分布。可用的容器类型包括数组（对于稀疏分布的值）、位图（对于密集分布的值）和游程编码（RLE，对于具有长连续值运行的数据）。按高 16 位排序的“容器数组”充当容器列表的入口点。此结构通常足够小，可以放入 CPU 缓存中。

在倒排索引的上下文中，能够快速合并和求交两个倒排列表也很重要。当用户搜索多个术语的析取 (OR) 或合取 (AND) 时，这变得必要，例如，SELECT * from docs WHERE doc IN ('wind', 'blows', 'sail')。Roaring bitmaps 在这方面特别出色，因为它们带有优化的算法来联合和求交两种容器类型的每种组合。有关 roaring bitmaps 的更多详细信息，我们请参考此出版物。

现在我们已经仔细研究了倒排列表，让我们将注意力转向字典的压缩。ClickHouse 中的倒排索引使用有限状态转换器 (FST) 来表示字典。大多数人可能不熟悉 FST，但很多人都知道有限状态机。这种类型的自动机具有一组状态和一组状态之间的转换，并且根据最终停留在接受状态还是非接受状态，它们接受或拒绝输入。FST 的工作方式类似，只是状态转换不仅消耗输入，还产生输出。因此，FST 是计算机语言学中用于在两种语言之间进行翻译的流行工具。

在 ClickHouse 的倒排索引中，FST 将术语“翻译”为倒排列表偏移量。上面示例中的 FST 接受术语“See”、“see”、“seas”、“seven”和“wind”。倒排列表偏移量是通过累积每次转换的输出来计算的。例如，术语“seas”产生偏移量 4 + 5 = 9。该图显示了一个压缩的 FST，其中使用 此处 解释的技术删除了公共子字符串。

在演示真实数据集上的倒排索引之前，我们将快速讨论它们的构造和磁盘布局。

倒排索引构造，也称为“倒排”，是一项 CPU 和时间密集型操作。ClickHouse 中的倒排索引实现为二级索引，因此，它们以 part 的粒度存在。在当前的实现中，合并两个 part 会从头开始在新 part 上重新创建倒排索引。将来可能会使用更轻量级的增量索引维护对其进行优化，该维护能够直接合并两个现有索引。目前，已注意限制索引创建的成本。在不同的可能的索引构造方法中，ClickHouse 使用一种策略（“单程内存倒排”），该策略

• 在单程中迭代底层列数据（而不是需要两遍），
• 处理可配置的数据块（而不是分配与底层列大小成比例的内存），以及
• 直接构造索引（而不是将中间文件写入磁盘，然后在后处理步骤中合并这些文件）。

生成的倒排索引是分段的，即由多个较小的子索引组成。每个段对应于原始列的连续行范围。行范围的大小可以不同，但它们的大概大小可以通过参数 max_digestion_size_per_segment 控制。

part 的索引存储为三个文件。

元数据文件是段描述符的数组，每个段描述符包含唯一的段 ID、起始行 ID、字典偏移量和倒排列表偏移量。起始行 ID 表示段的起始行，而字典和倒排列表偏移量指向倒排列表和字典文件中当前段的节的开头。

倒排列表文件包含所有段的倒排列表。一个段可以有多个倒排列表，因为它可能有多个术语。从元数据文件开始，我们可以使用倒排列表偏移量跳转到段的第一个倒排列表。但是由于段内可能有多个术语，我们还需要找到段内的正确倒排列表。

这就是字典文件的用途。它包含每个段的字典（+字典大小），形式为最小化的 FST。在索引查找期间，ClickHouse 将使用元数据文件中的字典和倒排列表偏移量跳转到正确的 FST 和段的倒排列表的开头。然后，它将使用字典文件中的 FST 来计算从段的倒排列表的开头到实际倒排列表的偏移量，并最终解压缩它。由于这种架构，倒排索引永远不会完全读入内存；一次只读取元数据文件、字典文件和倒排列表文件的一部分。

最后，是时候演示倒排索引了。我们使用 Hacker News 数据集，其中包含在 Hacker News 上发布的 2870 万条评论。让我们首先导入数据

CREATE TABLE hackernews
(
    `id` UInt64,
    `deleted` UInt8,
    `type` String,
    `author` String,
    `timestamp` DateTime,
    `comment` String,
    `dead` UInt8,
    `parent` UInt64,
    `poll` UInt64,
    `children` Array(UInt32),
    `url` String,
    `score` UInt32,
    `title` String,
    `parts` Array(UInt32),
    `descendants` UInt32
)
ENGINE = MergeTree
ORDER BY (type, author);

INSERT INTO hackernews
    SELECT * FROM s3(
        'https://datasets-documentation.s3.eu-west-3.amazonaws.com/hackernews/hacknernews.parquet',
        'Parquet',
        'id UInt64,
         deleted UInt8,
         type String,
         by String,
         time DateTime,
         text String,
         dead UInt8,
         parent UInt64,
         poll UInt64,
         kids Array(UInt32),
         url String,
         score UInt32,
         title String,
         parts Array(UInt32),
         descendants UInt32');

要找出有多少条评论提到了“ClickHouse”，我们可以运行

SELECT count(*)
FROM hackernews
WHERE hasToken(lower(comment), 'ClickHouse');

┌─count()─┐
│     516 │
└─────────┘

1 row in set. Elapsed: 0.843 sec. Processed 28.74 million rows, 9.75 GB (34.08 million rows/s., 11.57 GB/s.)

在我的机器上，查询花费了 0.843 秒完成。现在让我们在“comment”列上创建一个倒排索引。请注意，我们索引小写评论以查找与其大小写无关的术语。

ALTER TABLE hackernews ADD INDEX comment_idx(lower(comment)) TYPE inverted;
ALTER TABLE hackernews MATERIALIZE INDEX comment_idx;

索引的物化需要一段时间（要检查索引是否已创建，请使用系统表 system.data_skipping_indices）。让我们再次运行查询

SELECT count(*)
FROM hackernews
WHERE hasToken(lower(comment), 'clickhouse');

┌─count()─┐
│    1145 │
└─────────┘

1 row in set. Elapsed: 0.248 sec. Processed 4.54 million rows, 1.79 GB (18.34 million rows/s., 7.24 GB/s.)

EXPLAIN indexes = 1
SELECT count(*)
FROM hackernews
WHERE hasToken(lower(comment), 'clickhouse')

┌─explain─────────────────────────────────────────┐
│ Expression ((Projection + Before ORDER BY))     │
│   Aggregating                                   │
│     Expression (Before GROUP BY)                │
│       Filter (WHERE)                            │
│         ReadFromMergeTree (default.hackernews)  │
│         Indexes:                                │
│           PrimaryKey                            │
│             Condition: true                     │
│             Parts: 4/4                          │
│             Granules: 3528/3528                 │
│           Skip                                  │
│             Name: comment_idx                   │
│             Description: inverted GRANULARITY 1 │
│             Parts: 4/4                          │
│             Granules: 554/3528                  │
└─────────────────────────────────────────────────┘

这比没有索引快大约 3.4 倍！我们还可以搜索一个或多个术语，即析取或合取

SELECT count(*)
FROM hackernews
WHERE multiSearchAny(lower(comment), ['oltp', 'olap']);

┌─count()─┐
│    2177 │
└─────────┘

1 row in set. Elapsed: 0.482 sec. Processed 8.84 million rows, 3.47 GB (18.34 million rows/s., 7.19 GB/s.)

SELECT count(*)
FROM hackernews
WHERE hasToken(lower(comment), 'avx') AND hasToken(lower(comment), 'sve');

┌─count()─┐
│      22 │
└─────────┘

1 row in set. Elapsed: 0.240 sec. Processed 663.55 thousand rows, 272.44 MB (2.77 million rows/s., 1.14 GB/s.)

将来，希望会有一个类似于 multiSearchAny() 的专用函数，用于一次搜索多个 AND 连接的术语。

至此，我们结束了关于 ClickHouse 中倒排索引的博文。我们很乐意收到您的反馈，例如，您自己使用倒排索引的经验或对未来扩展的想法。