布尔查询
主线位置:查询主线的
Searcher::search里。old man解析出的是一个四个Should子句的BooleanQuery;每个段上,BooleanWeight先为子句建 scorer,再按「有哪些 Must、Should、MustNot,子 scorer 是不是TermScorer」挑一种合并方式;TopDocs取前 10 时,能走 Block-Max WAND 的形状整块跳过不可能进前 10 的文档。
flowchart TB
bw["BooleanWeight"] --> must["Must 子句对齐"]
must --> strip["剔除 All 和 Empty"]
strip --> how{"Should 怎么用"}
how -->|Ignored| ign["只有 Must"]
how -->|Optional| opt["ReqOpt"]
how -->|Required| req["并集或 Disjunction"]
ign --> ti["TermIntersection"]
ign --> other["Other"]
req --> tu["TermUnion"]
req --> other
opt --> other
ti --> bwi["block_wand_intersection"]
tu --> bwu["block_wand"]
other --> excl["有 MustNot 时 Exclude"]
excl --> plain["逐篇比较门槛"]
代码在 src/query/boolean_query/(6 个文件 3533 行,含测试)和 src/query/ 下的 intersection.rs、union/、exclude.rs、reqopt_scorer.rs、disjunction.rs、score_combiner.rs。Block-Max WAND 有两份:并集的 block_wand_union.rs(620 行)和 0.27.0 新增的交集版 block_wand_intersection.rs(662 行),两份都有一半以上是 proptest。
实验平台:M2 Max、macOS 27、rustc 1.99.0,tantivy 0.27.0(对照组 0.26.1),release 构建。实验程序在 srcha-lab/src/bin/(wand.rs、boolmisc.rs、maxscore.rs、blockmax.rs、dismax.rs)。
BooleanQuery 与 Occur
BooleanQuery 是一组 (Occur, Box<dyn Query>) 加一个 minimum_number_should_match。Occur 定义在 query-grammar crate 里,三个值:Should、Must、MustNot。
BooleanQuery::new 决定默认的最少命中数:只有 Should 子句时是 1,出现任何 Must 或 MustNot 就是 0(注释说和 Elasticsearch 保持一致)。所以 a b 至少命中一个,+a b 里的 b 只影响分数。
Query::weight 为每个子句建 Weight,装进 BooleanWeight::with_minimum_number_should_match,分数合并器是 SumCombiner。构造时先按 Should 子句数和最少命中数改写一次:
- 子句数大于最少命中数:保持原样;
- 相等:每个
Should都必须命中,全部提升为Must,最少命中数清零; - 小于:不可能满足,换成一个空的
Weight。
第二条有个副作用:只有一个 Should 子句的 BooleanQuery(最少命中数默认是 1)会被改写成只有一个 Must,下面的 Block-Max WAND 会讲到它的代价。第三条也是 0.27.0 删掉 BooleanWeight::new 的原因:PR #3071 的说明是「BooleanWeight::new just default min_should_match to 1」,只传一个 Must 子句的人会得到空结果,「it is quite the footgun」。现在只剩必须显式给出最少命中数的构造函数。
只有 MustNot 的布尔查询什么也匹配不到:
[-the] count 0 [+* -the] count 398
排除是「从某个集合里去掉」,必须有一个正向的集合。要表达「不含 the 的所有文档」,得自己加一个 Must 的 AllQuery。
按形状挑实现
每个段上,complex_scorer 依次做这些事:
- 对齐 Must。
create_aligned_scorers_for_intersection用scorer_danger逐个建Must的 scorer,每个都从当前候选文档开始,轮流seek_danger,直到所有 scorer 停在同一篇上;对不齐就返回空 scorer,整个段跳过。 - 建 Should 和 MustNot 的 scorer。
- 剔除特殊 scorer。
AllScorer(匹配全部)和EmptyScorer(匹配不到)从三组里拿出来计数:Must里有空的,整段为空;MustNot里有全集,整段为空;Should里的全集抵掉一个最少命中数。段里根本没有的词就在这一步消失,所以old man在没有这两个词的段上什么也不做。 - 决定 Should 的用法(
ShouldScorersCombinationMethod):最少命中数为 0 且没有 Should 子句是Ignored;为 0 是Optional,只加分;为 1 是Required,建并集;等于剩下的 Should 个数时并进Must;其他情况是Required,用Disjunction按命中数过滤。 - 组合,得到一个
SpecializedScorer:
enum SpecializedScorer {
TermUnion(Vec<TermScorer>),
TermIntersection(Vec<TermScorer>),
Other(Box<dyn Scorer>),
}
TermUnion 和 TermIntersection 是留给 Block-Max WAND 的两种特殊形状,其余一律装箱成 Other。scorer_union 只有在所有子 scorer 都是 TermScorer、并且都读词频(FreqReadingOption::ReadFreq)时才给出 TermUnion;TermIntersection 要求没有 Should、没有被剔除的全集、至少两个 Must、全是读词频的 TermScorer。
- 排除。 有
MustNot时,把上面的结果装箱,外面套一层Exclude。
交集:Intersection
intersect_scorers 按 cost() 从小到大排序,最便宜的两个放进 left 和 right 字段,其余进 others;前两个都是 TermScorer 时用 Intersection<TermScorer, Box<dyn Scorer>>,省掉这两个的动态分派。
前进的核心是 seek_from_candidate:left 用普通 seek 定出候选,right 和 others 用 seek_danger 确认;任何一个回答 SeekLowerBound(d),候选就跳到 d,从 left 重新来。只有 left 必须处于有效状态,其他子集合在确认失败时可以停在无效状态,下一轮还是只对它们调 seek_danger。分数是各子 scorer 之和,写死在 Intersection::score 里,和合并器无关。
计数另有一条路(count_including_deleted):打头的集合覆盖段里超过约 1/32 的文档时,每 1024 篇为每个子集合填一次位图,按位与后 popcount,不逐篇前进。
并集:BufferedUnionScorer
BufferedUnionScorer 不用堆,而用一个 4096 篇宽的窗口:
const HORIZON_NUM_TINYBITSETS: usize = HORIZON as usize / 64;
const HORIZON: u32 = 64u32 * 64u32;
bitsets是 64 个 64 位的TinySet,标记窗口里哪些文档出现过;scores是 4096 个分数合并器,一篇一个。refill把窗口起点设成所有子 scorer 里最小的 doc id,然后对每个子 scorer,把落在窗口里的文档全部推进来:置位,update对应的合并器,advance。子 scorer 是一个接一个处理的,每个都顺序读自己的倒排表。advance从当前桶里弹出最低位,读出合并好的分数;窗口空了再refill。seek的目标在窗口里时,清掉中间的桶;超出窗口时,清空整个窗口,让每个子 scorer 自己seek,再refill。
代价是每个并集带一个 4096 项的合并器数组(求和时每项一个 f32,共 16 KB),换来的是没有堆操作、内层循环只有置位和加法。计数时整窗 popcount。0.26.2 起它不再覆盖 seek_danger,用回默认实现:之前的优化版本在一个子集合确认失败、另一个子集合命中时,会让 refill 读到没对齐的子 scorer(0.26.2 CHANGELOG 记为 #3086)。
最少命中数大于 1 时用另一个结构 Disjunction:按当前 doc id 排序的二叉堆,每篇文档数一下有几个子 scorer 停在上面,够数才输出。
Exclude 与 RequiredOptionalScorer
Exclude 包住正向的 scorer,每得到一个候选就问排除集合 contains(doc),实现是 seek_danger(doc) == Found。排除集合只被「问」,不参与打分;多个 MustNot 时是一个 Vec,逐个问。
RequiredOptionalScorer 处理 +a b:文档集合完全由必需的一侧决定,advance、seek 只动它;可选的一侧只在 score 被调用时才 seek 过去看看在不在,结果缓存在 score_cache 里。不打分时干脆不建这一层,可选子句直接丢掉。
这两种形状都是 Other,TopDocs 取前 K 时没有 Block-Max WAND。
Block-Max WAND
取前 K 时,收集器手里有一个门槛:当前第 K 名的分数。一篇文档的分数是各个词的分数之和,如果能在解码之前算出「这里的文档最多能得多少分」,低于门槛的就可以整块跳过。tantivy 有两个层次的上界:
- 整个词的上界:
Bm25Weight::max_score(),即idf × (k1 + 1),词频趋于无穷时的极限(BM25)。 - 块上界:倒排表每个 128 篇的满块在跳表里存了一对
(fieldnorm_id, tf),查询时用当前的Bm25Weight算成分数(倒排表)。不足 128 篇的尾块没有这个信息,已解码时现算,未解码时退回整个词的上界。
BooleanWeight::for_each_pruning 按 SpecializedScorer 分派:
match scorer {
SpecializedScorer::TermUnion(term_scorers) => {
if TScoreCombiner::SUPPORTS_BLOCK_WAND {
super::block_wand(term_scorers, threshold, callback);
} else {
let mut union_scorer =
BufferedUnionScorer::build(term_scorers, &self.score_combiner_fn, num_docs);
for_each_pruning_scorer(&mut union_scorer, threshold, callback);
}
}
// ...
SpecializedScorer::TermIntersection(term_scorers) => {
super::block_wand_intersection(term_scorers, threshold, callback);
}
SpecializedScorer::Other(mut scorer) => {
for_each_pruning_scorer(scorer.as_mut(), threshold, callback);
}
}
Other 走的 for_each_pruning_scorer 只是「每篇都算分,超过门槛才回调」,没有跳块。
并集:block_wand
block_wand 是论文「Faster Top-k Document Retrieval Using Block-Max Indexes」的算法。子 scorer 始终按当前 doc id 排序,每一轮:
- 找枢轴。
find_pivot_doc从 doc id 最小的 scorer 开始累加整个词的上界,第一次超过门槛的那个 scorer 所在的文档就是枢轴:比它小的文档,就算前面几个词全中,也到不了门槛。累加到最后都没超过,整个段结束。 - 查块上界。 停在枢轴之前及枢轴上的每个 scorer 都
seek_block(pivot),只移动跳表、不解码,再把各自的块上界加起来。不超过门槛,就调block_max_was_too_low_advance_one_scorer:挑上界最大的那个 scorer,跳到这些块里最早结束的块之后,但不越过枢轴之后那些 scorer 的当前文档。 - 对齐和打分。 块上界够了,才把枢轴之前的 scorer 真正
seek到枢轴;有一个不包含枢轴,就回到第 1 步;全部对齐后算出真实分数,超过门槛才回调,回调返回新门槛。
只剩一个词时,block_wand 转给 block_wand_single_scorer:块上界不超过门槛就跳到下一块,否则把这一块逐篇算完。TermQuery 直接用的也是它。
交集:block_wand_intersection
0.27.0 的 PR #2865 加了 block_wand_intersection。按 size_hint 选最稀有的词做「领头」,以领头的块为单位:
- 所有 scorer
seek_block到当前位置,窗口取各自当前块的最小结尾;所有块上界之和不超过门槛,跳过整个窗口。 - 否则解码领头的这一块,先只用领头的真实分数加上其余词的块上界过滤(分支写成条件累加,方便编译成
cmov),幸存的候选才去其他 scorer 里seek确认,每确认一个词就用「已得分 + 剩余词的块上界」再剪一次。
0.27.0 改了什么
CHANGELOG 0.27.0 把这一组改动记作一条:「Block-max pruning for top-K on conjunctive queries, and Block-Max WAND for single-scorer boolean queries」(#2865、#2897、#2912、#2915、#2981、#3003)。按提交看:
- #2865:交集版 Block-Max。
d27ca164a(#2912):block_wand只剩一个 scorer 时走单 scorer 的路径。- #2915:
scorer_union去掉了「只有一个 scorer 就直接装箱」的提前返回,让一个读词频的TermScorer也能成为TermUnion。实际受益的是「多个 Should 子句、但这个段里只有一个词出现」的情况:其余子句在第 3 步被当作空 scorer 剔掉,剩下的一个词现在也能剪枝。 - #2897:单 scorer 版跳块的条件从
<改成<=,和多 scorer 版一致,分数相同的文档很多时少解码一些块。 874d54a63:#2915 让「一个词的并集」在装箱时变成了BufferedUnionScorer,在RequiredOptionalScorer的可选侧造成性能回退;改为只在剪枝路径上保留TermUnion,装箱时拆回单个TermScorer。
实测:剪枝什么时候有用
wand.rs 用 BooleanQuery 手工拼 body 上的 Should 或 Must 子句(WithFreqs),每个查询比较四种收集方式:
top10:TopDocs::with_limit(10).order_by_score(),走for_each_pruning;(top10,count):同时数总数。元组收集器没有覆盖collect_segment,走默认的for_each:每篇都算分,不剪枝;count:Count,走计数的捷径,不打分;top10[Basic]:同样的查询,子句的TermQuery用IndexRecordOption::Basic。
callbacks 是 for_each_pruning 把文档交给收集器的次数,hits 是命中总数。先是 1000 篇真实维基,每项 200 次取最小值(负载约 3.5):
docs 1000 segments 1
Should the of hits 866 callbacks 43 same_top10 true | top10 15.6 us (top10,count) 9.5 us count 4.5 us top10[Basic] 8.5 us
Should american football hits 149 callbacks 35 same_top10 true | top10 3.6 us (top10,count) 4.0 us count 1.8 us top10[Basic] 3.7 us
Should river city county hits 144 callbacks 35 same_top10 true | top10 4.9 us (top10,count) 4.6 us count 2.4 us top10[Basic] 4.3 us
Should music album band song hits 72 callbacks 28 same_top10 true | top10 5.0 us (top10,count) 5.0 us count 2.9 us top10[Basic] 4.9 us
Should war army battle history empire hits 176 callbacks 39 same_top10 true | top10 6.5 us (top10,count) 6.8 us count 3.7 us top10[Basic] 6.2 us
Must the of hits 753 callbacks 43 same_top10 true | top10 4.5 us (top10,count) 10.1 us count 4.7 us top10[Basic] 8.6 us
Must american football hits 12 callbacks 12 same_top10 true | top10 2.8 us (top10,count) 3.0 us count 2.0 us top10[Basic] 2.8 us
Must river city county hits 1 callbacks 1 same_top10 true | top10 3.3 us (top10,count) 3.5 us count 2.5 us top10[Basic] 3.3 us
Must music album band song hits 4 callbacks 4 same_top10 true | top10 4.0 us (top10,count) 4.2 us count 3.0 us top10[Basic] 4.0 us
1000 篇里大多数词的倒排表不满一块,没有块上界可用,几种方式都在几微秒。有差别的只有 the of 两行:交集剪枝 4.5 µs 对不剪枝 10.1 µs;并集剪枝反而更慢,15.6 µs 对 9.5 µs。the 和 of 几乎每篇都有,idf 很小,两个词的上界之和和第 10 名的分数相差无几(下面 10 万篇的语料里实测是 0.0402 对 0.0385),枢轴一轮轮地选出来又被否掉,每篇文档付出的簿记比直接算分还多。
真实维基太小,再用一个合成的大语料:从 1000 篇的正文里取出 3958 个至少有 3 个词的行,每篇随机拼 3 到 10 行,共 10 万篇(种子 42)。每一行平均被用到约 160 次,块与块之间的分数分布比真实语料平均得多,这对块上界剪枝是偏不利的。每项 20 次取最小值(负载约 3.6):
| 查询 | 命中 | 回调 | top10 | (top10,count) | count | top10[Basic] |
|---|---|---|---|---|---|---|
the of(OR) | 99,795 | 94 | 232.0 µs | 803.4 µs | 388.3 µs | 674.9 µs |
american football(OR) | 28,168 | 76 | 164.4 µs | 178.9 µs | 62.7 µs | 152.7 µs |
river city county(OR) | 31,628 | 75 | 191.8 µs | 193.8 µs | 67.7 µs | 172.3 µs |
music album band song(OR) | 23,618 | 77 | 298.1 µs | 161.4 µs | 61.2 µs | 146.5 µs |
war army battle history empire(OR) | 21,343 | 83 | 263.5 µs | 135.8 µs | 44.6 µs | 124.0 µs |
+the +of | 98,389 | 93 | 36.4 µs | 795.6 µs | 385.8 µs | 706.2 µs |
+american +football | 3,237 | 60 | 26.0 µs | 150.7 µs | 60.5 µs | 139.6 µs |
+river +city +county | 218 | 37 | 75.8 µs | 78.0 µs | 67.6 µs | 75.7 µs |
+music +album +band +song | 298 | 39 | 74.7 µs | 81.4 µs | 62.0 µs | 77.6 µs |
同一程序隔几分钟再跑一次,OR 各行和前两行 AND 的差别在 5% 以内,三个词以上的 AND 两行差到三成,数量级不变。读法:
- 交集剪枝收益最大。
+the +of从 796 µs 降到 36 µs,+american +football从 151 µs 降到 26 µs:领头的块上界加上另一个词的块上界很快就低于门槛,大部分块不解码。命中很少的交集本来就快,剪枝无事可做。 - 高频词的并集收益明显。
the of的并集 232 µs 对 803 µs,10 万篇里只回调了 94 次。 - 四五个中频词的并集,剪枝反而慢一倍。
maxscore.rs打印出music album band song四个词各自的上界(4.6 到 6.2,合计 21.95)和最终的门槛 14.51:任意三个词的上界加起来就能超过门槛,枢轴几乎每轮都成立,块上界的检查也很少能否掉,算法退化成「多做了很多簿记的并集」。BufferedUnionScorer顺序扫倒排表、在数组里累加,常数小得多。 Basic关掉了剪枝。 子句不读词频时scorer_union不给出TermUnion,交集也不给出TermIntersection,耗时和不剪枝的(top10,count)相当;而且所有文档的词频都当作 1,排序本身也变了。TermQuery和BooleanQuery文档里的示例用的就是Basic。(TopDocs, Count)关掉了剪枝。 剪枝有效的那几行,元组吃亏最多:+the +of分开查两次(36 µs 加 386 µs)也比元组的 796 µs 快;剪枝本来就无效的行,元组反而比分开查省一遍遍历。
same_top10 比较剪枝和不剪枝的前 10,按 1e-4 的相对误差判同。第一版程序要求分数差小于 1e-6 时,1000 篇维基上的 music album band song 曾判为不同:两边的文档和顺序完全一样,只有第 4 名的分数差最后一位(16.777549744 对 16.777551651)。剪枝版按枢轴顺序把各个词的分数相加,并集按子 scorer 的顺序相加,f32 加法不满足结合律。
还有几种常见形状不在快路径上,boolmisc.rs 在同一个 10 万篇语料上测(20 次取最小值):
the of hits 99795 top10 229.0 us (top10,count) 792.0 us
the of -battle hits 98792 top10 910.6 us (top10,count) 958.5 us
TermQuery the hits 99602 top10 19.1 us (top10,count) 378.2 us
Bool[Must the] hits 99602 top10 336.5 us (top10,count) 397.5 us
Bool[Should the] hits 99602 top10 336.1 us (top10,count) 397.0 us
+the of hits 99602 top10 853.6 us (top10,count) 937.5 us
- 加一个
MustNot,Exclude包住并集,变成Other:229 µs 变 911 µs。 +the of:RequiredOptionalScorer,同样是Other。- 后面的动脑筋问的是中间两行。
TermQuery(the) 取前 10 用 19 µs。把它包进一个只有一个子句的 BooleanQuery,无论这个子句是 Must 还是 Should,会更快、一样,还是更慢?提示:回到「BooleanQuery 与 Occur」一节,看构造时的改写;再看 TermIntersection 要求几个 Must。答案在文末。
块上界不一定是上界
BM25 一页讲过:块里存的那一对 (fieldnorm_id, tf) 是写段时用本段的 avgdl 挑出来的;查询时 avgdl 来自整个 Searcher,挑出来的那篇可能已经不是块里分数最高的。TermScorer::block_max_score 的注释说这种情况「extremely rare」,结果会偏低,「and may lead us to return a lesser document」。
blockmax.rs 构造了一个必然发生的例子。段 A 里每篇都含 x:
- 第 0 到 127 篇是
x x(长度 2,tf 2),构成第一个满块; - 第 128 到 255 篇是
x(长度 1,tf 1),只有第 200 篇是 10 个x加 90 个填充词(长度 100,tf 10),构成第二个满块; - 再加 10 篇
x作为尾块。
段 A 的 avgdl 约 1.85,在这个 avgdl 下,第二块里 tf 1、长度 1 的词频部分是 0.56,第 200 篇不到 0.2,块上界记成前者。段 B 是 3000 篇长度 1000、不含 x 的文档(每篇开头一个 zzz),把全局 avgdl 拉到 900 以上。这时第一块的文档每篇约 0.869,第二块记下的上界只有约 0.769,而第 200 篇的真实值是约 0.962:
segments 2
parsed: BooleanQuery { subqueries: [(Should, TermQuery(Term(field=0, type=Str, "x"))), (Should, TermQuery(Term(field=0, type=Str, "zzz")))], minimum_number_should_match: 1 }
TermQuery top1 first: 4.790494 DocAddress { segment_ord: 1, doc_id: 0 }
TermQuery top300 first: 5.304775 DocAddress { segment_ord: 1, doc_id: 200 }
BooleanQuery(1 Should) top1 first: 5.304775 DocAddress { segment_ord: 1, doc_id: 200 }
BooleanQuery(1 Should) top300 first: 5.304775 DocAddress { segment_ord: 1, doc_id: 200 }
QueryParser x zzz top1 first: 4.790494 DocAddress { segment_ord: 1, doc_id: 0 }
QueryParser x zzz top300 first: 5.304775 DocAddress { segment_ord: 1, doc_id: 200 }
- 取前 300 时堆一直没满,门槛始终是最小值,不剪枝,第一名是第 200 篇,5.304775。
- 取前 1 时,第一块让门槛升到 4.79,第二块的块上界算出来不到门槛,整块跳过,第一名变成了 4.790494 的第 0 篇。
QueryParser解析的x zzz也一样:段 A 里没有zzz,剔除后只剩x一个TermScorer,经 #2915 成为TermUnion,走单 scorer 剪枝。BooleanQuery(1 Should)结果正确,只是因为它被改写成了不剪枝的形状。
同一程序只建段 A(单段)时,四种查法的第一名都正确。拿 0.26.1 跑同一个程序,TermQuery 的结果相同(单词查询早就用块上界剪枝),QueryParser x zzz 取前 1 得到正确的 5.304775:0.26.1 里只剩一个 scorer 的并集不剪枝。0.27.0 让这种「多段、各段 avgdl 差别大」的偏差多了一条触发途径。
DisjunctionMaxQuery
DisjunctionMaxQuery 也是一个 BooleanWeight:所有子查询作为 Should,最少命中数 1,合并器换成 DisjunctionMaxCombiner,分数是「最高的子句分数 + 其余子句分数之和 × tie_breaker」。只要子查询都是读词频的 TermQuery,它在每个段上也会形成 TermUnion。
dismax.rs:rust 同时出现在第 0 篇的 title 和 body 里,用 DisjunctionMaxQuery 查两个字段的 TermQuery,比较剪枝路径(TopDocs)、不剪枝路径((TopDocs, Count))和 explain:
== 0.26.1
doc 0 TopDocs 1.341106 (TopDocs,Count) 0.906649 explain 0.906649
doc 1 TopDocs 0.434457 (TopDocs,Count) 0.434457 explain 0.434457
== 0.27.0
doc 0 TopDocs 0.906649 (TopDocs,Count) 0.906649 explain 0.906649
doc 1 TopDocs 0.434457 (TopDocs,Count) 0.434457 explain 0.434457
0.26.1 里同一篇文档,取前 10 得到的分数 1.341106 正好是两个字段之和(0.906649 + 0.434457),换个收集器就是 0.906649。
0.27.0 之前,BooleanWeight::for_each_pruning 见到 TermUnion 就交给 block_wand,不管合并器是什么。block_wand 按子句分数之和剪枝、也按和打分,于是合并器被换成了求和。PR #3022(「fix: do not drive a non-summing score combiner with Block-WAND」,首次发布在 0.27.0)的说明写道:「A DisjunctionMaxQuery collected through TopDocs therefore scored a document matching in two fields as the sum of both instead of the better of the two, and ignored the tie breaker」;这个 bug 藏得久,是因为「a query asking for Basic postings falls back to BufferedUnionScorer, which does honor the combiner」。修法是给 ScoreCombiner 加一个关联常量 SUPPORTS_BLOCK_WAND,默认 false,只有 SumCombiner 设为 true;其他合并器在 TermUnion 上退回普通并集。交集不需要这个开关,因为 Intersection::score 本来就写死了求和。
动脑筋答案
更慢,慢 17 倍左右:
TermQuery the hits 99602 top10 19.1 us (top10,count) 378.2 us
Bool[Must the] hits 99602 top10 336.5 us (top10,count) 397.5 us
Bool[Should the] hits 99602 top10 336.1 us (top10,count) 397.0 us
TermQuery 自己的 for_each_pruning 直接调 block_wand_single_scorer。包进 BooleanQuery 以后:
- 一个
Should子句时,BooleanQuery::new给出最少命中数 1,with_minimum_number_should_match发现子句数等于最少命中数,把它提升成Must;所以两种写法结果相同。 - 只有一个
Must:TermIntersection要求至少两个Must,这里不满足;effective_must_scorer把单个 scorer 原样交回,装箱成Other。 Other走for_each_pruning_scorer:每篇都算分,只是分数不够时不回调。10 万篇几乎都含the,于是和不剪枝的(top10,count)差不多。
#2915 让「一个词的并集」能剪枝,但只覆盖段里其他 Should 子句为空的情况;一开始就只有一个子句的 BooleanQuery,在构造 Weight 时就被改写掉了,走不到那里。
小结
BooleanQuery::new:只有Should时最少命中数为 1,否则为 0;BooleanWeight构造时把「Should 数等于最少命中数」的子句提升为Must,不可能满足的换成空Weight;只有MustNot什么也匹配不到。- 每个段上先对齐
Must、剔除全集和空集,再决定 Should 是忽略、加分还是必需,得到TermUnion、TermIntersection或Other;有MustNot时外面套Exclude。 - 交集按 cost 排序、用
seek_danger确认;并集是 4096 篇的位图窗口加分数数组;+a b用RequiredOptionalScorer,可选侧只在打分时才去看。 - Block-Max WAND 只用于全是读词频的
TermScorer的并集(合并器求和)和交集(至少两个Must);0.27.0 加了交集版和单词版。Basic记录、元组收集器、MustNot、+a b、单子句的BooleanQuery都不剪枝。 - 实测:交集和高频词的并集剪枝收益大(796 µs 降到 36 µs、803 µs 降到 232 µs),四五个中频词的并集剪枝反而慢一倍。
- 块上界按写段时本段的 avgdl 挑选,多段索引里可能偏低,取前 K 会漏掉真正的第一名;0.27.0 的 #2915 多了一条触发途径。#3022 修了 dis_max 被 Block-WAND 当作求和的问题。