拆解一个（Postgres）搜索引擎

数据库用索引来加速查询。与其逐行检查表中的值是否匹配，不如先在索引里查找该值，再直接定位到对应的行。大多数数据库索引是 b-tree 或 b+tree，它们把某一列的值按全序排序，因此能快速按精确值、值区间或前缀找到匹配项。举例来说，b-tree 可以快速找出所有名字为 Rick 的用户、所有价格低于 5 美元的商品，或所有创建日期落在某年 11 月的仓库。但 b-tree 无法匹配字符串中间的内容。全文搜索索引正是为此而生。不要这样做——它会检查 users 表中的每一行 name：

SELECT * FROM users
 WHERE name LIKE '% Royal';

更不要这样做——它会把 vendors 表中的每个 description 检查三遍：

SELECT * FROM vendors
 WHERE description LIKE '%postgres%'
 AND description LIKE '%reliable%'
 AND description LIKE '%fast%';

这类任务的正确工具是倒排索引，几乎所有全文搜索引擎都靠它按文档包含的词快速定位文档。注意PlanetScale TIN 是面向 Postgres 的完整全文搜索索引。关于 TIN 的功能、性能和实现细节，我们在另一篇文章里有深入剖析。需要系统复习全文搜索索引的读者，请继续往下读。

倒排索引概览

倒排索引是一种数据结构，通常存放在磁盘上，把词项映射到位置。它的工作方式就像书末的索引。它甚至和 b-tree 颇为相似，区别在于：b-tree 的键是文本列的完整值，而倒排索引的键是文本字段中的每一个词。顺带一问：那它为什么叫“倒排”？它是相对于文本本身倒排，而不是相对于其他索引。文本是一系列隐含的位置，每个位置对应一个词。倒排索引则是一串词，每个词对应一个或多个出现位置。回到结构本身。倒排索引至少包含一个词项词典和若干倒排列表。视功能集而定，它还可能带有位置数据和词频数据。在这里试几次搜索，看看你的查询如何对索引中各倒排列表里的文档 ID 求并集或交集。

词项词典

词项词典将全部文档中出现的所有词项映射到倒排列表。在磁盘上，它通常是一棵 B 树或其他按字典序排序的结构。查询到来时，系统会在词项词典中查找查询中的所有词项。带通配符和模糊匹配的查询可能会扫描词项词典的一部分甚至全部，以寻找匹配的精确词项。例如，g* 会同时查找 gonna 和 give，而 u~2 会查找与 u 编辑距离不超过两个字符的所有词项：即 you 和 up。可以在上面的图里试一下。

倒排列表

词项词典中的每个词项都指向一个位置列表，称为倒排列表。这些位置是某种文档标识符，足以让数据库或搜索引擎在表或文件存储中找到对应文档。在大多数倒排索引中，它们是连续编号的；一个有十个文档的索引使用数字 0 到 9（或 1 到 10）。不过，任何无歧义的标识符都可以。由于数据库需要把值映射回某一行，而不是映射回加入倒排索引的第 n 个文档，倒排索引要么额外存储一份文档 ID 到行的映射，要么直接把行标识符存进倒排列表。倒排列表几乎总是有序的，并且会以某种方式压缩。如果所有文档 ID 都小于 256，每个 ID 最多用八位存储。如果列表很稠密（即许多文档都包含某个词项），倒排列表可以只存数字之间的差值：id1、id2-id1、id3-id2，依此类推。这些差值总是小于 ID 本身，因此可以用更少的位存储。举个例子，假设一个索引有 300,000 个文档，其中 100,000 个包含单词 "who"。按原样存储每个 ID，每个倒排项需要 lg(n) = 19 位。但任意两个相邻 ID 之间的平均间隔（记住，倒排列表是有序的）只有 3，用两位就能存下。如果倒排项非常稠密，倒排列表可以存一个位图。若文档 n 包含某个词，则位图中第 n 位为 1，否则为 0。这种编码对 n 个文档恰好占用 n 位；当大约一半文档包含某个词项时，它就是最优的。对两个有序倒排列表求并集或交集很快，因为只需一趟 O(n) 扫描。对两个以位图形式存储的倒排列表求并集或交集则极快，因为支持向量指令的现代 CPU 可以在一条指令里对 128、256 甚至 512 位做 OR 或 AND。

位置数据

有些搜索引擎支持跨度查询和短语查询。跨度查询要求词项出现在文档中的特定位置，或彼此之间的距离不超过某个上限。例如 rules IN FIRST 5% 或 gotta NEAR/3 understand.。短语查询是跨度查询的一个特例，要求词语按精确顺序出现。为支持跨度和短语查询，倒排索引可以存储位置数据。倒排列表记录每个词项出现在哪些文档中，位置数据则记录词项出现在文档中的什么位置。由于大多数查询并非跨度查询或位置查询，位置数据通常与倒排列表分开存储，只在需要时才加载。

词频数据

有些搜索引擎支持对文档打分和排序。一种常见的打分方法是 BM25（下文会详细展开），它需要知道索引文档的一些统计信息：每个文档的长度、文档的平均长度、每个词项 t 在每个文档 d 中出现的次数，以及包含词项 t 的文档总数。索引会预先算好这些数据，以便为每次查询的结果打分时快速取用。

索引大小

所有被索引文档的集合称为语料库。索引大小通常是语料库大小的某个倍数，具体倍数取决于索引支持哪些功能。不含位置或评分数据的索引，大小可能约为语料库的 20%。带有重叠 token（用于支持精确匹配和正则表达式搜索）和位置数据的代码搜索索引，可能达到语料库大小的 300%。带位置数据和词频统计的英文文本索引，通常在语料库大小的 30% 到 50% 之间。这些数字会随文档长度、词汇量等因素变化，但能让你大致了解实现不同功能的相对成本。

分词器

每个被索引的文档都是一长串文本。把这串文本拆成词项，叫做分词（tokenizing）。不同的使用场景，尤其是不同的语言，需要不同的分词器。you're 是一个词项还是两个？{[] => []} 里到底有没有词项？Unicode 定义了一套不错的默认规则来识别词边界。分词之后，搜索引擎可能会在把词项加入倒排索引之前对其做修改或直接省略。去掉语言学上的后缀，叫做词干提取（stemming）。比如把 strangers 映射为 stranger，或者把 thinking 映射为 think，用户就能用一个词搜到包含该词任何形式的文档。有些词太常见，通常对搜索没什么用，这类词叫停用词（stop words），很多搜索引擎根本不索引它们。不过，一个把 new 当作停用词的索引，就无法区分包含 York 和包含 New York 的文档。一个同时丢掉 the 和 who 的索引，根本搜不到 The Who。停用词是一种取舍：索引更小、更快，但在这些词确实重要的场合下就没那么精确了。

打分：BM25 与 top-k

有些搜索场景只需要取回少数几条“最好”的结果，而不是所有匹配的结果。这和 SQL 不同——在 SQL 里，SELECT LIMIT 10 允许返回任意十行。判断哪些结果最好有很多种方法，其中之一是用 BM25 给它们打分。BM25 是一个公式，用来评估某个文档作为给定查询中所有词项的答案有多好。它把一个刻画词频的函数（某个词项在给定文档中出现的次数，相对于该文档长度）与一个刻画逆文档频率的函数（包含该词项至少一次的文档占多大比例）相乘，再把这项得分对查询中的所有词项求和。BM25 体现的直觉是：越罕见的词项越重要，而一个多次提到某个词项的文档，对该词项来说就是更好的结果。打分几乎总是和期望的结果数量一起使用，就像 SQL 的 LIMIT 10 那样。这就带来了一项重要的优化。倒排记录表（postings list）可以切分成块，每块带有词频统计。当索引要找出得分最高的 k 个文档时——也就是 top-k 查询——如果某些块的统计表明块内没有任何文档的得分能超过索引已经找到的前 k 个文档，索引就可以整块跳过这些倒排记录。这能显著加快 top-k 查询，在 k 较小时尤其明显。

段落、合并与可变性

构建倒排索引最简单的方式是一次性完成。只要索引足够小，就可以完全在内存中构建；毕竟，倒排索引不过是一个 Map>。超出内存容量的索引则要逐块写入。索引创建过程一直运行到内存写满，然后把一个自包含的倒排索引转储到磁盘上，代表前 n 篇文档。接着重复这一过程，直到内存再次写满，再把下一个 n 篇文档对应的自包含倒排索引转储到磁盘，依此类推。每个自包含的倒排索引称为一个段（segment）。处理查询时，整体索引必须在所有段中查找匹配项，然后合并结果。当然，很多数据集会随时间变化。语料库会随着文档的加入而增长。新文档可以先在内存中攒批，攒够一个段再写出，也可以立即逐条加入磁盘上的可变数据结构。这种可变存储的布局效率不如不可变段，但它的优势在于——可变：无需事先知道所有文档，就能高效地添加文档。之后每次查询时，可变存储中的文档会与所有不可变段一起被搜索。TIN 使用一个包含倒排列表的可变段，相当于不可变段的低效版本。由于可变段很慢，它最终必须被封存（sealed），转换为不可变段。在下面的示例段中试试插入、更新和删除。为简单起见，示例最多展示两个不可变段。当可变段达到大小上限时，示例会立即把它合并进较小的那个不可变段。而在实际中，被封存的可变段会先作为一个小型独立不可变段存在一段时间。最终，段的数量会变得太多。一个要在成百上千个小段中搜索的索引，光是跟踪所有段并合并查询结果就要消耗不少 CPU 和内存。因此，倒排索引通常需要合并（merge）段。合并时，两个或多个段变成一个更大的段。如果文档 ID 是各段局部的连续编号，那么它们都必须重新分配；一个段中的文档 i 不能与另一个段中的文档 i 混淆。合并的算法很直接：只需对词项词典和每个倒排列表做一次线性扫描。但合并需要大量磁盘空间和大量 I/O。合并以两个或多个不可变段为输入，产生一个新的输出段，其大小等于所有输入段之和，再减去已删除文档的倒排项。每个段很容易达到数 GB，因此一次合并过程可能要读写几十 GB 的数据，并临时占用同样多的额外磁盘空间。段合并始终是一种权衡：一边是合并的 I/O 成本，另一边是保留大量段所带来的效率损失。但这只是插入文档的情况。删除文档呢？从倒排列表中间删除文档 ID 并不现实，那需要重新压缩列表的一部分甚至全部。所以删除只是创建一个墓碑（tombstone）。墓碑是表中的一条记录，表示某个文档 ID 不再有效。倒排索引仍会把该文档 ID 作为查询结果产生出来，但它会将每个结果与墓碑比对，并在返回给调用方之前移除该 ID。这又带来一个权衡。每个被删除的文档仍然占用索引中的磁盘空间，并且浪费 CPU 时间——要从倒排列表中取出它，再把它从结果列表中过滤掉。而清除墓碑的唯一办法就是合并段，并用墓碑列表过滤写入输出段的文档 ID。有时，当一个段中很大一部分（接近一半）文档已被删除时，单独重写该段可能是值得的，只为清除这些已删除的文档。更新文档无非是删除（打墓碑）其旧版本，再插入新版本。这里描述的不可变段无法做原地更新。

Postgres 中的实现方式

最后，我们来看看倒排索引在 Postgres 中是如何实现全文搜索的。怎么才能让它跑起来？

CREATE INDEX ON songs USING tin(lyrics);
SELECT title, performer
 FROM songs
 WHERE lyrics ==> 'make you cry'
 ORDER BY tin.score(ctid) DESC
 LIMIT 10;

每个文档就是某一行的某个文本列的值。所以如果索引建在表 songs 的 lyrics 列上，那么每首歌的歌词就是一个文档。倒排索引必须提供行标识符，也就是 ctid，告诉 Postgres 执行器该去取哪十行 title 和 performer。整个倒排索引得有个地方存，最好是一个记录 WAL 的索引关系，这样 Postgres 的复制和备份才能把它带上。段被删除时，它原来占用的存储会被释放，但关系中间的空洞没法还给操作系统。索引只能自己维护一份空闲页列表，留着以后复用。合并通常在段超过某个大小阈值、或者它的 tombstone 列表超过文档总数的一定比例时触发。但我们绝不想在 INSERT、UPDATE 或 DELETE 里内联执行合并（别忘了：几十 GB 的读写，可能要好几分钟）。所以需要任务队列和后台维护 worker。既然是 Postgres，VACUUM 就得能用。VACUUM 会从堆中移除死行版本，并要求每个索引删掉指向它们的条目。VACUUM FULL 会重写表中的所有行，ctid 因此改变。如果倒排索引存了 ctid，就得跟着更新。文档的插入和删除必须关联事务号，这样在提交之前对其他事务不可见，也能回滚。索引必须返回所有可见的结果，且不返回任何不可见的。即便有这个要求，top-k 查询也必须真的返回 k 行。为了让 COUNT(*) 和 top-k 查询高效工作，倒排索引需要能访问行级可见性和页级可见性映射。查询经常把倒排全文约束（比如 lyrics ==> 'make you cry'）和传统 SQL 约束（比如 year = 1987）组合在一起。查询规划器需要知道什么时候用全文索引，什么时候用 b-tree，什么时候两者都用、再用位图求交合并结果。对多个列都有全文约束的查询，比如 title 和 lyrics，应该用 CustomScan 把过滤完全放在索引实现内部完成，这比每列各返回一个结果集、再让 Postgres 求交要快得多。

为 Postgres 找到最优解

我们如何解决这些挑战、成效如何，详见 TIN 深度解析——PlanetScale 为 Postgres 打造的全新全文搜索扩展。