【全文检索引擎】查询执行：BooleanScorer、两阶段与 Collector

BM25 给出词项分数；postings 给出 docID 迭代器。生产查询却是 多词 Boolean 组合 + 短语约束 + Top-K 截断——执行引擎要在「全量打分」之前尽可能 少碰文档，并把 survivors 交给 Collector 聚合成 TopDocs。

本文是系列第 9 篇：BooleanScorer 如何组织 DISJUNCTION/CONJUNCTION、两阶段迭代如何拆 近似 与 验证、以及 galloping 与 impacts 如何服务同一目标：在倒排相交上少做无用工作。

版本锚定：Apache Lucene 9.x / 10.x org.apache.lucene.search 包；相交算法谱系参见 Baeza-Yates & Ribeiro-Neto、Broder 等（见 §六）。本篇无 QPS benchmark。

一、查询执行全景

一次 IndexSearcher.search(query, n) 可粗分为：

flowchart TB
  q["Query tree"]
  rewrite["rewrite per segment"]
  weight["Weight / Scorer tree"]
  iter["docID iteration"]
  coll["Collector"]
  top["TopDocs"]
  q --> rewrite --> weight --> iter --> coll --> top

1. Rewrite：将 PrefixQuery、WildcardQuery 等展开为词项级子查询（可能昂贵）；
2. Weight：绑定 IndexReader 统计，构造段级 Scorer；
3. 迭代：按 docID 顺序推进，对匹配 doc 调用 Scorer#score()；
4. Collector：接受 (doc, score)；TopScoreDocCollector 维护大小为 n 的堆。

第 6 篇 的公式发生在 score()；本篇关心 哪些 docID 会走进 score()。

二、BooleanQuery 与 BooleanScorer

BooleanQuery 把子句标为 MUST、SHOULD、MUST_NOT、FILTER（filter 不打分但约束集合）。段内实现会按子句关系选 Conjunction（与）或 Disjunction（或）迭代器，并由 BooleanScorer（及更细分的 BlockMaxDISI 等优化路径）组合。

2.1 合取（MUST / FILTER）

多词 AND 要找 所有 posting 列表的交集。朴素双指针在 docID 有序列表上前进；当列表长度悬殊时，galloping（跳跃） 让短列表的 docID 在长列表上指数式前进定位（Baeza-Yates & Ribeiro-Neto, Modern Information Retrieval；Lucene ConjunctionDISI 实现族）。

flowchart LR
  p1["postings term A"]
  p2["postings term B"]
  p3["postings term C"]
  conj["ConjunctionDISI"]
  p1 --> conj
  p2 --> conj
  p3 --> conj
  conj --> bm25["BM25 sum score"]

FILTER 语义：参与集合约束但 不贡献分数（缓存友好，常_BITSET_ 预计算）。

2.2 析取（SHOULD）

OR 子句用 DisjunctionDISI：按最小当前 docID 推进，合并分数（受 minimumNumberShouldMatch 约束）。BooleanScorer 在「需要协调因子 / 多 SHOULD 打分」时避免重复计算同 doc 的子分数。

2.3 与 ES 查询 DSL 的对应（一层）

协调因子（coord）在经典 Similarity 中更明显；BM25 默认路径下多词分数主要为 词项分之和（仍以具体查询 rewrite 为准）。

三、两阶段迭代：approximation + confirmation

部分查询 精确匹配 比 倒排相交 更贵：

• 短语查询（PhraseQuery）：相交后还要核对 positions 是否相邻；
• 跨度查询（SpanQuery）：更复杂的位置约束；
• 部分 join / 父文档查询。

Lucene TwoPhaseIterator 把迭代拆成：

1. Approximation：廉价的上界集合（通常仅 docID 相交）；
2. Confirmation：matches() 做精确校验。

sequenceDiagram
  participant App as Collector
  participant Two as TwoPhaseIterator
  participant Appr as Approximation
  participant Ver as matches()
  App->>Two: nextDoc
  Two->>Appr: advance docID
  Appr-->>Two: candidate doc
  Two->>Ver: matches?
  alt false positive
    Ver-->>Two: skip score
  else match
    Ver-->>Two: ok
    Two-->>App: score()
  end

工程含义：Collector 仍只看见通过验证的 doc，但 CPU 花在 拒绝假阳性 上；短语越常见，positions 解码成本越高——mapping 里滥用 text + match_phrase 是慢查询温床（第 17 篇）。

四、Collector 与 TopDocs

4.1 Collector 接口

Collector 在搜索过程中接收 当前 doc 与 score（或仅 doc，对 TotalHitCountCollector）。核心实现：

TopDocs 返回 ScoreDoc[]（全局 docID + score）及 totalHits（可能为下界，若提前终止）。

4.2 Top-K 堆与「不必全排序」

Top-N 用 固定大小最小堆 维护当前最佳 N 个，内存 \(O(N)\)，无需对所有命中全排序。分片级 Top-N 在 Elasticsearch query 阶段 产出，协调节点 reduce 合并（第 13 篇）——每分片截断 可能漏全局 Top1，这是分布式搜索的结构性权衡，可用 dfs_query_then_fetch 缓解 IDF 不一致，不能单独解决「分片内截断」问题。

4.3 常见误解

1. 「Lucene 会对全索引排序」。默认相关性搜索只对 命中集 维护 Top 堆；全量排序需 match_all + sort，走 DocValues。
2. 「filter 不影响性能」。filter 不打分，但仍 约束迭代；复杂 filter 链会拖慢位图构建与缓存失效。
3. 「explain 分数慢说明 BM25 慢」。explain 是调试路径；生产慢常在 rewrite、相交、positions 验证，而非单次 ln IDF。

五、galloping 与 impacts：同一问题的两层剪枝

5.1 Galloping 相交

当 AND 的多条 posting 列表 长度差几个数量级 时，双指针线性 advance 会在长列表上「一格一格挪」。Galloping 在 advance 目标 docID 时 指数步进再二分，使长列表定位均摊更优。Lucene 在 ConjunctionDISI 等对子迭代器长度排序，最短列表优先 驱动跳跃——与 第 5 篇 skip list 互补：skip 在 单列表内 跳 docID；galloping 在 多列表间 对齐。

5.2 Impacts：按最大可能分数剪枝

Impacts（Lucene 索引结构，与 BlockMaxWAND / MaxScore 优化相关）在 posting 块上记录 该块内词项能贡献的最大分数上界。当查询带 分数阈值（来自当前 Top-N 堆底或 minCompetitiveScore）时，块若 不可能 进入 Top，可 整块跳过——在 disjunctive 或 MUST 组合里与 WAND 族算法协同。

关系可概括为：

Robertson & Zaragoza (2009) 讨论 BM25 的项级上界；Lucene 将 索引期预计算的上界 与 查询期动态阈值 结合，是工程化 WAND（Weak AND, Broder et al.）思路在通用搜索引擎中的落地。假设：打分单调可上界；使用 function_score、非标准 Similarity 时，优化路径可能退化。

flowchart TB
  subgraph intersect ["Intersection pruning"]
    gallop["Galloping alignment"]
    skip["Posting skip lists"]
  end
  subgraph score ["Score pruning"]
    impact["Impacts max per block"]
    heap["Top-N heap threshold"]
    impact --> heap
  end
  intersect --> score

5.3 BlockMaxWAND 与 MaxScore 查询路径

当 BooleanQuery 含多个 SHOULD 子句且 无 MUST 时，Lucene 可能走 Block-Max WAND 变体：用 impacts 估计各子句对当前 doc 的最大贡献，若累加上界仍低于堆底分数，则 跳过整段 doc 块。IndexSearcher#setTimeout 与 partial results 是另一维度的「早停」，与 WAND 正交。

前提：Similarity 必须支持 per-block 最大 impact 索引；自定义 Similarity 若未配合 impacts 编码，优化路径自动关闭，查询仍正确但 变慢——排障时除了解释 plan，还应看索引是否用默认 codec 与 BM25。

六、谱系与开放问题

争论：更激进的近似 Top-K（允许漏检）在 Web 规模有论文支持；Lucene 默认路径以精确 Top-K 为目标（在相似度可上界前提下剪枝），与「召回优先的 RAG 粗召回」场景可能不一致——RAG 常把 size 拉大换召回，代价是 post-filter 与 rerank 压力（llm-infra）。

6.1 分布式查询与执行层的接缝

单分片 Lucene 上，TopScoreDocCollector 维护全局 docID 堆；多分片时 每分片独立堆，协调节点做 归并 k 路（第 13 篇）。因此：

• 分片内 impacts / galloping 优化 照常生效；
• 全局 Top1 仍可能因 分片内截断 丢失——这是架构层问题，不能靠调 k1 解决。

开放问题：

1. 混合向量 + BM25 查询树如何共享剪枝阈值（第 15 篇）；
2. 多段 上 minCompetitiveScore 传递是否与段级 Top 堆一致；
3. Serverless / 冷段 上 impacts 缺失或旧 codec 导致优化路径关闭时的性能悬崖。

七、小结

三句话小结

1. 执行路径是 Query → Scorer 迭代 → Collector；BooleanScorer 把 MUST/SHOULD 变成合取/析取 posting 迭代。
2. 两阶段迭代 把短语/跨度等 昂贵校验 隔在 matches()，避免对仅 docID 相交的 doc 白算分。
3. Galloping 对齐多列表 docID；impacts 在块级用分数上界配合 Top-N 阈值剪枝——都与 第 5 篇 postings 编码一体设计。

下一篇看排序/聚合为何不走 postings：DocValues 与 stored fields。

参考资料

书籍 / 论文

1. Baeza-Yates, R. & Ribeiro-Neto, B., Modern Information Retrieval, 2nd ed.（倒排相交、galloping）。
2. Broder, A. et al., WAND: Search in Time, SIGIR 2003（块级上界剪枝思路）。
3. Robertson, S. & Zaragoza, H., BM25 and Beyond, FnTIR 2009（项级分数与上界讨论）。

规范 / 源码

4. Apache Lucene 9.x/10.x：BooleanScorer、ConjunctionDISI、TwoPhaseIterator、TopScoreDocCollector、ImpactsEnum / MaxScoreCache 相关类与 package-info。

站内

5. BM25、Postings、ES 查询路径、系列目录。

返回 系列目录 ｜ 上一篇：MergePolicy 与删除 ｜ 下一篇：DocValues 与 stored