Easysearch 布尔查询子句重排序（三）｜WAND 动态剪枝

Easysearch 布尔查询 BoolQuery 排序

2026-08-28

查看 Markdown

Lucene 如何用 WAND 算法实现 Top-K 的动态剪枝

INFINI Easysearch 是一款专注于企业级场景的分布式近实时搜索与分析引擎。它以 Apache Lucene 为内核进行了增强，在保持与行业主流搜索协议及开发生态完全兼容的同时，重点强化了安全性、稳定性、压缩率及信创兼容性。

一、回顾与引入 #

在 第二篇中，我们深入解析了合取查询的核心优化：ConjunctionDISI 按 cost 排序，让最稀疏的迭代器领跑。这套机制的前提是 AND 语义——所有子句都必须匹配，所以"谁最少"就决定了跳转的速度。

本文聚焦析取（SHOULD）场景。关键转变在于：不需要全部匹配，而是找 Top-K 高分文档。 优化目标从"最少匹配"变为"最高分数贡献"——cost 最低的子句不一定分数最高，而分数最高的子句才最可能帮你快速找到 Top-K。

这就是 WAND 算法的用武之地。

二、为什么析取不能简单按 cost 排序？ #

合取和析取的本质差异决定了它们的优化策略必须不同：

为什么 cost 排序在析取中不适用？看一个析取查询 should: [quantum, the, machine_learning]，找 Top-10：

设想文档 D：不含 “quantum”，但同时命中 “the” 和 “machine_learning”，总分 = 0.1 + 15.0 = 15.1，远超只命中 “quantum” 的文档（8.0），理应排进 Top-10。

若按 cost 让 quantum 领头驱动，候选集就由 quantum 的倒排表决定——D 不在其中，根本不会被推进打分，Top-K 就漏掉了 15.1 分。根源在于：cost 衡量的是"匹配多少"，分数衡量的是"匹配多高"，两者是不同的维度。

析取需要的是感知分数的调度策略：优先推进高分子句，快速积累 Top-K，再用已有最低分剪枝。这就是 WAND（Weak AND）算法的核心思想。

WANDScorer 的触发条件 #

WANDScorer 不是总生效。Lucene 在 Boolean2ScorerSupplier.opt() 中按以下条件决定是否为 SHOULD 子句构造 WANDScorer（否则走 DisjunctionSumScorer）：

if ((scoreMode == ScoreMode.TOP_SCORES && topLevelScoringClause) || minShouldMatch > 1) {
    return new WANDScorer(weight, optionalScorers, minShouldMatch, scoreMode);
} else {
    return new DisjunctionSumScorer(weight, optionalScorers, scoreMode);
}

即满足其一即可：

1. ScoreMode.TOP_SCORES 且该析取是顶层评分子句：正常的 _search 请求默认 track_total_hits=10000，对应 TOP_SCORES（由 TopScoreDocCollector 设置）
2. minShouldMatch > 1：此时即便非 TOP_SCORES 也用 WANDScorer 做合取推进

注意第 1 个条件里的 TOP_SCORES 是 Lucene 的内部评分模式，由请求参数 track_total_hits 间接决定用哪个 Collector，Collector 再把自己的 ScoreMode 报给 Scorer：

• track_total_hits: false（默认 10000 亦同）→ TOP_SCORES：收集满 Top-K 后允许提前结束，并把当前最低分回传给 WANDScorer，剪枝开启
• track_total_hits: true → COMPLETE：必须遍历全部匹配文档以给出精确总数，从不回传阈值，剪枝关闭

所以同一条 SHOULD 查询（默认 minShouldMatch=1），只改 track_total_hits 就能让 WANDScorer 在"真正剪枝"与"改走 DisjunctionSumScorer 不剪枝"之间切换——这正是 下一篇 §三对比实验的切入点。

三、WAND 的核心逻辑：用上界剪枝 #

3.1 WAND 要解决什么：Top-K 与一条不断抬高的及格线 #

析取查询的本质：SHOULD 子句"至少匹配一个"，但用户要的不是全部匹配文档，而是分数最高的 K 个（Top-K）。

既然只要 Top-K，就有一条隐形的及格线——当前已收集结果中第 K 名的分数，记作 minCompetitiveScore（最小竞争分）。超过它才可能挤进 Top-K，超不过一定落选。随着高分文档不断被收进来，这条线只会越抬越高。

于是每个候选文档只须回答一个问题：分数能不能超过及格线？ 能才值得精确打分，不能就该跳过，不进行精确打分。WAND 的全部巧思都围绕上述这点，而办法就是下节介绍的"分数上界"。

3.2 从查询语句到游标：每个 SHOULD 子句是一条独立的倒排链 #

先看一条布尔查询长什么样：

{
  "bool": {
    "should": [
      { "term": { "body": "rare" } },
      { "term": { "body": "common" } },
      { "term": { "tag": "hot" } }
    ]
  }
}

里的每个 SHOULD 子句，底层都是一次独立的倒排索引查找，对应一条倒排链（posting list）——按 docID 升序排列的、所有命中该词的文档号序列。每条倒排链配一个游标 docID，指向"这条链上下一个待处理的匹配文档"。

3 个 SHOULD 子句 = 3 条倒排链 = 3 个游标。WANDScorer 就是同时管着这几个游标、协调它们推进的调度器。

下面给这三条倒排链画个框图（沿用 下一篇 §三对比实验里 body:rare / body:common / tag:hot 的语义：一个稀有词、一个常见词、一个中等标签），方便后续讲游标怎么移动。竖线是已经按 docID 升序排好的匹配文档号，▼ 就是游标当前指向的那个文档：

        SHOULD 子句         倒排链（命中的 docID，升序排列）        游标 ▼

   ┌──────────────┐
   │  rare (稀有) │  ··· 42 ──── 87 ──── 156 ──── 203 ──── 318 ──── ···
   └──────────────┘        ▲
                           │  当前指向 doc=42

   ┌──────────────┐
   │ common (常见)│  ··· 5 ── 42 ── 87 ── 88 ── 156 ── 203 ── 318 ── 410 ── ···  (很长，省略)
   └──────────────┘       ▲
                          │  当前指向 doc=5

   ┌──────────────┐
   │  hot (标签)  │  ··· 17 ──── 87 ──── 203 ──── 318 ──── ···
   └──────────────┘        ▲
                           │  当前指向 doc=17

   ───────────────────────────────────────────────────────────────────→ docID 轴
        5     17    42         87 88         156        203   318  410

看这张图，三条游标彼此独立、各自往前走。WANDScorer 的全部工作，就是在它们之间做调度：选一个"候选文档号"（比如最小的 5），把三条游标推进到那个号去查命中，命中就打分、不命中就跳过。三堆（§3.4）就是为这个调度做的分工。

关键认知：一个文档的最终得分 = 它实际命中的那些子句的实际得分之和。子句"命中没命中"，看那条倒排链里有没有这个文档号——这正是游标要查的事。

3.3 核心招式：用分数上界代替实际分数 #

最直白的判断法：把命中的子句逐个 score() 加起来跟及格线比。但 score() 很贵（要算 BM25 的 tf/idf），WAND 不想这么干。

WAND 的招式：别算实际分数，估一个上界就够了。 每个子句在构建时就算好 maxScore——“命中任何文档最多贡献多少分”（由 idf 和该词可能的最高 tf 决定，计算成本低）。于是：

文档分数上界 = 所有"可能命中"的子句的 maxScore 之和

这个上界必然 ≥ 实际分数：maxScore ≥ 实际得分（往大了估），“可能命中” ⊇ 真正命中（多算不漏算）。

判断就简单了：上界 < 及格线 → 直接跳过，一次 score() 都不调用。 只有上界 ≥ 及格线的文档才值得精确打分。WAND 的全部收益就来自这里——用大量廉价的上界比较换掉少量昂贵的精确打分（“Weak"也在这里：不强求每个子句都查实，上界够用就敢下结论）。

那么"可能命中"怎么界定？答案在游标位置里。

3.4 游标的三种位置 → 三堆 #

§3.3 留了一个问题：哪些子句算"可能命中”？答案全在游标上。

WANDScorer 手里攥着好几条倒排链的游标，各自独立推进。每一轮它选定一个候选文档号（从哪来的 §3.5 会说，眼下先当成参照点），然后看每条链的游标相对这个文档号，只可能有三种位置：

• 游标 == 候选号：确认命中 → 上界按 maxScore 计
• 游标 > 候选号：游标走过头了，确认不命中 → 贡献 0
• 游标 < 候选号：还没走到，未知 → 上界按 maxScore 计（往乐观了估）

WANDScorer 把这三类子句分别放进三个结构，叫三堆：确认命中的进 lead，确认不命中的进 head，未知的进 tail。

         ┌────────────────────────────────────────────────────────────────┐
         │                      WANDScorer 内部结构                        │
         │                                                                │
         │   tail (maxScore 最大堆) lead        head (按 docID 升序)        │
         │   ┌──────────────┐       ┌─────┐     ┌──────────────┐          │
         │   │ S4 maxScore=9│       │ S1  │     │ S3 doc=156   │          │
         │   │ S2 maxScore=5│       │ S5  │     │ S6 doc=203   │          │
         │   │ S7 maxScore=2│       │     │     │              │          │
         │   └──────────────┘       └─────┘     └──────────────┘          │
         │                                                                │
         │   游标还没到当前文档     游标已停在      游标已越过当前文档           │
         │   按 maxScore 排，       当前文档      按 docID 排，              │
         │   按需推进                            决定下个候选                │
         └────────────────────────────────────────────────────────────────┘

三个结构各有分工：

• tail 按 maxScore 排最大堆，堆顶是分数最高的子句。上界不够时优先借它——最可能一把把上限抬过线。
• lead 是简单链表，串起确认命中的子句。精筛过关后逐个 score() 算实际分。
• head 按 docID 排最小堆，堆顶是文档号最小的——它就是下一个候选文档。

子句在三堆间流转：tail → lead → head。未知的推进去查，命中进 lead，不命中进 head。下一轮候选变了，部分子句又可能从 head 回到 tail。

3.5 搜索流程：粗筛、精筛与阈值回传 #

把三堆放回完整流程。WANDScorer 对外是个 Scorer，被 Collector 驱动，主循环四步：

Collector 主循环：
  while ((doc = scorer.nextDoc()) != NO_MORE_DOCS) {   // ① 粗筛
    if (twoPhase.matches()) {                          // ② 精筛
      float s = scorer.score();                        // ③ 精确打分
      collector.collect(doc, s);                       // ④ 收入结果 + 抬及格线
    }
  }

• ① 粗筛：候选从 head 堆顶来（docID 最小者）。nextDoc() 调用 doNextCompetitiveCandidate（ WANDScorer.java:492-504）做一道文档级跳过：若 leadMaxScore + tailMaxScore < 及格线，说明当前 doc 凑不够分，直接推进到下一个候选文档（可能跨 block）。这里只用每子句一个的 maxScore 求和判断，不逐子句查实命中、不算精确分。
• ② 精筛：留在候选 doc 上，逐个借 tail 堆顶推进查实命中，看实际能否过线。这是 WAND 的核心动作，§3.6 专门展开。
• ③ 精确打分：通过精筛的，把 lead 里确认命中的子句逐个 score() 加总。
• ④ 阈值回传：收满 K 个后，Collector 把第 K 名分数回传给 WANDScorer 抬高及格线——下一篇 §一展开。

3.6 核心剪枝：上界估计与"借 tail" #

对当前候选文档，WAND 只回答一个问题：它的分数上界够不够得着及格线？

上界 = lead 各子句 maxScore 之和（确认命中，贡献确定）+ tail 各子句 maxScore 之和（未知，按 maxScore 乐观估算）。这个上界必然 ≥ 实际分数。判断逻辑（ WANDScorer.java:309-332）：

while (leadMaxScore < minCompetitiveScore) {        // lead 自己不够线
    if (leadMaxScore + tailMaxScore < minCompetitiveScore)
        return false;        // 加上 tail 的乐观估计仍不够 → 必败，跳过
    advanceTail();            // 还有希望：从 tail 堆顶借一个子句去"查实"
}
return true;                  // lead 已够线 → 留下精确打分

关键在 advanceTail()——把 tail 堆顶（maxScore 最高的未知子句）推进到当前文档查实，结果只有两种：

• 命中 → 进 lead，leadMaxScore 实打实涨上去；
• 不命中 → 进 head，从 tail 挪走，tailMaxScore 掉下来。

每借一次，要么抬高下限（leadMaxScore），要么压低上限（tailMaxScore）。文档能不能活下来，取决于借出的子句里有多少真的命中；借遍 tail 仍够不到线就判负，全程没调用过 score()。

为什么永远先借堆顶？ tail 按 maxScore 排最大堆，堆顶最可能一下把 leadMaxScore 抬过线；如果连 leadMaxScore + tailMaxScore 都够不到线，低分子句就无需查实，候选文档可以直接跳过。这就是 WAND 的 “Weak”：不强求每个子句都查实，只查可能扭转局面的那几个。

3.7 数字示例：一次完整的剪枝流程 #

先给出示例的场景。3 个 SHOULD 子句，各自的 maxScore 和倒排链（命中的 docID，已升序排列）如下，及格线 minCompetitiveScore = 10：

每个子句配一个游标，指向"这条链下一个待处理的 docID"。假设已经收集满 Top-K、及格线抬到了 10，本轮候选文档 = 42（S1 的游标停在 42，刚从 head 堆顶取出作为领头）；S2、S3 因 maxScore 较低此前没被推进，游标还分别停在 20、30。把三个子句按"游标 vs 候选 42"的位置归堆：

• S1 游标 42 == 42：确认命中 doc=42 → lead
• S2 游标 20 < 42：还没走到，未知 → tail
• S3 游标 30 < 42：还没走到，未知 → tail
• 没有游标 > 42 的子句 → head 此刻是空的（S1 已进 lead，S2、S3 还在 tail）

于是初始状态：lead 装着 S1（确认能拿 8 分），tail 装着 S2、S3（最多还能补 5+3=8 分），head 空。

下面这张状态图把 doc=42 接下来怎么被剪掉完整画了出来。关键看右侧三个数：leadMax = lead 里已确认能拿的分数，tailMax = tail 里最多还能补多少（乐观估计），二者之和就是分数上界。每借一次 tail 堆顶，三堆成员就流动一次，这三个数也跟着变：

        候选 doc=42,  及格线 = 10                          分数上界 = leadMax + tailMax

              head          lead         tail            leadMax  tailMax  上界     动作
        ┌────────────┐  ┌─────────┐  ┌──────────┐
  初始   │   (空)     │  │  S1: 8  │  │  S2: 5   │          8        8     16   ≥10
        │            │  │         │  │  S3: 3   │                              ─→ 借堆顶 S2
        ├────────────┤  ├─────────┤  ├──────────┤
  借 S2 │  S2→55     │  │  S1: 8  │  │  S3: 3   │           8        3     11   ≥10
        │            │  │         │  │          │                              ─→ 借堆顶 S3
        ├────────────┤  ├─────────┤  ├──────────┤
  借 S3 │  S2→55     │  │  S1: 8  │  │  (空)    │           8        0      8   <10
        │  S3→60     │  │         │  │          │                              ─→ ✂️ 必败
        └────────────┘  └─────────┘  └──────────┘

        表头解读：head/lead/tail 三栏列出各自的子句成员（含 maxScore）；
                  右侧三个数描述【整堆】在这一轮的整体状态，不与某一格对应。

每一行发生了什么（看左栏 → 右栏）：

• 初始：lead 只有 S1 → leadMax=8 不够线（8 < 10），但加 tail 的乐观估计 tailMax=8 后上界 16 ≥ 10，还有希望 → 借 tail 堆顶 S2 查实。
• 借 S2：把 S2 游标从 20 推进到 ≥42，结果落在 55（> 42，没命中）→ S2 进 head，tailMax 从 8 掉到 3。leadMax 还是 8（没涨，因为 S2 没命中），上界 11 ≥ 10 仍有希望 → 再借 S3。
• 借 S3：把 S3 游标从 30 推进到 ≥42，落在 60（也没命中）→ S3 进 head，tailMax 从 3 掉到 0。上界 8 < 10 → 必败，剪掉 ✂️

读懂这张图就懂了 WAND：借出的子句都没真命中 42，所以 leadMax 三轮卡在 8 不动；而每借走一个，tailMax 就往下掉一截（8→3→0）。上界随之从 16 一路缩到 8，最后跌穿及格线——doc=42 全程没调一次 score() 就被剪掉。

再看下一个候选 doc=55——lead 自身就够线，根本不用借。doc=42 被剪掉后，S1 推进到它的下一个文档 55；S2、S3 在前面借出时已推进到 55、60。按游标位置归堆：S1、S2 游标 == 55 → lead；S3 游标 60 > 55 → head（贡献 0）。状态图只有一行：

        候选 doc=55,  及格线 = 10

              head          lead         tail            leadMax  tailMax  上界     动作
        ┌────────────┐  ┌─────────┐  ┌──────────┐
  初始   │  S3→60     │  │  S1: 8  │  │  (空)    │         13        0     13   ≥10   ─→ score()
        │            │  │  S2: 5  │  │          │                              实际 7+4=11 ✅
        └────────────┘  └─────────┘  └──────────┘

leadMax=13 一上来就够线，直接调 score() 算实际分 7+4=11 > 10 → ✅ 收入 Top-K。两图对比，分水岭就在第一行：doc=42 的 lead 只值 8，被迫借 tail 撞运气；doc=55 的 lead 自值 13，一步过关。同一个及格线下，命运全由"借出来的子句有没有真命中"决定——这正是 §3.6 那句"借堆顶"的实战含义。

3.8 cost 作为平局打破者（tiebreaker） #

当两个子句 maxScore 相同时，推进 cost 更低（更稀疏）的子句更高效——它每次 advance 跳过的文档更多。

代码解读：tail 堆的比较器 greaterMaxScore()（ WANDScorer.java:643-651）以 scaledMaxScore 为主键排序，maxScore 相同时用 cost 做次键：

private static boolean greaterMaxScore(DisiWrapper w1, DisiWrapper w2) {
  if (w1.scaledMaxScore > w2.scaledMaxScore) return true;
  else if (w1.scaledMaxScore < w2.scaledMaxScore) return false;
  else return w1.cost < w2.cost;   // 分数并列时，cost 更低（更稀疏）的排前面
}

小结 #

本文把 WAND 讲透了：一条不断抬高的及格线 + 用 maxScore 估上界 + 三堆分工调度游标 + 完整数字例子。核心就一句——用大量廉价的上界比较，换掉少量昂贵的精确打分。

但标准 WAND 还有一个明显短板：每个子句的上界是全局的，游标走到低分区域仍按全局最高分估，剪枝不够激进。Block-Max WAND 怎么补上这块、混合查询怎么端到端跑起来、Profile API 怎么亲手验证剪枝生效——都在 下一篇（四）。