【全文检索引擎】Postings 与 codec：freqs、positions、skip 与 impacts

FST 词典 解决「term 在哪里」；postings 解决「哪些 doc 包含该 term，以及每个 doc 上出现了几次、在什么位置」。Lucene 将后者编码进段文件的 PostingsFormat（9.x/10.x 默认 Lucene90PostingsFormat 一族），用 块压缩 + 跳表（skip list） 降低空间，并在查询相交时用 impacts 提示「下一段 docID 对打分的上限」，服务两阶段迭代（第 9 篇）。

本文是系列第 5 篇，回答：

1. freqs、positions、offsets、payloads 各服务哪类查询？
2. 块编码与 skip list 在相交时如何减少比较次数？
3. 为什么 match_phrase 必须索引 positions，仅有 docID 不够？

版本锚定：Apache Lucene 9.x/10.x PostingsFormat、PostingsEnum、ImpactsEnum 官方文档；Zobel & Moffat (2006) 对倒排列表压缩与跳跃的综述。本篇无自测吞吐数据。

一、最小故事：两个词相交，再验证短语

查询：title:"inverted index"（已分析为 term inverted 与 index，且要求相邻短语）

1. 在 title 字段 FST 上分别 seek 两个 term。
2. 打开各自 PostingsEnum，在 docID 维度 做相交（Boolean AND）。
3. 对每个共有 doc，读取 positions，检查 index 的位置是否等于 inverted 的位置 \(+1\)（加 slop 时更宽）。
4. 命中 doc 经 BM25 打分（第 6 篇）后进入 Top-K。

若索引时 IndexOptions 只到 DOCS，步骤 3 无位置信息，短语查询无法在引擎内完成——只能退化为 AND 两个词或返回错误配置。

sequenceDiagram
  participant P1 as Postings inverted
  participant P2 as Postings index
  participant Ph as Phrase matcher
  P1->>P1: advance docID
  P2->>P2: advance docID
  P1->>Ph: doc match
  P2->>Ph: doc match
  Ph->>Ph: check positions

二、Postings 的四层信息

对单个 (field, term)，倒排列表在逻辑上是一条有序 docID 序列；每个 doc 上可附加：

IndexOptions（文档模型）决定索引时写哪些层；查询若请求缺失层，PostingsEnum 无法提供相应 API。

flowchart TB
  term["Term lucene"]
  docs["docIDs: 3,7,12,..."]
  freq["freqs per doc"]
  pos["positions per doc"]
  off["offsets optional"]
  term --> docs --> freq --> pos --> off

三、PostingsEnum 与解码

TermsEnum.postings(PostingsEnum reuse, int flags) 返回可复用解码器（A 级 API）。常用 flags：

• PostingsEnum.FREQS
• PostingsEnum.POSITIONS
• PostingsEnum.OFFSETS
• PostingsEnum.PAYLOADS

核心方法：

• nextDoc() / advance(target) — docID 迭代与跳跃
• freq() — 当前 doc 词频
• nextPosition() — 当前 doc 内下一个位置
• startOffset() / endOffset() — 与位置对齐的字符偏移

advance 是相交算法的基石：当另一列表当前 docID 更大时，调用 advance(target) 跳过中间 doc，而非 nextDoc() 线性爬。

四、块编码（block encoding）直觉

Zobel & Moffat 综述将倒排压缩分为 docID 间隙编码、freq 编码、位置增量编码 等。Lucene 现代 codec 将 docID 序列切成 固定大小块（具体块大小以 Lucene90PostingsFormat 为准），块内用 bit-packed 或 FOR-delta 类编码；块头记录 最大值 / 基数，解码时按批展开。

好处：

• SIMD / 批量解码 友好，减分支。
• 与 skip data 对齐：每 \(k\) 个 doc 存一次跳跃锚点。

工程上不必手写解码器；查询路径走 PostingsEnum 抽象。核对行为时对照 Lucene org.apache.lucene.codecs.lucene90 包源码。

flowchart LR
  raw["Sorted docIDs + freqs"]
  blk["Split into blocks"]
  enc["Bit-pack / delta encode"]
  disk[".doc / .pos files"]
  raw --> blk --> enc --> disk

五、Skip list：相交时的剪枝

当两个 term 的 doc 频率悬殊（如 the vs lucene），线性双指针相交会对高频列表做大量无效 nextDoc()。Skip list 在 postings 字节流中嵌入层级锚点：给定目标 docID \(t\)，解码器可 跳过整段 不可能 \(\ge t\) 的块。

经典分析与 Lucene 实现细节见 Baeza-Yates 等相交文献及 Lucene SkipReader 一类组件；与 PG GIN posting list 扫描相比，Lucene 在只读段上可更激进地预计算 skip，因为无需维护 B-Tree 页分裂。

六、Impacts：为打分剪枝提供上界

Lucene 较新版本在 postings 旁记录 impacts（ImpactsEnum）：对 upcoming docID 块给出 最大贡献分数上界（依赖 Similarity 与 norms）。Boolean 查询在 近似阶段 可用 impacts 跳过「不可能进入 Top-K」的 doc，再在 验证阶段 完整算分。

这与 WAND（Weak AND）/ MaxScore 一类动态剪枝算法同脉（Broder et al. 等）；Lucene 将其工程化到 codec 与 BooleanScorer（第 9 篇展开执行路径）。

flowchart TB
  subgraph phase1 ["Approximation phase"]
    imp["Read impacts upper bound"]
    skip["Skip doc blocks below threshold"]
  end
  subgraph phase2 ["Verification phase"]
    full["Full BM25 score"]
    topk["Top-K heap"]
  end
  phase1 --> phase2

假设：Top-K 查询且 \(K \ll |D|\)；若要求全量打分或聚合，impacts 路径可能不启用或收益有限。

七、短语查询为何必须要 positions

短语查询约束的是 token 位置关系，不是 docID 集合本身。仅知 doc 同时含 inverted 与 index 无法区分：

• 「… inverted file for index …」（不相邻）
• 「… inverted index structure …」（相邻）

因此 PhraseQuery / SpanQuery 在 doc 匹配后必须消费 positions（及 positionIncrement 在索引期已固化进链序）。Elasticsearch match_phrase 同理。

offsets 不能替代 positions：offsets 是字符级，受 Analyzer 与原文归一化影响；短语默认在 position 空间 运算。

八、与 PG GIN posting 的一句对照

PG GIN 在 Entry Tree 叶子指向 TID 列表（行物理地址），列表可升级为 Posting Tree（B-Tree of TIDs）。Lucene postings 是 docID 逻辑列表 + 列式压缩块，通过 FST 指针定位，无堆表 TID。二者都在做「键→行集合」，但 行标识与压缩布局不同（GIN 篇）。

九、可插拔 PostingsFormat 与版本

PostingsFormat 是 Lucene codec SPI：索引写入时 IndexWriter 选定格式名持久化在 segment info；读取时若 JVM 无对应 codec 则无法打开段。Elasticsearch 升级主版本时常伴随 Lucene major 与 codec 变化，需要 reindex 或滚动升级 兼容策略——属服务层运维，但根因在 postings 字节布局不可变。

十、相交算法：从双指针到 galloping

两个有序 docID 列表 \(A\)、\(B\) 求交集时，朴素双指针在 \(|A| \ll |B|\) 时仍可能对 \(B\) 做 \(\Theta(|B|)\) 次步进。Galloping（亦称 exponential search / finger search 变体）在列表上按指数步长试探，再二分回退，使总代价接近 \(O(|A| \log \frac{|B|}{|A|})\) 量级（Zobel & Moffat 对跳跃结构的讨论；Lucene ConjunctionDISI 等实现与之同脉）。

flowchart LR
  a["Rare term list A"]
  b["Frequent term list B"]
  adv["advance(target) on B"]
  match["docID equal -> emit"]
  a --> match
  b --> adv --> match

Lucene 将跳跃能力暴露在 PostingsEnum.advance(int target)；skip 字节与 impacts 元数据减少 解码 成本，galloping 减少 比较 次数——二者互补。第 9 篇在 BooleanScorer 层展开两阶段 approx + verify 如何消费 ImpactsEnum。

开放争论（仍活跃）：静态 skip 预计算在 段合并后 是否最优；动态相交算法（WAND、Block-Max WAND）与磁盘 postings 布局的协同在近年论文与 Lucene 提交中持续演进——生产默认以当前 Lucene release 的 PostingsFormat 为准，不宜用单一论文数字覆盖所有 workload。

十一、复现：验证 positions 是否索引（步骤）

ES 8.x 示例（无伪造输出）：

# 创建显式关闭 positions 的字段 vs 默认 text 字段，分别索引同一短语
curl -s -X PUT "localhost:9200/phrase-demo" -H 'Content-Type: application/json' -d '{
  "mappings": {
    "properties": {
      "title_positions": {
        "type": "text",
        "index_options": "positions"
      },
      "title_docs_only": {
        "type": "text",
        "index_options": "docs"
      }
    }
  }
}'
# 对两字段分别 match_phrase 同一查询，观察 docs_only 是否无法完成短语匹配

纯 Lucene：对 IndexOptions.DOCS 与 DOCS_AND_FREQS_AND_POSITIONS 各建一小索引，执行 PhraseQuery，用 Explanation 对比命中差异（第 6 篇 BM25 解释接口）。

十二、常见误解

1. 「倒排只存 docID」。BM25 与短语分别要 freqs 与 positions；省层即省能力。
2. 「skip list 是独立索引文件」。在 Lucene 实现里 skip 数据与 postings 字节交织，由 PostingsEnum 解释。
3. 「impacts 替代 BM25」。impacts 只帮助剪枝；最终得分仍由 Similarity 计算（第 6 篇）。

十三、小结

三句话小结

1. Postings 在 FST 定位后提供 docID 序列及可选 freqs/positions/offsets，由 PostingsEnum 解码。
2. 块编码 + skip 压缩空间并加速相交；impacts 为 Top-K 类查询提供打分上界剪枝。
3. 短语查询 在位置空间验证邻接，仅有 docID 交集不够，映射必须索引 positions。

参考资料

核心论文

1. Zobel, J. & Moffat, A., Inverted Files for Text Search Engines, ACM Computing Surveys 38(2), 2006（列表压缩与跳跃）。
2. Baeza-Yates, R. A. & Ribeiro-Neto, B., Modern Information Retrieval, 2nd ed.（相交算法背景）。

规范 / 文档

3. Apache Lucene 9.x/10.x, PostingsFormat、PostingsEnum、ImpactsEnum、IndexOptions。
4. Apache Lucene, Lucene90PostingsFormat 源码包 org.apache.lucene.codecs.lucene90。

站内

5. FST 词典、BM25 相似度、查询执行。

上一篇：词项词典 FST ｜ 下一篇：BM25 与 Similarity ｜ 系列目录