Easysearch 布尔查询子句重排序（二）｜ConjunctionDISI 按 cost 排序源码解析

Lucene 如何让最稀疏的迭代器领跑，最大化跳过无效文档

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

一、回顾与引入

在第一篇中，我们走完了布尔查询从用户 JSON 到 Lucene 执行的构建层旅程：Easysearch 的BoolQueryBuilder会保留同类子句的书写顺序，Lucene 的BooleanQuery.rewrite()则通过等价改写简化查询结构。

其中，和本文关系最直接的是SHOULD + FILTER → MUST：一个原本只是“可选加分”的 SHOULD 子句，如果同时出现在 FILTER 中，就会被改写成 MUST。它的执行路径也随之改变——从可选评分路径，进入更直接的合取路径。

所谓合取路径，就是按 AND 语义执行查询：所有必选条件都要同时满足，任意一个不满足就可以跳过该文档。对于 MUST / FILTER 这类合取子句，真正影响性能的不是用户在 JSON 里先写谁、后写谁，而是 Lucene 在执行层如何安排它们的检查顺序。

这就是本文要讲的“布尔查询子句重排序”：进入 Scorer 构造阶段后，每个 MUST / FILTER 子句会变成对应的文档迭代器，Lucene 再按cost()对这些迭代器重新排序，让匹配文档最少的迭代器先领跑。

一个直觉可以帮助我们理解：在 AND 查询中，谁的结果最少，谁最有"话语权"。因为 AND 语义要求所有条件都满足，所以结果最少的那个条件能最快地排除不满足的文档，剩下的条件只需要确认即可。

本文就专注于这条合取路径的核心机制：ConjunctionDISI 如何按 cost 排序，让最稀疏的迭代器领跑整场迭代。

二、前置：什么情况下走 ConjunctionScorer？

上面已经说明，rewrite 可能会把子句带入合取路径；但并不是所有 bool 查询都会走这条路径。本节先界定范围：哪些查询会进入合取路径，哪些不会。Lucene 在Boolean2ScorerSupplier.getInternal()中会根据子句组合做这个判断。

对本文来说，记住一个判断就够了：只要查询里出现多个“必须同时满足”的条件，Lucene 就需要做交集计算，ConjunctionDISI 的 cost 排序就有发挥空间。

那么 ConjunctionDISI 内部到底做了什么？让我们深入源码。

三、核心揭秘：ConjunctionDISI 按 cost 排序

这是合取查询最核心的优化。

3.1 生活类比

可以把合取查询理解成多条件筛选：先用结果最少的条件缩小候选集，再让其他条件确认，通常最省事。

比如在快递系统里找“已签收、发往北京、备注里有易碎品”的包裹。“已签收”和“发往北京”的包裹可能很多，但“备注里有易碎品”的包裹很少。先从“易碎品”开始查，再确认它是否发往北京、是否已签收，比先遍历所有已签收包裹更快。

3.2 源码解析

先解释一下“迭代器”，比如下文的DocIdSetIterator。迭代器可以理解为某个查询条件对应的匹配文档列表游标。它负责在自己的列表里向前移动，告诉 Lucene：下一个匹配这个条件的 docID 是谁。

比如author:sam的迭代器里可能是[42, 78, 203]，category:ai的迭代器里可能是[12, 42, 100, 203]。执行 AND 查询时，Lucene 要做的就是不断推进这些游标，找到它们共同出现的 docID，比如这里的42和203。

所以，本文说的“重排序”不是改写用户 JSON 里的子句顺序，而是在执行阶段对这些子句对应的迭代器排序：谁的cost()更小，谁就更靠前执行。

核心逻辑在 Lucene 的ConjunctionDISI.java（ConjunctionDISI.java:154-163）：

privateConjunctionDISI(List<?extendsDocIdSetIterator>iterators){assertiterators.size()>=2;// Sort the array the first time to allow the least frequent DocsEnum to// lead the matching.CollectionUtil.timSort(iterators,(o1,o2)->Long.compare(o1.cost(),o2.cost()));lead1=iterators.get(0);// 代价最小 → 领头lead2=iterators.get(1);others=iterators.subList(2,iterators.size()).toArray(newDocIdSetIterator[0]);}

三行代码，逻辑清晰：

1. 按cost()升序排序：cost()返回迭代器预估的匹配文档数，越少越"便宜"（注：cost 是预估值，实际匹配数可能有偏差，但排序逻辑依然成立）
2. lead1：代价最小的迭代器，负责领头跳转——它最稀疏，每次跳转跳过的文档最多
3. lead2：代价第二小的迭代器，负责二次确认
4. others：其余迭代器，仅在 lead1 和 lead2 都停下时才被调用

3.3 执行过程

核心迭代方法doNext()（ConjunctionDISI.java:165-199）：

privateintdoNext(intdoc)throwsIOException{advanceHead:for(;;){// doc 是当前 lead1 停住的位置；lead1 是最稀疏的迭代器，负责给出候选 docIDassertdoc==lead1.docID();// 先让 lead2 追上 lead1：advance(doc) 会跳到 >= doc 的第一个文档finalintnext2=lead2.advance(doc);if(next2!=doc){// lead2 跳过了当前 doc，说明当前候选不匹配；lead1 跳到 lead2 的位置作为新起点doc=lead1.advance(next2);if(next2!=doc){// 仍没对齐，说明 lead1 又跳到了更后面，重新开始对齐continue;}}// lead1 和 lead2 对齐后，再检查其他迭代器for(DocIdSetIteratorother:others){// other 可能在上一轮已经被推进过；只有落后时才需要追赶if(other.docID()<doc){finalintnext=other.advance(doc);if(next>doc){// other 跳过了当前 doc，当前候选失败；lead1 追到新的最大 docIDdoc=lead1.advance(next);continueadvanceHead;}}}// 所有迭代器都停在同一个 doc 上 → 这个文档满足所有条件returndoc;}}

这段代码的核心就是“不断对齐”：谁跳到了更大的 docID，其他迭代器就追上去；直到所有迭代器停在同一个 docID，才算匹配成功。

例如lead1停在 78，而lead2.advance(78)返回 100，就说明 78 不可能匹配。Lucene 会直接把lead1推进到 100 附近，而不是继续检查 79、80、81……这些中间文档。

3.4 直观示例

为突出 cost 的量级差异，下面用夸张的数量级示意（§六会给出真实测试索引的实测数据，数量级更小，但结论一致）：

查询：must:[status:published(100万), category:ai(1万), author:sam(500)]迭代器按 cost 排序后： lead1: author:samcost=500← 最稀疏，领头跳转 lead2: category:aicost=10,000other: status:publishedcost=1,000,000 执行过程： lead1 →doc=42→ lead2确认✓ → other确认✓ → 匹配！ lead1 →doc=78→ lead2确认✗ → 跳过（不用查 other） lead1 →doc=203→ lead2确认✓ → other确认✓ → 匹配！ 如果没有 cost 排序，让高频词先给出候选，后续条件就要确认大量无效文档。

cost排序的效果：Lucene 实际执行时，lead1一定是 cost 最小的迭代器（即最低频）。低频迭代器先领头，可以显著减少候选文档数量。

3.5 子合取展平

还有一个值得注意的细节：当嵌套的 ConjunctionDISI 作为子句出现时，会被"拆包"展平（ConjunctionDISI.java:54-77）：

}elseif(disi.getClass()==ConjunctionDISI.class){// 发现子句本身也是一个 ConjunctionDISI，也就是嵌套的 AND 查询ConjunctionDISIconjunction=(ConjunctionDISI)disi;// 不把整个子 ConjunctionDISI 当成一个黑盒，// 而是把它内部已经拆好的 lead1、lead2、others 全部取出来allIterators.add(conjunction.lead1);allIterators.add(conjunction.lead2);Collections.addAll(allIterators,conjunction.others);}

这些迭代器取出来后，会和外层迭代器一起进入统一排序流程。也就是说，Lucene 不会把内层 AND 当成一个整体参与外层排序，而是先展平，再让所有迭代器按 cost 统一排序。

这确保了基于 cost 估算的全局最优迭代顺序——如果内层有一个极稀疏的迭代器，它也有机会“越级”成为全局 lead1，而不是被锁在内层。

注意这里使用了精确类检查disi.getClass() == ConjunctionDISI.class，而不是instanceof。这是为了确保只拆包原始的 ConjunctionDISI，不误拆子类（如 BitSetConjunctionDISI，它有自己的优化路径）。

四、延伸：候选文档确定后，验证也要按成本排序

前面讲的是cost()排序：在多个迭代器之间，先让匹配文档最少的迭代器领头，尽量少产生候选文档。它背后的思想是：把执行成本低、过滤能力强的步骤放在前面，尽早排除不匹配的文档。

matchCost()排序是这个思想在“验证阶段”的延伸：cost()决定“谁先领头找候选”，matchCost()决定“先做哪个精确验证”。

为什么候选文档还要验证？因为有些迭代器是"近似的"——先用低成本方式定位可能匹配的文档，再用精确方式二次确认。典型场景是短语查询：先对短语中的每个词做倒排合取，得到“包含全部词”的候选文档，再检查这些词是否出现在符合要求的相对位置上。前者用 posting list 快速缩小范围，后者才是真正的精确匹配。

Lucene 用TwoPhaseIterator表示这种两阶段验证，而ConjunctionTwoPhaseIterator会按matchCost()从低到高排序，让便宜的验证先执行；一旦失败，就不用再执行后面更贵的验证（ConjunctionDISI.java:317-357）：

CollectionUtil.timSort(twoPhaseIterators,(o1,o2)->Float.compare(o1.matchCost(),o2.matchCost()));

类比：先查身份证（快，matchCost 低），再查指纹（慢，matchCost 高），而不是反过来。如果身份证就不对，指纹根本不用查。

与cost()不同，matchCost()没有统一公式：它是每个TwoPhaseIterator子类按自身验证逻辑估算的“简单操作数”（如 DocValues 查 bitset 约记为 3 次操作）。这个值比较粗略，实际排序时用到的只是相对大小——让便宜的验证先跑。

在实际代码中，ConjunctionDISI.createConjunction()会把执行过程拆成两个阶段来看：

• 找候选 docID：用allIterators完成。普通迭代器会直接放进来；如果某个查询是两阶段查询，就把它的“近似迭代器”放进来，先参与cost()排序和合取对齐。
• 验证候选是否真的匹配：用twoPhaseIterators完成。这里保存的不是另一批文档列表，而是候选 docID 命中后要执行的matches()验证逻辑，并按matchCost()排序。

所以可以理解为：allIterators负责“先找可能匹配的文档”，twoPhaseIterators负责“再确认这些文档是否真的匹配”。前者按cost()排序，目标是少产生候选；后者按matchCost()排序，目标是少做昂贵验证。

五、进阶补充：cost 排序还会影响子查询策略

前面讲的是 cost 排序对“当前这一层”的影响：选出最稀疏的迭代器作为 lead1，减少候选文档。但 cost 排序选出的 lead1 还会带来一个连锁效应：它把代价信息继续传给子查询，让子查询也能根据外层的调用频率选择更合适的执行方式。

这个连锁效应的起点是：在合取查询里，外层最终会由最稀疏的迭代器领头，所以其他子查询被推进的次数通常不会超过这个领头迭代器的规模。这个规模就是向外传播给子查询的代价上限。Lucene 在Boolean2ScorerSupplier.getInternal()中用Math.min(leadCost, cost())给这个估计加了一个上限（Boolean2ScorerSupplier.java:126）：如果上层传来的leadCost过大，就用当前查询自己的cost()压住，避免子查询误判使用模式。对于纯合取查询来说，这个值通常接近lead1.cost()。

这个向外传播的代价上限，就是leadCost。它可以理解为上层给子查询的一个提示：“接下来你大概要被推进这么多次”。它不是 ConjunctionDISI 内部的概念，而是ScorerSupplier.get(long leadCost)的参数。

这里的“推进”指的是：上层会不断要求子查询的迭代器向后移动，要么调用nextDoc()走到下一个匹配文档，要么调用advance(target)直接跳到>= target的文档。

为什么这个提示有用？因为不同实现适合不同使用方式：如果会被频繁推进，就适合用支持高效跳转的结构；如果只会被少量推进，就可以选择初始化成本更低的结构。一个典型例子是IndexOrDocValuesQuery。它内部同时持有索引结构（点数据 / term 查询）和 DocValues 两种策略，会根据leadCost动态选择（IndexOrDocValuesQuery.java:176-186）：

publicScorerget(longleadCost)throwsIOException{finallongthreshold=cost()>>>3;// cost / 8if(threshold<=leadCost){returnindexScorerSupplier.get(leadCost);// 推进频繁：用索引结构}else{returndvScorerSupplier.get(leadCost);// 推进较少：用 DocValues}}

简单说：外层通过 cost 排序估算推进频率，再把这个信息传给子查询；子查询只需要判断“我会被频繁推进，还是只会偶尔确认”，就能做出局部最优选择。

六、一个 MUST 查询是如何被重新排序的

用一个简单的 MUST 查询，把第一篇的 rewrite 和本文的 cost 排序串起来。下面这个例子中，status:published写在前面，category:ai写在后面：

GET/bool_cost_profile_test/_search{"profile":true,"query":{"bool":{"must":[{"term":{"status":"published"}},{"term":{"category":"ai"}}]}}}

完整过程可以拆成四步：

① Easysearch 层：按用户写法构建 BooleanQuery profile description 仍显示：+status:published +category:ai ② Lucene rewrite：2 个 MUST，无重复、无矛盾 查询形态保持为两个 MUST 子句 ③ Scorer 构造： Boolean2ScorerSupplier.req() → new ConjunctionScorer(...) ConjunctionScorer 内部创建 ConjunctionDISI ConjunctionDISI 再按 cost 对迭代器排序 ④ 执行： 低 cost 的 category:ai 负责产生候选 docID status:published 通过 advance(candidate) 追赶确认

在本地 Easysearch 2.2.0 / Lucene 9.12.2 的测试索引中，status:published约 900 条，category:ai约 100 条。实际 profile 结果是：

子句 next_doc_count advance_count 说明 ────────────────────────────────────────────────────────────── category:ai 91 1 低 cost，产生候选 status:published 0 91 跟随候选，用 advance 确认

把 JSON 里的两个 MUST 顺序反过来再查，profile 仍然显示category:ai通过nextDoc()产生候选，status:published通过advance()确认。也就是说，description会保留查询展示顺序，但真正执行时的迭代器顺序由 cost 排序决定。

这就是本文的关键点：用户在 JSON 中先写谁，不等于执行时谁先跑。对于合取查询，Lucene 会在 Scorer 构造阶段按 cost 重新安排迭代器顺序，让更稀疏的条件领头。唯一的例外是多词查询混入 must/filter 且版本较老的场景，见 §八末尾的边界说明。

双条件场景验证了"重排序确实发生"，接下来看三条件场景如何用 Profile 观察。

七、如何用 Profile API 观察 cost 排序效果

现在扩展到三条件，重点看一个更极端的对比：author:sam只有 5 条，status:published有 900 条。Profile 不会直接告诉你lead1是谁，但可以通过next_doc_count和advance_count的分布间接推断。

在同一个测试索引上，查三个 MUST：

"must":[{"term":{"status":"published"}},{"term":{"category":"ai"}},{"term":{"author":"sam"}}]

BooleanQuery 的子节点大致如下：

子句 next_doc_count advance_count 说明 ────────────────────────────────────────────────────────────── author:sam51最稀疏，负责产生候选 docID category:ai06跟随候选，用 advance 对齐 status:published05跟随候选，用 advance 对齐

注意跟随迭代器的advance_count未必完全相等，这和实际匹配过程中发生的追赶次数有关，不影响"谁是领头"的判断。

如何看这份 Profile

Profile 不会直接打印lead1，但指标和源码是对应的：ConjunctionDISI.nextDoc()会调用lead1.nextDoc()产生下一个候选；进入doNext()后，再通过lead2.advance(doc)和other.advance(doc)让其他迭代器追赶。next_doc_count和advance_count统计的正是这些底层调用。

可以总结成一条简单观察规律：

• 领头迭代器：next_doc_count通常更高，它要不断产生候选
• 跟随迭代器：advance_count通常更高，它只在候选 docID 上确认

需要注意：Profile 只提供观察线索，不同 Lucene 版本、查询类型（DocValues、PointRange 等）和数据分布，都可能让next_doc/advance的表现有所不同。特别是当查询走了 BitSet 优化路径或 BlockMaxConjunctionScorer 时，指标分布会不一样。解读时要结合description、type和各子节点的 breakdown 一起判断。

八、小结与预告

回到本系列的主题：布尔查询子句重排序。本文讲的是其中最典型的一种——MUST / FILTER 这类合取子句进入执行层后，会从“用户书写顺序”转换为“按 cost 排序的迭代器执行顺序”。

本文着重介绍的核心机制包括：

• ConjunctionDISI 按 cost 排序：最稀疏的迭代器领头，其他迭代器仅做确认，最大化跳过无效文档
• 两阶段验证按 matchCost 排序：最便宜的验证先执行，失败即可短路
• leadCost 传播：代价信息从外向内传播，子查询据此做局部最优策略选择（如 IndexOrDocValuesQuery 的自适应切换）
• 子合取展平：嵌套的 ConjunctionDISI 被拆包到同一层级，确保全局最优的迭代顺序

这些机制的共同特点是：代价感知 + 动态决策——排序在 Scorer 构造时完成，与用户书写顺序无关。

一条边界：老版本里混入多词查询，顺序仍然敏感

"与书写顺序无关"有个前提：每个子句在调度阶段都能被轻量地试探。TermQuery 满足——预建的 TermStates 让它能 O(1) 判断某段有无匹配，没有就返回 null，短路掉还没轮到的子句。但 prefix / wildcard / regexp / range-on-keyword / fuzzy 这类多词查询在 Lucene 9.5 之前不满足：它们一旦被调度就同步干重活——枚举全部 term、读倒排、建 bitset——而调度又是按书写顺序进行的。

在一个 2900 万文档、23 个主分段的索引上实测，must 里放一个极稀疏的 term（命中 12 篇，只落在 6 个段）和一个极稠密的 prefix（展开约 11.7 万个 term）：

两条查询逻辑等价却差了近 3 倍：prefix 写前面时，其余 17 个段的 term 返回 null 触发整段短路，但 prefix 的 bitset 已经白白建好又扔掉；term 写前面时，这些段根本轮不到 prefix 出场。

💡 结论：稀疏廉价的子句写在前面，让它先行短路，昂贵的多词查询就不会被无效触发。

分界线是 Lucene 9.5（PR #12055）：多词查询的 wrapper 自此实现了轻量的 ScorerSupplier，调度阶段只估成本不干活，重活推迟到真正取迭代器时才做，顺序自此真正无关。对应到版本：Easysearch 1.x 基于 Lucene 8.11，存在此问题；Easysearch 2.x 基于 Lucene 9.12，已包含修复——本文的全部结论在其上均成立。

但合取查询的优化目标很明确：所有子句都要匹配，找"最少"的那个领头即可。析取（SHOULD）场景完全不同：不需要全部匹配，而是找Top-K 高分文档。优化目标从"最少匹配"变为"最高分数贡献"，WAND 算法登场——第三篇详解。

作者：冯田立，极限科技（INFINI Labs）Easysearch 搜索引擎研发专家，曾在亚马逊 AWS 有多年的 Elasticsearch 开源插件和 OpenSearch 的开发经验和客户集群的运维经验，并有幸参与 OpenSearch 的创立。