1. 概述
ClickHouse 支持多种跳表索引，其中包含近期 IBM 两个员工提交的倒排索引。
本文先简单介绍倒排相关概念与大体框架，然后将重点讲解 ClickHouse 采用 SPIMI、RoaringBitmap 与 FST 等倒排技术，最后给出相关实现。
2. 倒排索引
1. 全文检索
数据一般分为结构化数据、半结构化数据和非结构化数据等三类，而按数据的分类，搜索也可以分为三种：
-
对结构化数据的搜索
由于结构化数据具备一些固有结构，一般可以根据结构信息来构造出搜索算法来加速搜索，如数据库索引。 -
对半结构化数据的搜索
即然是半结构化数据当然也有一定的结构，同样也可以设计出相应的搜索算法来加速搜索，如 JSON 数组索引。 -
对非结构化数据的搜索：
非结构化数据没有固定格式；若需要在非结构化文档数据集合中搜索出那些文档包含指定内容时往往只能采取顺序扫描方式，对于每一个文档，从文档开头到结尾逐个检查是否匹配指定内容，如 grep 命令。顺序扫描方式对于少量非结构化文档是比较适合的，但对海量数据就无能为力。
既然非结构化数据的顺序扫描方式比较慢，而结构化数据的搜索却相对较快，那比较自然的想法是先将非结构化数据中一部分数据提取出来并重建组织成一定结构化数据，然后再按结构化数据方式进行搜索，从而达到加快搜索目的。
这部分从非结构化数据中提取出来并重新组织的信息，称之索引，而这种针对非结构化数据先建立索引再利用索引进行搜索的过程就叫全文检索（fulltext search）。
全文检索大体分两个过程：索引构建（Indexing）和索引检索（Search）。
既然要针对非结构化数据进行构建索引，那首先需要明确索引内容。非结构化数据中所存储的信息是每个文档包含哪些字符串，若想查找文档中是否包含指定字符串时相对容易，因为根据文档到字符串的映射，那只需要遍历该文档即可；而若需要搜索有那些非结构化文档包含了指定字符串时则比较困难，因为没有字符串到文档的映射，搜索时只能全量遍历所有文档。
但如果索引内容能够保存从字符串到文档的映射，那利用该索引则可以加速搜索，避免遍历全量文档。而从字符串到文档的映射是文档到字符串映射的反向过程，于是保存这种映射信息的索引称为反向索引，即倒排索引（Inverted index）。
前面提到倒排索引上保持的是字符串到文档的映射信息，那从直观上来说倒排索引构建只需要从文档中抽取出一系列字符串，并且每一个字符串都指向包含此字符串的文档集合即可；而倒排索引查询无非就是在一系列字符串中查找是否匹配指定字符串，若匹配则直接返回该字符串保存的文档集合即可。
总的来说，全文检索核心思想就是如此简单。
https://nlp.stanford.edu/IR-book/html/htmledition/contents-1.html
2. 倒排索引
1. 基本概念
上小节用比较通俗描述方式，但在进一步描述全文检索与倒排索引前需要规范一些用语。
-
Term：词项，即上面提到的从文档中抽取出的一个个字符串，一般是字符串类型；
-
Posting List：倒排表，即上面提到的包含指定字符串的文档集合，而一个文档常使用唯一文档ID来表示，故倒排表实际上就是文档ID集合，一般是整数集合类型；
-
Term Dictionary：词项字典 或 词典，即上面提到的字符串到文档的映射信息，用于能够根据 Term 快速查找出其 Posting List；
-
Term Index：词项索引
对于海量 Term，内存可能无法直接容纳全量 Term Dictionary，而 Term Index 并不维护完整 Term，仅包含 Term 一些前缀，因此可以常驻内存；Term Index 首先根据 Term 前缀可以快速定位到 Term Dictionary 块偏移地址，然后在 Term Dictionary 块内查找出 Term 对应的 Posting List。有些实现中并没有 Term Dictionary 概念，而通过 Term Index 直接查找出 Term 对应 Posting List；
2. 索引构建
根据 A first take at building an inverted index 索引构建主要分为四步：
1. 收集文档
主要是收集用于建立索引的文档数据（如应用产生或爬虫得到）。
假如应用产生下面文档数据
| DocID | Document |
|---|---|
| 1 | hello imci |
| 2 | PolarDB IMCI |
2. 分词
分词顾名思义是使用生成规则或算法对文档拆分出一系列的词元（token），包括去除标点符号、去除停词（如 a、this等）。
对收集到文档进行分词得到以下词元
| DocID | Token |
|---|---|
| 1 | hello |
| 1 | imci |
| 2 | PolarDB |
| 2 | IMCI |
3. 词元处理
对于词元进行语言学预处理，产生归一化的词条来作为词项（Term）。
(1) 归一化处理
大写转小写，缩写处理，近义词转换等；
(2) 词干还原
将单词缩减为词根形式（如 Porter 算法），如单复式与单词形态等；通常指很粗略的去除单词两端词缀的启发式过程。
(3) 词形归并
将单词转变为词根形式，如字典转换等；通常指利用词汇表和词形分析来去除前后词缀，从而返回词的原形或词典中的词的过程。
对上述词元进行处理得到以下词项
| DocID | Term |
|---|---|
| 1 | hello |
| 1 | imci |
| 2 | polardb |
| 2 | imci |
4. 构建倒排链
(1) 创建词项字典
| Term | DocID |
|---|---|
| hello | 1 |
| imci | 1 |
| polardb | 2 |
| imci | 2 |
(2) 词典排序
| Term | DocID |
|---|---|
| hello | 1 |
| imci | 1 |
| imci | 2 |
| polardb | 2 |
(3) 合并相同的词项组成倒排表，并构建出词典
| Term | PostingList |
|---|---|
| hello | [1] |
| imci | [1, 2] |
| polardb | [2] |
合并过程中也常记录文档频率与词频：
文档频率（DF，Document Frequency）表示包含该词项的所有文档数
词频（TF，Term Frequency）表示词项在该文档中出现的次数
| Term | DF | PostingList(ID, TF) |
|---|---|---|
| hello | 1 | [(1,1)] |
| imci | 2 | [(1,1), (2,1)] |
| polardb | 1 | [(2,1)] |
(4) 生成词项索引
当内存无法容纳词典时，则需要将词典进行落盘；为了避免全量遍历磁盘中词典，常常通过词项前缀来构建词项索引来加速查找。构造词项索引时即先将词项按不同前缀进行分片落盘并记录好偏移，然后在词项索引中记录好该前缀到词典分片偏移地址；查询时先通过词项前缀在词项索引中查找出该前缀所在词典分片偏移地址，然后在词典分片中查找词项，找到则直接得到倒排表。
至此，倒排索引构建完成。
3. 索引检索
索引检索主要是利用已构建的索引进行查询，主要分为四步：
1. 查询解析
对查询请求进行解析得到检索词，有些情况还需要进行归一化处理、词干还原与词形归并等。
如查询
select * from t where c like "%polardb%”;
2. 搜索索引
(1) 通过内存中词项索引查找到检索词对应的词典分片偏移地址
词项索引中记录 “polar” 及其所有以 “polar” 前缀的词项的词典偏移地址；
(2) 遍历词典分片查找出该检索词的倒排表
通过词项索引找到以 “polar” 为前缀的词项的词典偏移地址，从该偏移地址开始查找词典获取检索词的倒排表；
(3) 对检索词的倒排表进行处理
根据查询请求对各个检索词的倒排表进行处理，如求交集、并集与差集等；
3. 结果集排序并返回
通过搜索索引得到结果集可能比较大，可以根据词典中 DF 与 TF 等进行相关性计算并进行搜索排序；除了基于 DF 与 TF 搜索相关性算法外，还有基于集合论模型（如布尔模型）、基于代数模型（如向量空间模型）与基于概率轮模型（如回归模型）等相关性算法。
3. 倒排技术
1. CK 倒排技术
ClickHouse 倒排索引参考 Inverted Indices Implementation、clickhouse-search-with-inverted-indices 与 github commit。
主要用到 token/ngram 分词、SPIMI（Single-pass index construction with segmentation）构建算法、倒排表压缩算法 RBM（RoaringBitmap）与 词项字典有限转换算法 FST（Finite State Transducer）等；上述各项技术在 Lucene 中也均有应用，下面各小节分别描述相关算法。
2. 分词
1. 分词
CK 倒排索引仅支持 token 和 ngram 两种分词方式：
- token 分词主要是按空格、标点符号或其它非字母数字等分割符进行分割出词项；
- ngram 分词主要是按指定字符数目进行分割出词项，其基于假设，第 n 个词的出现只与前面 n-1 个词相关，而与其它任何词均不相关；
此外，CK 分词不支持指定停止词（即stop words，如a/and/the等）、不同时态（如doing/do/done等），没有词干还原和词形归并等过程。
2. CK 分词实现
CK 分词实现位于 src/Interpreters/ITokenExtractor.h、src/Interpreters/ITokenExtractor.cpp；
struct ITokenExtractor {
virtual void stringToGinFilter(const char * data, size_t length, GinFilter & gin_filter) const = 0;
virtual void stringLikeToGinFilter(const char * data, size_t length, GinFilter & gin_filter) const = 0;
};
其中 stringToGinFilter 与 stringLikeToGinFilter 分别用于 equal 与 like，分开主要是因为 like 需要去除 % 与 _ 等符号；
template <typename Derived>
class ITokenExtractorHelper : public ITokenExtractor {
void stringToGinFilter(const char * data, size_t length, GinFilter & gin_filter) const override {
gin_filter.setQueryString(data, length);
size_t cur = 0, token_start = 0, token_len = 0;
while (cur < length && static_cast<const Derived *>(this)->nextInString(data, length, &cur, &token_start, &token_len))
gin_filter.addTerm(data + token_start, token_len);
}
void stringLikeToGinFilter(const char * data, size_t length, GinFilter & gin_filter) const override {
gin_filter.setQueryString(data, length);
size_t cur = 0;
String token;
while (cur < length && static_cast<const Derived *>(this)->nextInStringLike(data, length, &cur, token))
gin_filter.addTerm(token.c_str(), token.size());
}
}
stringToGinFilter 与 stringLikeToGinFilter 均从字符串开始不断调用 next 相关函数来获取词项，并添加到索引对象中；
struct NgramTokenExtractor final : public ITokenExtractorHelper<NgramTokenExtractor> {
explicit NgramTokenExtractor(size_t n_) : n(n_) {}
static const char * getName() { return "ngrambf_v1"; }
bool nextInString(const char * data, size_t length, size_t * __restrict pos, size_t * __restrict token_start, size_t * __restrict token_length) const override;
bool nextInStringLike(const char * data, size_t length, size_t * pos, String & token) const override;
size_t getN() const { return n; }
private:
size_t n;
};
ngram 分词具体实现；
bool NgramTokenExtractor::nextInString(const char * data, size_t length, size_t * __restrict pos, size_t * __restrict token_start, size_t * __restrict token_length) const {
*token_start = *pos;
*token_length = 0;
size_t code_points = 0;
for (; code_points < n && *token_start + *token_length < length; ++code_points) {
size_t sz = UTF8::seqLength(static_cast<UInt8>(data[*token_start + *token_length]));
*token_length += sz;
}
*pos += UTF8::seqLength(static_cast<UInt8>(data[*pos]));
return code_points == n;
}
算法比较简单，就是从指定位置开始找到 n 个字符，可以支持 utf-8。
bool NgramTokenExtractor::nextInStringLike(const char * data, size_t length, size_t * pos, String & token) const {
token.clear();
size_t code_points = 0;
bool escaped = false;
for (size_t i = *pos; i < length;) {
if (escaped && (data[i] == '%' || data[i] == '_' || data[i] == '\\')) {
token += data[i];
++code_points;
escaped = false;
++i;
} else if (!escaped && (data[i] == '%' || data[i] == '_')) {
/// This token is too small, go to the next.
token.clear();
code_points = 0;
escaped = false;
*pos = ++i;
} else if (!escaped && data[i] == '\\') {
escaped = true;
++i;
} else {
const size_t sz = UTF8::seqLength(static_cast<UInt8>(data[i]));
for (size_t j = 0; j < sz; ++j)
token += data[i + j];
i += sz;
++code_points;
escaped = false;
}
if (code_points == n) {
*pos += UTF8::seqLength(static_cast<UInt8>(data[*pos]));
return true;
}
}
return false;
}
与 nextInString 不同，nextInStringLike 需要处理 like 的匹配符（包括任意匹配符 % 与 单一匹配符 _) 和 转义符 \ 等，按这个实现，CK 应该不能类似 MySQL 那样可以通过 ESCAPE 来自定义转义符。
struct SplitTokenExtractor final : public ITokenExtractorHelper<SplitTokenExtractor> {
static const char * getName() { return "tokenbf_v1"; }
bool nextInString(const char * data, size_t length, size_t * __restrict pos, size_t * __restrict token_start, size_t * __restrict token_length) const override;
bool nextInStringLike(const char * data, size_t length, size_t * __restrict pos, String & token) const override;
};
token 分词具体实现大体类似 ngram 分词实现，不再展示，具体可以直接阅读 SplitTokenExtractor::nextInString、SplitTokenExtractor::nextInStringLike。
2. SPIMI
1. 索引构建流程
CK 主要对指定列进行分词得到 Term 并通过 SPIMI 进行索引构建（index construction 或 indexing），总体上比较纯粹，不支持词频加权 TF-IDF（term frequency-inverse document frequency）等。
2. 索引构建算法
目前常用单机索引构建算法（不包含Web搜索引擎常用的分布式索引构建算法）：
1. 基于排序的索引构建方式（Sorting-Based Index Construction）
对 Term 进行排序并将相同的 Term 进行合并，但基于内存且排序效率比较低。
2. 基于散列表的索引构建方式（Hash-Based Index Construction）
将 Term 作为散列表的 key，遇到相同 Term 则合并 Post Lists，但只能基于内存。
3. 基于块的排序索引算法 BSBI（Blocked Sort-Based Indexing Algorithm)
BSBI 算法主要思想类似外排，主要分为三步：
（1）将文档集分割为大小相等的几个部分，保证每一分区均可以内存中处理；
（2）将每个分区的（TermID，DocID）进行排序并落盘；
（3）将磁盘中所有分区的（TermID，DocID）进行合并后得到最终的索引；
BSBI 为了节省空间会将 Term 转换为 TermID，因此构建过程需要一直在内存中额外维持每一个 Term 到 TermID 的全局映射关系以便每一块构建过程中查找，若内存不能存储所有 Term 则算法失败；此外基于排序构建方式显然没有基于散列表构建方式来得高效；
3. SPIMI 算法
因此，综合上述各算法优缺点，基于散列表的分区方式的内存式单遍扫描索引构建算法 SPIMI（ Single-Pass In-Memory Indexing）应运而生。
- 创建输出文件 output_file；
- 创建（词项Term，倒排表PostingList）键值对的散列表 dictionary，即词项字典（TermDictionary）；
- 当存在足够内存时循环执行以下算法：
- 对分割出的每一词项 Term（token）；
- 判断 Term 是否存在 dictionary 中：
- 若不存在则将该 Term 作为 key 创建新散列项并插入到 dictionary 并返回空 PostingList；
- 否则直接返回该 Term 对应的 PostingList；
- 若 PostingList 已满：
- 则扩大 PostingList 大小；
- 将 token 所对应的 DocID 添加到倒排表 PostingList；
- 在收集到足够（Term，PostingList）后对当前词项字典 dictionary 按 Term 进行排序；
- 将排序后 Term 集合和 PostingList 等结果写入 output_file 文件中，排序是为了加速后续合并操作；
- 返回 output_file 对象；
SPIMI 算法后续的文件合并操作与 BSBI 算法基本一致，即总输出的 Term 集合是有序的。
SPIMI 与 BSBI 算法的区别在于：
- BSBI 算法在分块构建索引阶段，需要一直维护一个全局的词项 Term 到 TermID 的映射表、局部索引为 TermID 及其有序倒排表 PostingList，即在合并前就构造 TermID 到 PostingList 的全局映射表；
- SPIMI 算法分块构建索引阶段只需要建立当前块 Term 和 Posting List 的局部映射表，在合并阶段将块倒排表按 Term 进行两两合并，合并完成后自然构造出 Term 到 PostingList 的全局映射表，即在合并过程中逐步构造。
总的来说 SPIMI 更加高效且节省空间，还可以借助对词项 Term 和 倒排表 Posting List 压缩进一步提升算法的效率。
4. CK SPIMI 实现
TODO：
GinFilter 提供基本功能来构建倒排索引，如添加词项；
/// GinFilter provides underlying functionalities for building inverted index and also
/// it does filtering the unmatched rows according to its query string.
/// It also builds and uses skipping index which stores (segmentID, RowIDStart, RowIDEnd) triples.
class GinFilter {
public:
/// Add term (located at 'data' with length 'len') and its row ID to the postings list builder
/// for building inverted index for the given store.
void add(const char * data, size_t len, UInt32 rowID, GinIndexStorePtr & store, UInt64 limit) const;
};
// 通过添加分割出的词项来构建索引
void GinFilter::add(const char * data, size_t len, UInt32 rowID, GinIndexStorePtr & store, UInt64 limit) const {
String term(data, len);
// 查找词项是否在词项字典TermDictionary（词项Term，倒排表PostingList）中
auto it = store->getPostingsListBuilder().find(term);
if (it != store->getPostingsListBuilder().end()) {
// 若该词项已经存在对应的倒排表，则直接将该词项所对应的文档ID添加到倒排表中
// 不过先判断文档ID是否已存在，比如一个文档中出现多次该词项时防止重复添加
if (!it->second->contains(rowID))
it->second->add(rowID);
} else {
// 若该词项没有对应的倒排表则需要创建该词项的倒排表
UInt64 size_limit = std::lround(limit * params.density);
auto builder = std::make_shared<GinIndexPostingsBuilder>(size_limit);
// 将该词项的文档ID添加到其对应的倒排表中
builder->add(rowID);
// 并将该（词项Term，倒排表PostingList）添加到词项字典TermDictionary中
store->setPostingsBuilder(term, builder);
}
}
GinIndexPostingsBuilder 用于构建倒排表，其使用 roaring::Roaring 来保存倒排表，即文档ID集合；
/// Build a postings list for a term
class GinIndexPostingsBuilder {
public:
/// Check whether a row_id is already added
bool contains(UInt32 row_id) const;
/// Add a row_id into the builder
void add(UInt32 row_id);
/// Serialize the content of builder to given WriteBuffer, returns the bytes of serialized data
UInt64 serialize(WriteBuffer & buffer) const;
/// Deserialize the postings list data from given ReadBuffer, return a pointer to the GinIndexPostingsList created by deserialization
static GinIndexPostingsListPtr deserialize(ReadBuffer & buffer);
private:
constexpr static int MIN_SIZE_FOR_ROARING_ENCODING = 16;
/// When the list length is no greater than MIN_SIZE_FOR_ROARING_ENCODING, array 'rowid_lst' is used
/// As a special case, rowid_lst[0] == CONTAINS_ALL encodes that all rowids are set.
std::array<UInt32, MIN_SIZE_FOR_ROARING_ENCODING> rowid_lst;
/// When the list length is greater than MIN_SIZE_FOR_ROARING_ENCODING, roaring bitmap 'rowid_bitmap' is used
roaring::Roaring rowid_bitmap;
};
提供添加文档ID到倒排表、判断文档ID是否在倒排表中等功能；
// 添加文档ID到倒排表中
void GinIndexPostingsBuilder::add(UInt32 row_id)
{
if (containsAllRows())
return;
if (useRoaring()) {
if (rowid_bitmap.cardinality() == size_limit) {
/// reset the postings list with MATCH ALWAYS;
rowid_lst_length = 1; /// makes sure useRoaring() returns false;
rowid_lst[0] = CONTAINS_ALL; /// set CONTAINS_ALL flag;
} else {
rowid_bitmap.add(row_id);
}
} else {
assert(rowid_lst_length < MIN_SIZE_FOR_ROARING_ENCODING);
rowid_lst[rowid_lst_length] = row_id;
rowid_lst_length++;
if (rowid_lst_length == MIN_SIZE_FOR_ROARING_ENCODING) {
for (size_t i = 0; i < rowid_lst_length; i++)
rowid_bitmap.add(rowid_lst[i]);
rowid_lst_length = USES_BIT_MAP;
}
}
}
// 判断文档ID是否在倒排表中
bool GinIndexPostingsBuilder::contains(UInt32 row_id) const {
if (useRoaring())
return rowid_bitmap.contains(row_id);
const auto * const it = std::find(rowid_lst.begin(), rowid_lst.begin()+rowid_lst_length, row_id);
return it != rowid_lst.begin() + rowid_lst_length;
}
GinIndexStore 用于存储词项字典TermDictionary（词项Term，倒排表PostingList）；
/// Gin index store which has gin index meta data for the corresponding column data part
class GinIndexStore {
public:
/// Container for all term's Gin Index Postings List Builder
using GinIndexPostingsBuilderContainer = std::unordered_map<std::string, GinIndexPostingsBuilderPtr>;
/// Get current postings list builder
const GinIndexPostingsBuilderContainer & getPostingsListBuilder() const { return current_postings; }
/// Set postings list builder for given term
void setPostingsBuilder(const String & term, GinIndexPostingsBuilderPtr builder) { current_postings[term] = builder; }
/// Dictionaries indexed by segment ID
using GinSegmentDictionaries = std::unordered_map<UInt32, GinSegmentDictionaryPtr>;
/// Term's dictionaries which are loaded from .gin_dict files
GinSegmentDictionaries segment_dictionaries;
// 词项字典TermDictionary（词项Term，倒排表PostingList）
/// Container for building postings lists during index construction
GinIndexPostingsBuilderContainer current_postings;
};
void GinIndexStore::writeSegment() {
/// Write segment
metadata_file_stream->write(reinterpret_cast<char *>(¤t_segment), sizeof(GinIndexSegment));
TokenPostingsBuilderPairs token_postings_list_pairs;
token_postings_list_pairs.reserve(current_postings.size());
// 所有词项字典TermDictionary
for (const auto & [token, postings_list] : current_postings)
token_postings_list_pairs.push_back({token, postings_list});
// 落盘前对所有词项字典TermDictionary（词项Term，倒排表PostingList）按词项进行排序
/// Sort token-postings list pairs since all tokens have to be added in FST in sorted order
std::sort(token_postings_list_pairs.begin(), token_postings_list_pairs.end(),
[](const TokenPostingsBuilderPair & x, const TokenPostingsBuilderPair & y)
{
return x.first < y.first;
});
// 将所有倒排表落盘
/// Write postings
std::vector<UInt64> posting_list_byte_sizes(current_postings.size(), 0);
for (size_t i = 0; const auto & [token, postings_list] : token_postings_list_pairs)
{
auto posting_list_byte_size = postings_list->serialize(*postings_file_stream);
posting_list_byte_sizes[i] = posting_list_byte_size;
i++;
current_segment.postings_start_offset += posting_list_byte_size;
}
///write item dictionary
std::vector<UInt8> buffer;
WriteBufferFromVector<std::vector<UInt8>> write_buf(buffer);
FST::FstBuilder fst_builder(write_buf);
UInt64 offset = 0;
for (size_t i = 0; const auto & [token, postings_list] : token_postings_list_pairs)
{
fst_builder.add(token, offset);
offset += posting_list_byte_sizes[i];
i++;
}
fst_builder.build();
write_buf.finalize();
/// Write FST size
writeVarUInt(buffer.size(), *dict_file_stream);
current_segment.dict_start_offset += getLengthOfVarUInt(buffer.size());
/// Write FST blob
dict_file_stream->write(reinterpret_cast<char *>(buffer.data()), buffer.size());
current_segment.dict_start_offset += buffer.size();
current_size = 0;
current_postings.clear();
current_segment.segment_id = getNextSegmentID();
metadata_file_stream->sync();
dict_file_stream->sync();
postings_file_stream->sync();
}
2. RoaringBitmap
1. 倒排表压缩算法
倒排表（Posting List）保存的是有序的 DocID 数值列表，而有序数值数组是比较容易进行压缩处理的，而且一般来说压缩效益也不错。
倒排索引的压缩算法主要有 FOR（Frame Of Reference）和 RBM（RoaringBitMap）算法，比如 ES，其中位图压缩 RBM 应用更加广泛，包括 ES、Greenplum、Spark 与 Druid 等。
FOR 压缩算法核心是按照差值进行压缩，当分词 DocID 比较分散且差值较大（稀疏数组）时压缩效果比较有限，而 RBM 内部采用不同类型的容器让其能够有效处理稀疏与稠密数值数组。ClickHouse 也采用 RBM 来保存 Posting List。
2. RBM 算法
RBM 主要思路是将整数按照高 16 位进行分桶（container），在存储整数时先按照数据的高 16 位定位到 container，再将低位数值（去掉高 16位后）放到该 container，而 container 主要有三种不同类型：
1. Array Container
Array Container 不压缩数据，只保存少量数据，数组容量会随整数加入进行动态增加，且按递增顺序存储；当达到最大元素数量（如4K）时，RBM 会将 Array Container 内部转换为 Bitmap Container。Bitmap Container 主要用于稀疏数据。
2. Bitmap Container
Bitmap Container 为 bitmap 实现，其实就是一个每个整数都只占用一个bit的数组，其使用固定长度的数组来存储位图数据，不支持动态扩展数组，插入整数时直接修改对应位置的 bit 位。Bitmap Container 主要用于稠密数据。
3. RLE Container
Run-length Encoding（RLE）Container 采用行程长度编码方式做压缩，偶数索引处的值表示连续整数的第一个整数值，奇数索引处的值表示连续整数数目，如 [2, 3, 4, 8, 9]可以编码为 [2, 3, 8, 2]。RLE Container 有效性取决于 Posting List 数值数组的紧凑程度和连续性；假如一个 Posting List中所有数据都是连续的，那只需要 4 字节；但假如所有数据均不连续则编码后空间反正增加 1 倍。RLE Container 主要用于连续整数较多的数据。
4. Container 创建与转换
在向 Posting List 添加 DocID 时，若分桶后该 Container 不存在时则需要创建新 Container；若只插入少量元素，RBM 默认会采用 Array Container 来存储；若插入的是元素序列，RBM 会计算 Array Container 和 RLE Container 的空间占用量，并选择空间较小的 Container 类型来存储。
当 Array Container 的容量超过 4K 后，RBM 会自动将其转换为 Bitmap Container 来存储；RBM 一般还提供优化接口，对于 Array Container 或 Bitmap Container，若其与对应的 RLE Container 的空间占用量进行对比，若占用更小则会转换。
RBM 可以做到 O(log N) 查找性能：
- 首先二分查找 key 的高 16 位找出所在桶（Container）；
- 若找到则在该 Container 查找低 16 位：对于 Bitmap Container 查找性能为 O(1)；Array Container 与 RLE Container 需要二分查找，查找性能为 O(log N)；
RBM 还可以支持 SIMD加速位图操作、交集与联合等操作，可用于多个连接条件进行快速过滤。
3. CK RBM 实现
CK RBM 实现直接使用 CRoaring，c++实现，支持 SIMD 等，具体接口参见 contrib/croaring/cpp/roaring.hh。
class Roaring {
typedef api::roaring_bitmap_t roaring_bitmap_t; // class-local name alias
public:
void add(uint32_t x) { api::roaring_bitmap_add(&roaring, x); }
bool contains(uint32_t x) const {
return api::roaring_bitmap_contains(&roaring, x);
}
bool removeRunCompression() {
return api::roaring_bitmap_remove_run_compression(&roaring);
}
bool runOptimize() { return api::roaring_bitmap_run_optimize(&roaring); }
roaring_bitmap_t roaring;
};
CK 用 roaring::Roaring 来存储 PostingsList；
using GinIndexPostingsList = roaring::Roaring;
/// Build a postings list for a term
class GinIndexPostingsBuilder {
public:
bool contains(UInt32 row_id) const {
if (useRoaring()) return rowid_bitmap.contains(row_id);
}
void add(UInt32 row_id) {
if (useRoaring()) rowid_bitmap.add(row_id);
}
UInt64 serialize(WriteBuffer & buffer) const;
static GinIndexPostingsListPtr deserialize(ReadBuffer & buffer);
std::array<UInt32, MIN_SIZE_FOR_ROARING_ENCODING> rowid_lst;
roaring::Roaring rowid_bitmap;
};
TODO:
3. FST
1. 词项索引
倒排索引的核心思想是根据查询词来快速查找对应词项（Term）所有的文档或列（Posting List），那如何设计 Term 到 PostingList 的词项索引（Term Index）就显得尤其重要，如散列表、字典树与二叉搜索树等；比如基于二叉搜索树的词项索引是先将所有词项排序再二分查找即可，查找的时间复杂度是 O(log N)，而空间复杂度是 O(N*len(Term))，内存消耗非常大。
而基于 FST（Finite State Transducer）底层结构来构建词项索引能够更好保证时间和空间复杂度的均衡，其应用更加广泛，如 ES。
- 空间复杂度：空间占用小，通过 Term 拆分复用及前后缀重用等压缩存储空间；
- 时间复杂度：查询速度快，查询仅有 O(len(Term)) 时间复杂度；
ClickHouse 也采用 FST 来构建 Term 到 Posting List 地址偏移的词项索引，其可以利用 FST 结构以 O(len(Term)) 时间复杂度来快速定位出指定 Term 到其所在 Posting List 压缩数据块的地址偏移，然后根据该地址偏移读取该 Posting List 压缩数据块并构建出对应的 RBM 对象，最后用 RBM 对象以 O(log N) 查找出该 Term 所对应的 Posting List。
2. FST 算法
讨论 FST（Finite State Transducer）前先来回顾一下大家都熟悉的有限状态机 FSM（Finite State Machine），其表示有限个状态（State）集合以及这些状态之间转移和动作的数学模型；而 FST 也是一个 FSM，每个节点表示一个状态，每个节点可以有多个出边，每个出边不仅有标签还有对应的值，终止时会输出一个关联值，具有 transducer 特性，在语音识别和自然语言搜索、处理等方向被广泛应用。
FST 从功能上来说是类似于散列表，可以表示成 FST<Key, Value> 形式，比如 ClickHouse 使用 FST<Term, PostingListOffset> 来记录词项到倒排表地址偏移，即词项索引，其用于找出指定 Term 所在的 PostingList 压缩块的地址偏移。
介绍 FST 算法前，先通过简单例子展示 FST<Key, Value> 构建与查找过程；
下面以 <mon,2>、<thurs,5>、<tues,3> 与 <tye,99> 为例来构建 FST，下面各图中虚线表示可能修改，而虚线则已经不可修改。
从第一个 <mon,2> 开始插入；
可以看出三个出边分别为：m/2、o/0 与 n/0，当然也可以按 m/0、o/1 与 n/1 来分配，但关联值靠近初始状态让算法更加简单，后面论文中算法也是如此。
接着插入 <thurs,5>，mon 和 thurs 没有共同的前缀；
然后插入 <tues,3>，tues 的 output 是 3，并且 tues 与 thurs 有共同的前缀 t，因此 5 和 3 的前缀操作得出的结果为 3，根据前缀值来调整关联值，状态0 -> 状态4的关联值设置为3，状态4 -> 状态5的关联值设置为2；
最后插入 <tye,99>，tye 与 tues也共同的前缀 t，因此也需要调整关联值，状态4 -> 状态9的关联值设置为99-3=96。
构建完成后生成最终 FST：
构建出 FST 后则可以使用 FST 来查找 Key，若存在则返回 Value；
以查找 tues 为例：
开始时在初始状态0位置，不断查找是否有各字符的出边，有则累计关联值，否则判断是否为结束状态；
初始状态 0
输入 t，FST 从 0 -> 4，value = 3
输入 u，FST 从 4 -> 8，value = 3 + 0
输入 e，FST 从 8 -> 7，value = 3 + 0 + 0
输入 s，FST 从 7 -> 3，value = 3 + 0 + 0 + 0
状态 3 为结束状态，则表示找到 tues，且其关联值为 3。
以查找 me 为例：
初始状态 0
输入 t，FST 从 0 -> 1，value = 2
输入 e，FST 没有对应出边，则表示 FST 不存在 me 键。
通过构造流程来看，输入 key 集合按序来构造 FST 会更加方便，尤其是在处理大数据量；当内存无法容纳整个 FST 结构时则需要按需将构建好的部分 FST 落盘，若 key 是按序输出时则可以直接将前面子树逐步落盘，反正后续构造过程中也不会再次访问到。针对 ClickHouse 来说，其 FST 的 key 是 Term，而 SPIMI 算法构建出的 Term 集合刚好是有序的。
从上面例子也可以看出，FST 不仅可以共同前缀和后缀以节省空间，而且保证不同的转移有唯一的关联值。
此外，FST 的前缀计算基于字节而不是字符，因此也是支持 utf8 等编码。
FST 算法完整描述参见 Direct Construction of Minimal Acyclic Subsequential Transducers 论文，下面直接给出论文中 FST 算法伪代码：
program Create_Minimal_Transduer_for_Given_List(input, output);
var
MinimalTransduerStatesDitionary : DICTIONARY;
TempStates : array [0..MAX_WORD_SIZE] of STATE;
InitialState : STATE;
PreviousWord, CurrentWord, CurrentOutput, WordSuffix, CommonPrefix : string;
tempString : string;
tempSet : set of string;
i, j, PrefixLengthPlus1 : integer;
c:char;
funtion FindMinimized (s : STATE) : STATE;
{returns an equivalent state from the ditionary. If not present inserts a copy of the parameter to the ditionary and returns it}
var r : STATE:
begin
r := MEMBER(MinimalTransduerStatesDitionary,s);
if r = NULL then begin
r := COPY_STATE(s);
INSERT(r);
end;
return(r);
end; {FindMinimized}
begin
MinimalTransduerStatesDitionary := NEW_DICTIONARY;
for i := 0 to MAX_WORD_SIZE do
TempState[i]:= NEW_STATE;
PreviousWord := '';
CLEAR_STATE(TempState[0]);
while not eof(input) do begin
{Loop for the words in the input list}
readln(input,CurrentWord,CurrentOutput);
{the following loop calulates the length of the longest common prefix of CurrentWord and PreviousWord }
i := 1;
while (i<length(CurrentWord)) and (i<length(PreviousWord)) and (PreviousWord[i] = CurrentWord[i]) do
i := i+1;
PrefixLengthPlus1 := i;
{we minimize the states from the suffix of the previous word }
for i := length(PreviousWord) downto PrefixLengthPlus1 do
SET_TRANSITION(TempStates[i-1], PreviousWord[i], FindMinimized(TempStates[i]));
{This loop initializes the tail states for the current word}
for i := PrefixLengthPlus1 to length(CurrentWord) do begin
CLEAR_STATE(TempStates[i]);
SET_TRANSITION(TempStates[i-1], CurrentWord[i], TempStates[i]);
end;
if CurrentWord <> PreviousWord then begin
SET_FINAL(TempStates[length(CurrentWord)], true);
SET_OUTPUT(TempStates[length(CurrentWord)], {''});
end;
for j := 1 to PrefixLengthPlus1-1 do begin
CommPrefix:= OUTPUT(TempStates[j-1], CurrentWord[j]) ^ CurrentOutput;
WordSuffix := OUTPUT(TempStates[j-1], CurrentWord[j]) - CommPrefix;
SET_OUTPUT(TempStates[j-1], CurrentWord[j], CommonPrefix);
for c := FIRST_CHAR to LAST_CHAR do begin
if TRANSITION(TempStates[j],c) <> NULL then
SET_OUTPUT(TempStates[j], c, concat(WordSuffix, OUTPUT(TempStates[j],c)));
end;
if FINAL(TempStates[j]) then begin
tempSet := Ø;
for tempString in STATE_OUTPUT(TempStates[j]) do
tempSet := tempSet U concat(WordSuffix,tempString);
SET_STATE_OUTPUT(TempStates[j], tempSet);
end;
CurrentOutput := CurrentOutput - CommonPrefix;
end;
if CurrentWord = PreviousWord then
SET_STATE_OUTPUT(TempStates[length(CurrentWord)], STATE_OUTPUT(TempStates[length(CurrentWord)] U CurrentOutput);
else SET_OUTPUT(TempStates[PrefixLengthPlus1-1], CurrentWord[PrefixLengthPlus1], CurrentOutput);
PreviousWord := CurrentWord;
end; {while}
{ here we are minimizing the states of the last word }
for i := length(CurrentWord) downto 1 do
SET_TRANSITION(TempStates[i-1], PreviousWord[i], FindMinimized(TempStates[i]));
InitialState := FindMinimized(TempStates[0]);
PRINT_TRANSDUCER(output,InitialState);
end;
l1：定义 Create_Minimal_Transduer_for_Given_List 函数，用于根据输入词项列表得到输出
l2：变量段
l3：定义 MinimalTransduerStatesDitionary<STATE, STATE> 散列表，即 FST 中状态集合
l4：定义 STATE 数组变量 TempStates[MAX_WORD_SIZE]，其中 key 长度不能超过 MAX_WORD_SIZE 长度
l5：定义 STATE 对象变量 InitialState
l6：定义字符对象 PreviousWord, CurrentWord, CurrentOutput, WordSuffix, CommonPrefix
l7：定义字符对象 tempString
l8：定义字符集合 tempSet
l9：定义整形变量 i, j, PrefixLengthPlus1，其中 PrefixLengthPlus1 表示公共前缀长度 + 1
l10：定义字节变量，FST 前缀计算基于字节而非字符
l11：定义 FindMinimized 函数，输入参数和返回参数均为 STATE 对象
l12：注释 { 在 MinimalTransduerStatesDitionary 散列表中查找输入 STATE s，若不存在则复制 s 并插入到该散列表，否则直接查找到的 STATE 对象 }
l13：定义 STATE 对象变量 r
l14：FindMinimized 函数开始
l15：判断输入 STATE 对象 s 是否在散列表，即是否在 FST 状态集合中，若找到则记录到 r
l16：若不存在
l17：则复制 s 到 r 对象
l18：将新创建 r 插入到 MinimalTransduerStatesDitionary 散列表，即为 FST 创建新状态节点
l19：块结束
l20：返回 r 对象
l21：FindMinimized 函数结束
l22：Create_Minimal_Transduer_for_Given_List 函数开始
l23：初始化 MinimalTransduerStatesDitionary 散列表为空
l24：遍历 TempStates 数组每一成员变量
l25：初始化每一成员为初始新 STATE 对象，NEW_STATE 表示返回一个新的state
l26：初始化 PreviousWord 为空，其用于记录前一个词项
l27：调用 CLEAR_STATE 函数清空 TempState[0] 对象
l28：对于输入 input 键值对集合中每一 <key, value>
l29：注释 { 循环处理键值对集合中每一键值对 }
l30：将当前键值对的 key 记录为 CurrentWord，value 记录为 CurrentOutput
l31：注释 { 下面循环计算 CurrentWord 与 PreviousWord 的最长公共前缀 }
l32：定义变量 i 记录相同前缀的长度
l33：判断当前词项和上次词项是否有相同前缀
l34：若相同则累加长度
l35：PrefixLengthPlus1 记录当前词项和上次词项的相同前缀的长度
l36：注释 { 从 PreviousWord 的后缀开始直到公共前缀进行最小化状态 }
l37：从 PreviousWord 最后一个字节开始直到公共前缀处字节
l38：设置 TempStates[i-1] 转换规则，即添加从 TempStates[i-1] 到 TempStates[i] 转换边，其边上字节为 PreviousWord[i]
l39：注释 { 循环初始化当前输入 CurrentWord 不相同的后缀对应的状态，而共同前缀对应状态已经存在于 FST }
l40：从公共前缀处字节开始当前输入 CurrentWord 最后一个字节
l41：重置 TempStates[i]
l42：设置 TempStates[i-1] 转换规则，即添加从 TempStates[i-1] 到 TempStates[i] 转换边，其边上字节为 CurrentWord[i]
l43：循环结束
l44：若当前输入与前一个输入不相等，则
l45：直接将当前输入最后一个字节对应的状态标记为结束状态
l46：同时设置其 output 为空
l47：判断结束
l48：遍历相同前缀索引，更新当前 FST 中已经存在的状态中前缀相同的状态的关联值
l49：CommPrefix:= OUTPUT(TempStates[j-1], CurrentWord[j]) ^ CurrentOutput;
l50：WordSuffix := OUTPUT(TempStates[j-1], CurrentWord[j]) - CommPrefix;
l51：SET_OUTPUT(TempStates[j-1], CurrentWord[j], CommonPrefix);
l52：for c := FIRST_CHAR to LAST_CHAR do begin
l53：if TRANSITION(TempStates[j],c) <> NULL then
l54：SET_OUTPUT(TempStates[j], c, concat(WordSuffix, OUTPUT(TempStates[j],c)));
l55：end;
l56：if FINAL(TempStates[j]) then begin
l57：tempSet := Ø;
l58：for tempString in STATE_OUTPUT(TempStates[j]) do
l59：tempSet := tempSet U concat(WordSuffix,tempString);
l60：SET_STATE_OUTPUT(TempStates[j], tempSet);
l61：end;
l62：CurrentOutput := CurrentOutput - CommonPrefix;
l63：end;
l64：
l65：
l66：
l67：
l68：
l69：
l70：
l71：
l72：
l73：
l74：TODO:
3. CK FST 实现
CK 基本按照上小节 FST 算法来实现，代码注释都有算法对应的行数，觉得比伪代码更易于阅读，具体可以参见 src/Common/FST.h、src/Common/FST.cpp；
FST 的状态类，主要包括状态信息（FlagValues）与出边信息（arcs）；
/// State implements the State in Finite State Transducer
/// Each state contains all its arcs and a flag indicating if it is final state
class State {
public:
Arc * getArc(char label) const;
void addArc(char label, Output output, StatePtr target) {
arcs[label] = Arc(output, target);
}
bool isFinal() const { return flag_values.is_final == 1; }
void setFinal(bool value) { flag_values.is_final = value; }
/// Transient ID of the state which is used for building FST. It won't be serialized
UInt64 id = 0;
/// State index which indicates location of state in FST
UInt64 state_index = 0;
/// Arcs which are started from state, the 'char' is the label on the arc
std::unordered_map<char, Arc> arcs;
private:
struct FlagValues {
unsigned int is_final : 1;
EncodingMethod encoding_method : 3;
};
union {
FlagValues flag_values;
uint8_t flag = 0;
};
};
FST 的出边类，主要记录出边的关联值与其所指定的状态；
using Output = UInt64;
/// Arc represents a transition from one state to another.
/// It includes the target state to which the arc points and the arc's output.
struct Arc {
Arc() = default;
Arc(Output output_, const StatePtr & target_);
Output output = 0; // 0 means the arc has no output
StatePtr target;
};
FST 构造类，即 FST 算法实现，其接口比较简单，先不断 add 等添加完成后再 build 即可，但仅支持按序添加词项，且词项长度不能超过 256；
/// FstBuilder is used to build Finite State Transducer by adding words incrementally.
/// Note that all the words have to be added in sorted order in order to achieve minimized result.
/// In the end, the caller should call build() to serialize minimized FST to WriteBuffer.
class FstBuilder {
public:
void add(std::string_view word, Output output);
UInt64 build();
private:
StatePtr findMinimized(const State & s, bool & found);
void minimizePreviousWordSuffix(Int64 down_to);
std::array<StatePtr, MAX_TERM_LENGTH + 1> temp_states;
String previous_word;
StatePtr initial_state;
/// map of (state_hash, StatePtr)
std::unordered_map<UInt64, StatePtr> minimized_states;
/// Next available ID of state
UInt64 next_id = 1;
WriteBuffer & write_buffer;
UInt64 previous_written_bytes = 0;
UInt64 previous_state_index = 0;
};
可以按注释中算法行数阅读；
// 在状态集合中查找状态对象，若不存在则创建并插入集合；
/// See FindMinimized in the paper pseudo code l11-l21.
StatePtr FstBuilder::findMinimized(const State & state, bool & found) {
found = false;
auto hash = state.hash();
/// MEMBER: in the paper pseudo code l15
auto it = minimized_states.find(hash);
if (it != minimized_states.end() && *it->second == state) {
found = true;
return it->second;
}
/// COPY_STATE: in the paper pseudo code l17
StatePtr p = std::make_shared<State>(state);
/// INSERT: in the paper pseudo code l18
minimized_states[hash] = p;
return p;
}
// 找出两个词项的公共前缀
/// See the paper pseudo code l33-34.
size_t getCommonPrefixLength(std::string_view word1, std::string_view word2) {
size_t i = 0;
while (i < word1.size() && i < word2.size() && word1[i] == word2[i])
i++;
return i;
}
// 初始化当前输入与上一个输入不相同的后缀对应的状态
/// See the paper pseudo code l33-39 and l70-72(when down_to is 0).
void FstBuilder::minimizePreviousWordSuffix(Int64 down_to) {
for (Int64 i = static_cast<Int64>(previous_word.size()); i >= down_to; --i) {
bool found = false;
auto minimized_state = findMinimized(*temp_states[i], found);
if (i != 0) {
Output output = 0;
Arc * arc = temp_states[i - 1]->getArc(previous_word[i - 1]);
if (arc) output = arc->output;
/// SET_TRANSITION
temp_states[i - 1]->addArc(previous_word[i - 1], output, minimized_state);
}
if (minimized_state->id == 0)
minimized_state->id = next_id++;
if (i > 0 && temp_states[i - 1]->id == 0)
temp_states[i - 1]->id = next_id++;
if (!found) {
minimized_state->state_index = previous_state_index;
previous_written_bytes = minimized_state->serialize(write_buffer);
previous_state_index += previous_written_bytes;
}
}
}
// 添加词项 TODO:
void FstBuilder::add(std::string_view current_word, Output current_output) {
/// We assume word size is no greater than MAX_TERM_LENGTH(256).
/// FSTs without word size limitation would be inefficient and easy to cause memory bloat
/// Note that when using "split" tokenizer, if a granule has tokens which are longer than
/// MAX_TERM_LENGTH, the granule cannot be dropped and will be fully-scanned. It doesn't affect "ngram" tokenizers.
/// Another limitation is that if the query string has tokens which exceed this length
/// it will fallback to default searching when using "split" tokenizers.
size_t current_word_len = current_word.size();
size_t prefix_length_plus1 = getCommonPrefixLength(current_word, previous_word) + 1;
minimizePreviousWordSuffix(prefix_length_plus1);
/// Initialize the tail state, see paper pseudo code l39-43
for (size_t i = prefix_length_plus1; i <= current_word.size(); ++i) {
/// CLEAR_STATE: l41
temp_states[i]->clear();
/// SET_TRANSITION: l42
temp_states[i - 1]->addArc(current_word[i - 1], 0, temp_states[i]);
}
/// We assume the current word is different with previous word
/// See paper pseudo code l44-47
temp_states[current_word_len]->setFinal(true);
/// Adjust outputs on the arcs
/// See paper pseudo code l48-63
for (size_t i = 1; i <= prefix_length_plus1 - 1; ++i) {
Arc * arc_ptr = temp_states[i - 1]->getArc(current_word[i - 1]);
assert(arc_ptr != nullptr);
Output common_prefix = std::min(arc_ptr->output, current_output);
Output word_suffix = arc_ptr->output - common_prefix;
arc_ptr->output = common_prefix;
/// For each arc, adjust its output
if (word_suffix != 0) {
for (auto & [label, arc] : temp_states[i]->arcs)
arc.output += word_suffix;
}
/// Reduce current_output
current_output -= common_prefix;
}
/// Set last temp state's output
/// paper pseudo code l66-67 (assuming CurrentWord != PreviousWorld)
Arc * arc = temp_states[prefix_length_plus1 - 1]->getArc(current_word[prefix_length_plus1 - 1]);
assert(arc != nullptr);
arc->output = current_output;
previous_word = current_word;
}
// 构建 TODO:
UInt64 FstBuilder::build() {
minimizePreviousWordSuffix(0);
/// Save initial state index
previous_state_index -= previous_written_bytes;
UInt8 length = getLengthOfVarUInt(previous_state_index);
writeVarUInt(previous_state_index, write_buffer);
write_buffer.write(length);
return previous_state_index + previous_written_bytes + length + 1;
}
4. 总结
TODO:
阅读开源项目，解决长尾问题，扩大；
ck 如何保证更新及时性，可能需要添加额外 cache ? 或对于没来得及更新的 pack 进行全pack扫描；
后台线程异步构建？
倒排可以用于 eq、like、or、and、in 等；
其它AP系统的倒排索引
Druid(过滤)
Greenplum
Doris(CLucene)，不如基于 ck 实现
全文检索库 Manticore / LucenePlusPlus / CLucene / sphinx
全文检索服务 Lucene / Elasticsearch / Apache Solr
