TIN：为 Postgres 带来的全文搜索
PlanetScale 发布 Postgres 全文搜索扩展 TIN，直接拿 48 位 ctid 当 posting 的原生格式，在 85 GB、1.5 亿篇文档的基准里吞吐量至少比 ParadeDB、pg_textsearch 与内置 GIN 高 8 倍，建索引用 8 分 10 秒。
中文
复制
客户向我们提得最多的 Postgres 需求之一，就是全文搜索。今天我们很高兴地发布 TIN：一个快速、功能完备、可靠的 Postgres 全文搜索扩展。TIN 是「Text INdex」的缩写，它做的也正是这件事。TIN 已作为 GA 版本立即可用，面向所有 Postgres 与 Neki 数据库。来看看：
CREATE INDEX an_index_name ON table_name USING tin(text_column_name);
SELECT * FROM table_name
WHERE text_column_name ==> 'some words';
我们做 TIN，是因为我们相信一个好的文本索引应当支持：
- 布尔表达式、短语查询和 span 查询
- 词项的模糊匹配、通配符匹配和正则表达式匹配
- 大小写与重音折叠
COUNT(*)查询和按 BM25 打分的 top-k 查询
而一个在 Postgres 里好用的文本索引，必须在支持以上全部能力的同时，还能应对 join、跨越全文列与其他列类型的复杂 WHERE 子句、持续更新、复制、备份，以及正确的事务可见性。Postgres 上至少已经有三款现成的文本搜索索引，但没有一款满足全部这些要求。TIN 满足了。而且 TIN 真的快得令人瞠目。
TIN 用来做什么
应用开发者用文本索引构建各种搜索功能。电商平台可能需要检索包含全部关键词的前十件商品：
SELECT * FROM products
WHERE description ==> 'stretch denim jeans'
ORDER BY tin.score(ctid) DESC
LIMIT 10
法律取证平台可能需要返回包含某一组关键词中任意一个的全部文档，但完全不关心排序：
SELECT * FROM emails
WHERE body ==> '[insider trading conspiracy]'
图片标签平台可能想显示带有某个标签的图片的精确数量：
SELECT COUNT(*) FROM photos
WHERE tags ==> '"san francisco"';
大多数应用还需要插入、更新和删除文档，而且是在继续查询索引的同时进行。搜索查询必须在新行或改动过的行提交之后，立刻按它们返回匹配结果。
TIN 的性能与基准测试
我们跑了基准测试，评估上述这些以及更多场景下的性能。我们尝试了这些负载：
- 包含合取（必须包含全部词）、析取（必须包含任一词）和短语（必须按顺序包含全部词）查询，以及三者混合的查询。
- 统计文档数量的查询，以及按 BM25 分数取前 k 的查询。
- 在基准查询负载进行的同时，有无客户端向索引写入新数据两种情况。
负载与语料
我们拿 TIN 与多种文本语料做过对比测试：整个维基百科、总计 2.3 TB 的 Reddit 评论集合，以及一个我们直接叫「pile」的混合负载，其中包含 797 GB 的开放获取研究论文、法律文书、公有领域书籍和 Enron 邮件。本文分享的基准结果来自 Stack Exchange 问答的一份导出数据：85 GB 语料，1.5 亿篇文档。因为这份语料没有标准的查询轨迹，我们用采样办法生成了合成查询：抽取长度为 2 到 15 个词项的子串。每个子串我们按三种方式解释：合取、析取和短语查询，共 1,719 条查询。
测试环境
我们的基准测试跑在一台 AWS i7i.8xlarge EC2 实例上，本地 NVMe 存储，CPU 支持 AVX-512。对每一款文本搜索扩展，我们都在一个隔离容器里装了 Postgres 18.6，限制为 8 个 vCPU 和 32 GB 内存。这个规格小到足以看出各索引系统在索引不能全部装进 Postgres 缓冲区时的表现。各基准阶段顺序执行，所以各引擎之间不会争夺资源。我们选择独立的 EC2 实例，是为了把运维开销和复制的影响降到最小，也为了让任何想复现我们对竞品文本搜索索引的基准测试的人，能用同样的实例规格和容器限制来做。为了给 Postgres 容器施加搜索流量，我们用了 ParadeDB Benchmarker。我们有一个分叉版本，会在开始测量前预热，并增加了读取字节数和写入 WAL 字节数的指标。除三项之外，我们把所有 Postgres 参数都保持在 Benchmarker 给出的默认值：max_parallel_workers 设为 8（原为 40）、shared_buffers 设为 24 GB（原为 128 MB）、maintenance_work_mem 设为 24 GB（原为 64 MB），以尽量匹配容器的资源。我们把 Benchmarker 跑在与目标 Postgres 服务器同一台 EC2 实例上，以确保网络延迟不影响测量结果。每个场景中，我们都拿 TIN v1.0.2 与所有至少能跑起该负载的其他 Postgres 文本搜索索引对比：ParadeDB v0.25.2、pg_textsearch v1.4.0，以及 Postgres v18.6 内置的 GIN 索引。除 TIN 之外，只有 ParadeDB 完成了全部基准测试。
索引构建时间与大小
各索引的大小在语料的 33% 到 61% 之间，准备、构建和收尾耗时从 8 分钟到 129 分钟不等。除 TIN 外的三个引擎都在容器配置的 32 GB 限制下失败了，所以仅在构建索引时，我们按表中所示提高了可用内存。开始跑查询之前，我们把所有容器的内存都调回 32 GB。
| 总耗时 | 索引大小 | 所需内存 | |
|---|---|---|---|
| TIN | 8m10s | 50.7 GB | 32 GB |
| ParadeDB | 19m20s | 52.1 GB | 64 GB |
| pg_textsearch | 26m49s | 41.5 GB | 128 GB |
| Postgres GIN | 2h09m04s | 28.0 GB | 64 GB |
混合查询，取前 10 并排序
我们的第一项基准把 TIN 与 ParadeDB 对比，负载是混合查询（合取、析取、短语），按 BM25 分数取前 10 条结果，索引无并发写入。TIN 每秒处理的查询数是 ParadeDB 的 25 倍，p99 延迟低 26 倍。GIN 无法完成这项基准，因为它在执行析取搜索时内存耗尽。pg_textsearch 也无法完成，因为它_只_处理析取搜索。
合取与短语查询，取前 10 并排序
下一项基准把 TIN 与 ParadeDB、Postgres GIN 对比，负载是按前 10 取合取与短语查询，无并发写入。TIN 与 ParadeDB 用 BM25 排序，GIN 用 ts_rank_cd 排序。TIN 处理的查询数是 ParadeDB 的 10 倍、GIN 的 541 倍，p99 延迟分别低 6 倍和 1,356 倍。pg_textsearch 依旧缺席，因为它只处理析取查询。
带并发写入的析取查询
第三项结果把 TIN 与 ParadeDB 和 pg_textsearch 对比，负载是析取查询，按 BM25 分数取前 10 条结果，同时有一个并发客户端以每秒 1,000 条 UPDATE 的速度写入。TIN 处理的查询数是 pg_textsearch 的 36 倍、ParadeDB 的 57 倍，p99 延迟分别低 24 倍和 36 倍。在十分钟的运行中，TIN 完成了 270,279 次更新，ParadeDB 完成了 185,584 次，pg_textsearch 只完成了 735 次。ParadeDB 接受写入的方式牺牲了读吞吐和延迟。pg_textsearch 的读取端在有写入和没有写入时都保持 3.5 QPS，因为持续的读流量让写流量永远拿不到需要的锁，所以写入在几秒之后就停滞了。GIN 依然缺席，因为它在析取查询上内存耗尽。
当索引能全部装进内存
在开头我们说 TIN 快得令人瞠目。最后一张图展示的是当索引能完整装进 shared buffers 时，TIN、ParadeDB 和 Postgres GIN 各自的表现。这个负载统计（但不排序）在 8.0 GB 的维基百科语料上匹配某条析取查询的文档数。pg_textsearch 在这里缺席，因为它只能做 top-k 查询，不能做统计查询。
完整结果
图大概已经够了，但它还没有覆盖我们全部的使用场景。下面用表格给出同样的场景，外加另外几个。其中「MB/query」一列显示每次查询时各索引从磁盘或块缓存读取了多少数据。TIN 在这方面数字更低，这正是它更快的原因之一，同时也降低了 TIN 查询对块缓存和 I/O 容量的影响，也就是说，同一台服务器上的其他查询也能保持快速。
Conjunction, disjunction, and phrase queries; top-10
┌────────────────────────────────────────────────────────────────────┐
│ QPS p99 MB/query Updates │
├─────────────────────────┬───────┬──────────┬───────────┬───────────┤
│ TIN - read-only │ 199 │ 256ms │ 65 │ │
│ - with updates │ 172 │ 284ms │ 88 │ 271,398 │
├─────────────────────────┼───────┼──────────┼───────────┼───────────┤
│ ParadeDB - read-only │ 7.9 │ 6,765ms │ 582 │ │
│ - with updates │ 6.0 │ 7,990ms │ 591 │ 193,487 │
└─────────────────────────┴───────┴──────────┴───────────┴───────────┘
Conjunction and phrase queries; top-10 (read-only)
┌───────────────────────────────────────────────┐
│ QPS p99 MB/query │
├───────────────┬───────┬───────────┬───────────┤
│ TIN │ 242 │ 212ms │ 73 │
├───────────────┼───────┼───────────┼───────────┤
│ ParadeDB │ 24 │ 1,279ms │ 668 │
├───────────────┼───────┼───────────┼───────────┤
│ Postgres GIN │ 0.4 │ 288,066ms │ 595 │
└───────────────┴───────┴───────────┴───────────┘
Disjunction queries; top-10
┌────────────────────────────────────────────────────────────────────────┐
│ QPS p99 MB/query Updates │
├──────────────────────────────┬───────┬───────────┬─────────┬───────────┤
│ TIN - read-only │ 148 │ 324ms │ 48 │ │
│ - with updates │ 125 │ 354ms │ 77 │ 270,279 │
├──────────────────────────────┼───────┼───────────┼─────────┼───────────┤
│ ParadeDB - read-only │ 17 │ 2,385ms │ 303 │ │
│ - with updates │ 2.2 │ 12,634ms │ 394 │ 185,584 │
├──────────────────────────────┼───────┼───────────┼─────────┼───────────┤
│ pg_textsearch - read-only │ 3.5 │ 8,646ms │ 11,639 │ │
│ - with updates │ 3.5 │ 8,409ms │ 11,656 │ 735 │
└──────────────────────────────┴───────┴───────────┴─────────┴───────────┘
Conjunction, disjunction, and phrase queries; COUNT(*) (read-only)
┌─────────────────────────────────────────┐
│ QPS p99 MB/query │
├───────────┬───────┬──────────┬──────────┤
│ TIN │ 179 │ 438ms │ 97 │
├───────────┼───────┼──────────┼──────────┤
│ ParadeDB │ 10 │ 2,704ms │ 544 │
└───────────┴───────┴──────────┴──────────┘
Disjunction queries; COUNT(*); Wikipedia corpus (read-only)
┌───────────────────────────────────────────────────┐
│ QPS p99 MB/query │
├───────────────┬──────────┬─────────────┬──────────┤
│ TIN │ 10,260 │ 2ms │ 1.7 │
├───────────────┼──────────┼─────────────┼──────────┤
│ ParadeDB │ 291 │ 95ms │ 22 │
├───────────────┼──────────┼─────────────┼──────────┤
│ Postgres GIN │ 1.4 │ 30,292ms │ 2.5 │
└───────────────┴──────────┴─────────────┴──────────┘
如你所见，在各种各样的场景里，TIN 的吞吐量至少比其他方案高 8 倍，从磁盘读取的数据少得多，而且即使索引每秒更新数百行，性能也只下降一点点。
为什么 TIN 这么快
TIN 在基准测试里的表现可能让人难以相信。为了使它更可信，或者至少满足读者的好奇，我们会解释一些让它如此快的架构选择。简单说：所有文档 posting 用的都是 Postgres 的 ctid，而不是连续的文档标识符，这使得它很适合在现代 CPU 上做高度向量化的交集与并集运算。
文档标识
文本索引需要为它索引的每个文档的每个版本准备一个标识符。它把这些标识符分组，装进高度压缩的 posting 链表；每个 posting 链表记录包含某一个给定词的全部文档。在大语料里，像「the」这样的常用词的 posting 链表可能包含数十亿条 posting，而像「xyz-9876」这样的词项的 posting 链表只有寥寥几条。
大多数文本搜索系统把索引组织成段（segment）。一个段里存在 posting 的那 n 篇文档，通常被赋予 1 到 n 的文档标识符。顺序的文档标识符让 posting 链表可以用 delta 编码、bit-packing 等技巧做高度压缩。但这也意味着不同段里的文档标识符是各自独立分配的；第 4 段里的文档 ID 42 和第 7 段里的 ID 42 是完全不同的两篇文档。
TIN 也把索引组织成段，但目的不是给文档编号。TIN 直接拿 Postgres 的 ctid 值当文档标识符。
存储在 Postgres 表里的每一行（tuple）的每一个版本，都有一个对应的 ctid 值。ctid 是「current tuple identifier」（当前元组标识符）的缩写。任何插入或更新的行都会得到一个新的 ctid。它是一个 48 位数，直接标识该元组在 Postgres 堆里的物理位置。在文本里表示为 (<block number>, <offset number>)，高 32 位是块号，低 16 位是块内的偏移量。下文我们把 <block number> 这部分称为「页号」或「页」。
给定 ctid 为 (190, 17)，我们就知道它代表的元组在 190 号页的第 17 个槽位。瞬间完成 O(1) 查找！你甚至可以直接用 ctid 从堆里查询并取出整行：
-- retrieve the first 10 rows from "books" in physical heap order
SELECT ctid, id, title FROM books ORDER BY ctid LIMIT 10;
-- no scan required! instant O(1) lookup of the row
SELECT * FROM books WHERE ctid = '(190, 17)';
TIN 直接使用 ctid，是因为 Postgres 内部就在用 ctid。实现新索引类型的 Postgres 扩展必须返回 ctid。Postgres 的 bitmap scan 背后是可能不精确的 ctid 位图。Postgres 的内置索引类型（b-tree、GIN、GiST 和 hash）都用 ctid 作为它们的 posting。ctid 遍布 Postgres 的各个角落。
要在 Postgres 内部工作，一个赋予连续标识符的文本搜索系统必须在某个时刻把这些标识符转换回 ctid，Postgres 才能使用。ParadeDB 和 pg_textsearch 都维护了一套单独的数据结构专门做这个映射。如果一次文本搜索命中 1,000 万行，ParadeDB 和 pg_textsearch 就得在它们的 ctid 映射里查 1,000 万个标识符。TIN 完全省掉了这部分工作。
48 位标识符很疯狂
常规的 posting 链表压缩技巧对不连续的 48 位数效果不好。delta 编码在每个页边界都会断掉，而位图又太稀疏，不划算。所幸 Postgres 页的一些有趣性质让两级位图编码变得可行。一个 8KB 的页最多只能放 291 个元组（8192 字节减去 24 字节页头，再除以每个非空元组至少 28 字节），而对于带 TEXT 等列的表结构，页里往往只有 32 个或更少的元组。所以页号列表稠密到可以用位图，而在每一页内部，偏移号列表也稠密到（且足够小到）可以用每页的小位图。
相对于直接存 48 位 ctid 值，节省可以相当可观。在整个语料上，高频词项接近每条 posting 1 bit，中频词项大约每条 7 bit，低频词项可以接近每条 25 bit。只出现一次的词项根本不存成位图。
省掉的工作与向量化
TIN 的页级位图（哪些页包含某个词项）是 256 位，正好装进任何支持 AVX2 及以上指令的 x86 CPU 的向量寄存器。这带来了几项优化。
考虑查询 the AND rareword。TIN 一次对 256 位（页）做页级位图的 AND。交集中不存在的任何一位，都对应一个 TIN 完全不需要解码其偏移级位图的页。
对于 the OR rareword 这种 COUNT(*) 析取查询，TIN 常常完全跳过读取 posting 链表。TIN 的索引元数据里存有每个词项的精确 posting 数量。如果两个词的页级位图没有共同位，它们析取后的计数就等于这两个精确 posting 数量之和。
每个页级位图都装得进一个 AVX2 寄存器，每个偏移级位图都装得进一个 AVX-512 寄存器或两个 AVX2 寄存器。合取与析取查询不过是在这些向量寄存器上分别执行 AND 和 OR 指令。需要统计匹配数量的查询可以用 CPU 原生的 POPCNT 指令来数结果位图里的位。昂贵的循环和分支指令基本都能避开。
需要返回整行而不是计数的查询，直接从位的位置算出 ctid，而不必去磁盘上查。置位的位置_就是_ ctid。
TIN 从某个段返回给 Postgres 的文档 ctid，天然是按堆顺序标识页以及页内元组的。这意味着当 Postgres 需要从堆里读取匹配的元组时，是按堆顺序进行的。即便用现代 NVMe 磁盘，顺序访问也远快于随机访问；TIN 白得了这项优化。
解决 MVCC
TIN 返回的结果是 MVCC 正确的，也就是说，在任意时刻执行的一条语句，只会看到或作用于当前对它可见的元组。这意味着每个基于堆的查询结果都需要相对当前快照做可见性检查。
堆检查
有几种不同的做法。有些查询天然就要做堆检查：
SELECT a, b, c FROM lyrics WHERE content ==> 'give you up'
因为这条查询返回的是真正的堆数据（a, b, c 三列），TIN 无论如何都必须把 ==> 'give you up' 返回的所有匹配 ctid 从堆里取出来。当 TIN 向 Postgres 索取每个 ctid 背后的物理元组数据时，Postgres 会告诉 TIN 该元组对当前快照是否可见。可见就返回；不可见就跳到下一个匹配的 ctid，直到返回所有可见的匹配。
可见性映射
另一些查询形状可以像 Postgres 的「Index Only Scan」那样执行，答案直接从索引返回，不碰堆（或者至少希望不碰整个堆）。考虑这样一条只做计数的查询：
SELECT COUNT(*) FROM lyrics WHERE content ==> 'give you up'
如果每个堆页都被标记为全可见，TIN 就能在不碰任何一个堆页的情况下返回这个计数。
当然，不是所有数据都是静态的，在堆被改动的情况下，TIN 会做额外的优化，通过与 Postgres 可见性映射直接做交集，确保它只统计可见的行。TIN 的页级位图恰好是正确的机制，可以与同样是页级位图的 Postgres 可见性映射高效求交。只有在非全可见页上的 ctid 才需要去堆里核对。通常，Postgres 索引会返回所有匹配的 ctid，不管可见与否，再由 Postgres 执行器逐个做可见性检查。TIN 规划自定义扫描，把可见性检查搬进 TIN 自己内部，从而能利用页级位图上的向量指令。
VACUUM 与 TIN 的存活位图
支持删除文档的文本索引，通常会维护某种适合自身引擎的「墓碑」列表。TIN 也不例外。TIN 为每个段维护一个存活位图，每个 ctid 一位，组织方式与页级、偏移级位图相同。当 VACUUM 运行并判定某个 ctid 已从堆中删除（因 UPDATE 或 DELETE 所致）时，TIN 会清掉该 ctid 的存活位。含有至少一个被清位的页会被分组标记，当查询触及某个被标记的页组时，TIN 会把 posting 链表里的偏移位图与该存活位图做 AND，因此它永远不会返回或统计一个真正被删除的元组。
段与合并
第一次为一张表创建新索引时，TIN 会创建 n 个不可变段，每个段包含该表在堆中 1/n 的页的 posting。随着数据变动，TIN 会创建可变段，这种段搜索效率较低，但便于插入新文档。最终，一个后台 worker 会把每个可变段提升为不可变段：不再变化，但搜索效率高得多。
过一段时间，TIN 会开始把不可变段合并成更大的不可变段。这也在后台进行。
使用连续文档标识符的文本索引系统在创建合并后的新段时，必须重新给所有文档编号。如前所述，第 4 段里的文档 ID 42 与第 7 段里的 ID 42 不是同一篇文档。所以当第 4 段和第 7 段合并时，必须对合并后的文档集合重新编号，每个段的全部数据都要重新打包、重新压缩、重新写入。合并两个段的存储开销虽然算不上原来的 2 倍，但可以接近。
TIN 既没有重新编号的问题，也没有由此产生的写放大。因为 TIN 用 Postgres 的 ctid 值作为文档标识符，没有任何东西需要重新编号。一条像 (190, 17) 这样的 posting 在每个段里都是同一个意思。页级与偏移级位图在每个段里也是同一个意思。当 TIN 合并段时，每个旧段里的许多位图可以在新段里原样复用。它们既不必重新压缩，甚至不必复制；TIN 可以直接把存在磁盘上的位图的归属从旧段转到新段。这减少了写放大，也省掉了通常伴随段合并的大部分 CPU 与 I/O 开销。
小结
所以这就是为什么 TIN 在每一项基准里都至少快 8 倍：选择 ctid 作为索引里每条 posting 的原生格式，带来了一系列下游效果。
如果你想知道 TIN 在你的文本数据上有多快，可以进一步了解它的功能，或者直接跳到入门指南。我们期待看到你用它做出什么。