--- title: "Easysearch 布尔查询子句重排序（三）｜WAND 动态剪枝" date: 2026-08-28 lastmod: 2026-08-28 description: "本文是系列第三篇，聚焦析取（SHOULD）场景。关键转变在于：不需要全部匹配，而是找 Top-K 高分文档。 优化目标从“最少匹配” 变为 “最高分数贡献” —— cost 最低的子句不一定分数最高，而分数最高的子句才最可能帮你快速找到 Top-K。这就是 WAND 算法的用武之地。" tags: ["Easysearch", "布尔查询", "BoolQuery", "排序"] summary: "Lucene 如何用 WAND 算法实现 Top-K 的动态剪枝 INFINI Easysearch 是一款专注于企业级场景的分布式近实时搜索与分析引擎。它以 Apache Lucene 为内核进行了增强，在保持与行业主流搜索协议及开发生态完全兼容的同时，重点强化了安全性、稳定性、压缩率及信创兼容性。 一、回顾与引入 # 在 第二篇中，我们深入解析了合取查询的核心优化：ConjunctionDISI 按 cost 排序，让最稀疏的迭代器领跑。这套机制的前提是 AND 语义——所有子句都必须匹配，所以"谁最少"就决定了跳转的速度。 本文聚焦析取（SHOULD）场景。关键转变在于：不需要全部匹配，而是找 Top-K 高分文档。 优化目标从"最少匹配"变为"最高分数贡献"——cost 最低的子句不一定分数最高，而分数最高的子句才最可能帮你快速找到 Top-K。 这就是 WAND 算法的用武之地。 二、为什么析取不能简单按 cost 排序？ # 合取和析取的本质差异决定了它们的优化策略必须不同： 维度 合取（MUST） 析取（SHOULD） 语义 所有子句都匹配 至少部分子句匹配 优化目标 快速排除不匹配文档 快速找到 Top-K 高分文档 排序依据 cost（谁最少谁领头） maxScore（谁分最高谁优先推进） 关键操作 跳过不匹配的文档 跳过不可能进 Top-K 的文档 为什么 cost 排序在析取中不适用？看一个析取查询 should: [quantum, the, machine_learning]，找 Top-10：" --- > Lucene 如何用 WAND 算法实现 Top-K 的动态剪枝 _INFINI Easysearch 是一款专注于企业级场景的分布式近实时搜索与分析引擎。它以 Apache Lucene 为内核进行了增强，在保持与行业主流搜索协议及开发生态完全兼容的同时，重点强化了安全性、稳定性、压缩率及信创兼容性。_ --- ## 一、回顾与引入 在[第二篇](/blog/2026/easysearch-boolean-query-clause-reordering-part-2/)中，我们深入解析了合取查询的核心优化：ConjunctionDISI 按 cost 排序，让最稀疏的迭代器领跑。这套机制的前提是 AND 语义——所有子句都必须匹配，所以"谁最少"就决定了跳转的速度。 本文聚焦析取（SHOULD）场景。关键转变在于：**不需要全部匹配，而是找 Top-K 高分文档。** 优化目标从"最少匹配"变为"最高分数贡献"——cost 最低的子句不一定分数最高，而分数最高的子句才最可能帮你快速找到 Top-K。 这就是 WAND 算法的用武之地。 --- ## 二、为什么析取不能简单按 cost 排序？ 合取和析取的本质差异决定了它们的优化策略必须不同： | 维度 | 合取（MUST） | 析取（SHOULD） | | -------- | -------------------- | ------------------------------ | | 语义 | 所有子句都匹配 | 至少部分子句匹配 | | 优化目标 | 快速排除不匹配文档 | 快速找到 Top-K 高分文档 | | 排序依据 | cost（谁最少谁领头） | maxScore（谁分最高谁优先推进） | | 关键操作 | 跳过不匹配的文档 | 跳过不可能进 Top-K 的文档 | 为什么 cost 排序在析取中不适用？看一个析取查询 `should: [quantum, the, machine_learning]`，找 Top-10： | 子句 | 匹配文档数（cost） | 单次命中得分 | | ------------------ | ------------------ | ------------ | | `quantum` | 100 | 8.0 | | `the` | 1000 万 | 0.1 | | `machine_learning` | 5 万 | 15.0 | 设想文档 **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`）： ```java 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` 不剪枝"之间切换——这正是[下一篇 §三](/blog/2026/easysearch-boolean-query-clause-reordering-part-4/#三动手验证profile-api-观察-wand-生效)对比实验的切入点。 --- ## 三、WAND 的核心逻辑：用上界剪枝 ### 3.1 WAND 要解决什么：Top-K 与一条不断抬高的及格线 析取查询的本质：SHOULD 子句"至少匹配一个"，但用户要的不是全部匹配文档，而是**分数最高的 K 个**（Top-K）。 既然只要 Top-K，就有一条隐形的及格线——当前已收集结果中**第 K 名的分数**，记作 `minCompetitiveScore`（最小竞争分）。超过它才可能挤进 Top-K，超不过一定落选。随着高分文档不断被收进来，这条线只会越抬越高。 于是每个候选文档只须回答一个问题：**分数能不能超过及格线？** 能才值得精确打分，不能就该跳过，不进行精确打分。WAND 的全部巧思都围绕上述这点，而办法就是下节介绍的"分数上界"。 ### 3.2 从查询语句到游标：每个 SHOULD 子句是一条独立的倒排链 先看一条布尔查询长什么样： ```json { "bool": { "should": [ { "term": { "body": "rare" } }, { "term": { "body": "common" } }, { "term": { "tag": "hot" } } ] } } ``` 里的**每个 SHOULD 子句**，底层都是一次独立的倒排索引查找，对应一条**倒排链**（posting list）——按 docID 升序排列的、所有命中该词的文档号序列。每条倒排链配一个**游标** `docID`，指向"这条链上下一个待处理的匹配文档"。 3 个 SHOULD 子句 = 3 条倒排链 = 3 个游标。WANDScorer 就是同时管着这几个游标、协调它们推进的调度器。 下面给这三条倒排链画个框图（沿用[下一篇 §三](/blog/2026/easysearch-boolean-query-clause-reordering-part-4/#三动手验证profile-api-观察-wand-生效)对比实验里 `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](https://github.com/apache/lucene/blob/releases/lucene/9.12.2/lucene/core/src/java/org/apache/lucene/search/WANDScorer.java#L492-L504)）做一道文档级跳过：若 `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](https://github.com/apache/lucene/blob/releases/lucene/9.12.2/lucene/core/src/java/org/apache/lucene/search/WANDScorer.java#L309-L332)）： ```java 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`： | 子句 | maxScore | 倒排链（命中的 docID） | | ---- | -------- | ---------------------- | | S1 | 8 | 42, 55 | | S2 | 5 | 20, 55 | | S3 | 3 | 30, 60 | 每个子句配一个游标，指向"这条链下一个待处理的 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](https://github.com/apache/lucene/blob/releases/lucene/9.12.2/lucene/core/src/java/org/apache/lucene/search/WANDScorer.java#L643-L651)）以 `scaledMaxScore` 为主键排序，maxScore 相同时用 `cost` 做次键： ```java 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 怎么亲手验证剪枝生效——都在[下一篇（四）](/blog/2026/easysearch-boolean-query-clause-reordering-part-4/)。