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列上创建一个倒排索引。由于倒排索引仍处于实验状态，我们首先需要启用它。一旦倒排索引正式发布，这个步骤就不再需要。

SET allow_experimental_inverted_index = true;
ALTER TABLE docs ADD INDEX inv_idx(doc) TYPE inverted;
ALTER TABLE docs MATERIALIZE INDEX inv_idx;

在创建索引时，ClickHouse将"doc"这列中的每个文档拆分成一个术语列表。默认情况下，拆分是按空格进行的，但也可以将文本标记化为n-grams（参考ngrams函数）。索引结果在概念上看起来像这样：

Dictionary (Terms)	Posting Lists
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

从中我们可以看到，倒排索引将每个"Terms"与“postings”关联起来，即包含相应术语文档的行位置。

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

目前还不支持但未来可能会添加的词典的进一步有趣扩展包括：

删除不带有语义权重的停用词(stop words)，如"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位图格式来压缩倒排表。这种格式的主要思想是将倒排表示为位图(例如[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位图在这方面特别出色，因为它们带有优化的算法来联合和交叉两个容器类型的每种组合。

字典压缩

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

在ClickHouse的倒排索引中，FSTs将术语“翻译”为倒排列表偏移量。上述例子中的FST接受"See, "see", "seas", "seven"和"wind"这些术语。通过累积每个转换的输出来计算倒排列表的偏移量。例如，术语“seas”产生偏移量4 + 5 = 9。该图展示了一个简化版的FST。

磁盘布局

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

倒排索引的构建，也称为“倒置”，是一个CPU和时间密集型的操作。在ClickHouse中的倒排索引被实现为辅助索引，因此它们存在于Part的粒度上。在当前的实现中，合并两个Part会重新从头开始在新Part上创建倒排索引。将来可能会用更轻量级的增量索引维护优化这一点，使增量索引能够直接合并两个现有索引。目前，已经注意到索引创建这一成本限制。在不同的索引构建方法中，ClickHouse使用了一种策略（“单通道内存倒置”）：

单次迭代底层列数据（而不是需要两次迭代），
处理一个可配置的数据chunk（而不是根据底层列的大小分配内存），并
直接构建索引（而不是先将中间文件写入磁盘，然后在随后的处理步骤中合并）。

生成的倒排索引是分段的，即由多个较小的子索引组成。每个段对应原始列的连续行范围。行范围可以有不同的大小，但其近似大小可以通过参数 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"列上创建一个倒排索引。注意，我们对小写后的"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 版是阿里云提供的全托管 ClickHouse服务，是国内唯一和 ClickHouse 原厂达成战略合作并一方提供企业版内核服务的云产品。企业版较社区版 ClickHouse 增强支持实时update&delete，云原生存算分离及Serverless 能力，整体成本可降低50%以上，现已开启邀测，欢迎申请体验（链接：https://www.aliyun.com/product/apsaradb/clickhouse）

产品介绍（https://www.aliyun.com/product/apsaradb/clickhouse）

技术交流群：