介绍 ClickHouse 中的倒排索引

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

倒排索引是在几十年前发明的，但只有像谷歌这样的搜索引擎才让大多数人每天多次与倒排索引互动——通常是在不知情的情况下。倒排索引是中心数据结构，它使在庞大的文本文档集合中快速有效地搜索成为可能。倒排索引背后的想法是编译一个包含术语的数据库，以及指向包含这些术语的文档的指针。

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

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 位图”的形式）存储倒排列表，目的是减少它们的内存消耗。我们将在下面更深入地探讨倒排列表压缩。在初始倒排索引版本中，倒排列表引用包含相应术语的文档的行位置。这将来可能会扩展为包含其他元数据，例如

• 与每个倒排一起存储的文档频率计数，指示术语在文档中出现的频率。此类信息将使我们能够计算术语频率/逆文档频率 (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.

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

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

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

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

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

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

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

倒排索引构建，也称为“反转”，是一项 CPU 密集型和时间密集型操作。ClickHouse 中的倒排索引实现为二级索引，因此它们以部分的粒度存在。在当前实现中，两个部分的合并会从头开始重新创建新部分上的倒排索引。将来可能会通过更轻量级的增量索引维护来优化这一点，该维护能够直接合并两个现有索引。目前，我们已采取措施限制索引创建的成本。在不同的索引构建方法中，ClickHouse 使用了一种策略（“单遍内存反转”），该策略

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

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

部分的索引存储为三个文件。

元数据文件是一个段描述符数组，每个描述符包含一个唯一的段 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() 的专用函数来一次搜索多个 ANDed 术语。

有了这些，我们就完成了有关 ClickHouse 中的倒排索引的博文。我们很乐意收到您的反馈，例如，您使用倒排索引的经验或对未来扩展的想法。