TIN：面向 Postgres 的全文搜索扩展
， |
全文搜索是我们客户最常请求的 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，是因为我们相信一个好的文本索引应当支持：
- 布尔表达式、短语查询和跨度查询
- 术语的模糊匹配、通配符和正则表达式匹配
- 大小写和音调折叠
COUNT(*)查询和基于 BM25 排名的 Top-k 查询
在 Postgres 中，一个好的文本索引必须支持上述所有功能，同时还要处理连接、跨全文搜索及其他列类型的复杂 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 问答导出：一个包含 1.5 亿个文档的 85 GB 语料库。由于该语料库没有标准的查询轨迹，我们通过采样长度为 2 到 15 个词元的子串生成了一份合成轨迹。我们将每个子串以三种方式解释：作为合取查询、析取查询和短语查询，共生成 1,719 个查询。
测试环境
我们在 AWS i7i.8xlarge EC2 实例上运行基准测试，配备本地 NVMe 存储和现代 AVX-512 架构 CPU。对于每个全文搜索扩展，我们都在一个隔离容器中部署 Postgres 18.6，限制为 8 vCPU 和 32 GB 内存。这个规模足够小，可以展示当索引无法完全装入 Postgres 缓冲区时各索引系统的表现。基准测试阶段顺序执行，因此各引擎之间不争夺资源。我们选择独立的 EC2 实例，以最小化运维开销和复制的影响，并确保任何希望复现我们基准测试（对比不同全文搜索索引）的人都能使用相同的实例类型和容器限制完成复现。
为了向 Postgres 容器发起搜索流量，我们使用了 ParadeDB Benchmarker，并基于它维护了 一个 fork 版本，会在开始测量前预热，并增加了读取字节数和 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 | 8 分 10 秒 | 50.7 GB | 32 GB |
| ParadeDB | 19 分 20 秒 | 52.1 GB | 64 GB |
| pg_textsearch | 26 分 49 秒 | 41.5 GB | 128 GB |
| Postgres GIN | 2 小时 9 分 4 秒 | 28.0 GB | 64 GB |
混合查询（Top-10 排序）
我们的第一个基准测试将 TIN 与 ParadeDB 进行对比，负载包含混合查询（合取、析取和短语查询），按 BM25 分数返回前 10 条结果，期间索引没有并发写入。TIN 的每秒查询吞吐量是 ParadeDB 的 25 倍，且 p99 延迟低 26 倍。GIN 无法完成此基准测试，因为执行析取查询时内存不足。pg_textsearch 也无法完成，因为它仅支持析取查询。
合取与短语查询，Top-10 排序
接下来的基准测试将 TIN 与 ParadeDB 及 Postgres GIN 进行对比，执行 Top-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 的速度快得惊人。
最后一张图展示了当索引完全适配于共享缓冲区时，TIN、ParadeDB 和 Postgres GIN 的性能表现。该工作负载统计匹配维基百科（8.0 GB 语料库）中析取查询的文档数量（但不进行排序）。pg_textsearch 未参与此测试，因为它仅支持 Top-K 查询，不支持计数查询。
完整结果
这些图表或许已经足够了，但并未覆盖所有使用场景。下面以表格形式列出了上述场景以及更多场景。其中“MB/query”列显示了每个查询中索引从磁盘或块缓存读取的数据量。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 在基准测试中展现的性能让人难以置信。为了增加说服力，或至少满足读者的好奇心，下文将简要解释那些让 TIN 速度如此之快的架构选择。简而言之：所有文档的位置信息都直接采用 Postgres 的 ctid，而非连续的文档标识符，这使得在现代 CPU 上执行高度向量化的交集与并集操作成为可能。
文档标识
全文索引需要为它所索引的每个文档版本分配一个标识符。这些标识符会被分组为高度压缩的位置列表（postings list），每个位置列表记录包含某个特定词汇的所有文档。在大型语料库中，像 "the" 这样常见词汇的位置列表可能包含数十亿条记录，而像 "xyz-9876" 这样罕见词汇的位置列表则可能只有寥寥几条。
大多数全文搜索系统将索引组织为多个段（segments）。通常情况下，某个段中 n 个存在位置信息的文档会被分配标识符 1 到 n。连续的文档标识符允许使用差异编码（delta-encoding）和位打包（bit-packing）等技巧对位置列表进行高效压缩。但这也意味着不同段中的文档标识符是独立分配的；第 4 段中的文档 ID 42 与第 7 段中的 ID 42 代表的是完全不同的文档。
TIN 也将其索引划分为段，但目的并非用于文档编号。相反，TIN 直接使用 Postgres 的 ctid 值作为文档标识符。
Postgres 表中存储的每个行（元组）的每个版本都有一个关联的 ctid 值。ctid 是 "current tuple identifier"（当前元组标识符）的缩写。任何插入或更新的行都会获得一个新的 ctid。它是一个 48 位数字，直接指向该元组在 Postgres 堆表中的物理位置。以文本形式表示为 (<块编号>, <偏移量>)，其中高 32 位指示块编号，低 16 位指示块内的偏移量。从今往后，我们将 <块编号> 部分称为 "页号" 或 "页"。
给定 ctid 为 (190, 17)，我们知道它代表的元组位于第 190 页的第 17 个槽位。这就是即时的 O(1) 查找！甚至可以直接使用 ctid 查询并从堆表中检索行：
-- 按物理堆顺序获取 "books" 表的前 10 行
SELECT ctid, id, title FROM books ORDER BY ctid LIMIT 10;
-- 无需扫描！ 直接以 O(1) 复杂度查找该行
SELECT * FROM books WHERE ctid = '(190, 17)';
TIN 直接使用 ctid，因为 Postgres 内部依赖 ctid。Postgres 扩展在实现新索引类型时，必须返回 ctid。Postgres 的位图扫描（bitmap scans）背后是由可能丢失的 ctid 位图支撑的。Postgres 的内置索引类型（B-tree、GIN、GiST 和 Hash）也将 ctid 作为其倒排链项（postings）。在 Postgres 内部，ctid 无处不在。
要在 Postgres 中运作，任何分配顺序标识符的全文搜索系统，最终都必须将这些标识符转换回 ctid，以便 Postgres 能处理它们。ParadeDB 和 pg_textsearch 都维护了独立的数据结构来执行此映射。如果全文搜索匹配了 1000 万行数据，ParadeDB 和 pg_textsearch 就需要在它们的 ctid 映射表中查询 1000 万次标识符。TIN 完全避免了这部分开销。
48 位标识符极其棘手
常规的倒排链项压缩技术并不适用于不连续的 48 位数字。增量编码在页边界处失效，而位图又过于稀疏，效率低下。幸运的是，Postgres 页面的某些特性让两级位图编码变得可行。一个 8KB 的页面永远无法包含超过 291 个元组（8192 字节，减去 24 字节的页头，再除以每个非空元组至少占用的 28 字节）。对于包含 TEXT 等列的表结构，页面中通常只包含 32 个或更少的元组。因此，页号列表足够密集，可以使用位图；而在每个页面内部，偏移号列表既足够密集又足够小，可以为每页使用小型位图。
与直接存储 48 位 ctid 值相比，节省的空间可能相当可观。在整个语料库上，高频词的压缩率接近每倒排链项 1 位，中频词稳定在每倒排链项 7 位左右，低频词则接近每倒排链项 25 位。仅出现一次的词根本不以位图形式存储。
工作省略与向量化
TIN 的页级位图（记录哪些页包含某个词）有 256 位，正好能装进任何支持 AVX2 及以上指令集的 x86 CPU 的向量寄存器里。这带来了好几项优化。
以查询 the AND rareword 为例：TIN 对页级位图做 AND 运算，每次处理 256 位（即 256 个页）。交集里不存在的位，对应的页其偏移级位图 TIN 根本不用解码。
对于 COUNT(*) 形式的析取查询，比如 the OR rareword，TIN 经常可以完全跳过读取 postings list。因为 TIN 的索引元数据里存着每个词的精确 posting 数量：如果两个词的页级位图没有任何共同位，它们析取结果的计数就是两者 posting 数之和。
每个页级位图都能装进单个 AVX2 寄存器，每个偏移级位图则能装进一个 AVX-512 寄存器或两个 AVX2 寄存器。合取和析取查询分别就是这些向量寄存器上的 AND 和 OR 指令。需要统计匹配数量的查询可以直接用 CPU 原生的 POPCNT 指令来数结果位图中的位。昂贵循环和分支指令基本都能避免。
需要返回行而非计数的查询，直接从位的位置算出 ctid，不用去磁盘上查。置位的位置本身就是 ctid。
TIN 从某个 segment 返回给 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 该元组对当前快照是否可见。如果可见，TIN 就返回该数据；否则，TIN 继续处理下一个匹配的 ctid，直到返回所有可见的匹配项。
可见性映射
其他类型的查询也可以类似地执行 Postgres 的“仅索引扫描”，直接从索引返回结果，而不触及堆（或者至少希望不触及整个堆）。考虑如下这种仅统计计数的查询：
SELECT COUNT(*) FROM lyrics WHERE content ==> 'give you up'
如果所有堆页面都被标记为全可见，TIN 可以在不接触任何堆页面的情况下返回该计数值。
当然，并非所有数据都是静态的。对于发生过变更的堆，TIN 会进行额外的优化，通过与 Postgres 的可见性映射直接相交，确保只统计可见行。TIN 的页级位图恰好是高效的机制，可以与 Postgres 的可见性映射（也是页级位图）进行高效相交。只有那些并非全可见页面上的 ctid 才需要与堆进行检查。通常，Postgres 索引会返回所有匹配的 ctid，而不管其可见性，随后由 Postgres 执行器逐个检查可见性。TIN 规划了自定义扫描，将可见性检查移入 TIN 内部，从而利用页级位图上的向量指令加速处理。
VACUUM 与 TIN 的生命周期位图
支持删除文档的全文索引通常会维护某种与引擎机制相适应的“墓碑”列表，TIN 也不例外。它按段落维护活跃度位图，每个 ctid 占用一位，其组织方式与页面级和偏移位图类似。当 VACUUM 运行并判定某个 ctid 已从堆表中删除（由 UPDATE 或 DELETE 操作引起）时，TIN 会清除该 ctid 的活跃位。若某个页面组中存在至少一个被清除的位，该页面组会被标记；当查询触及这些被标记的页面组时，TIN 会将倒排列表中的偏移位图与活跃度位图进行按位与运算，从而确保绝不返回或统计已真正删除的元组。
分段与合并
初次为表创建索引时，TIN 会生成 n 个不可变段，每个段包含堆表中该表相关页面的 1/n 的倒排数据。随着数据变更，TIN 会创建可变段；虽然可变段的搜索效率较低，但便于插入新文档。最终，后台进程会将每个可变段提升为不可变段，使其保持数据不变，同时显著提升搜索效率。
随着时间推移，TIN 会在后台开始将多个不可变段合并为更大的不可变段。
使用顺序文档标识符的全文索引系统，在创建新的合并段时，必须对所有文档重新编号。如前所述，第 4 段中的文档 ID 42 与第 7 段中的 ID 42 并非同一文档。因此，当第 4 段和第 7 段合并时，必须对合并后的文档集应用新的编号，并对每个段的全部数据进行重新打包、重压缩和重写。虽然合并两个段的存储开销并非严格的两倍，但已非常接近。
TIN 不会遇到重新编号问题，也避免了由此引发的下游写放大效应。
由于 TIN 使用 Postgres 的 ctid 值作为文档标识符，无需任何重新编号。(190, 17) 这样的 posting 在每个 segment 中的含义完全相同，页级和偏移级的 bitmap 也一样。因此 TIN 合并 segment 时，旧 segment 的很多 bitmap 可以原封不动地在新生成的 segment 中复用——不仅无需重新压缩，甚至无需复制，直接把磁盘上存储的 bitmap 从旧 segment 划归新 segment 即可。这大大降低了写放大，也省去了 segment 合并通常带来的大部分 CPU 和 I/O 开销。
总结
这就是 TIN 在所有基准测试中至少快 8 倍的原因：一切源于选择 ctid 作为索引中每个 posting 的原生格式所带来的连锁效应。