Rust in Everything
基于 tantivy 0.27.0

布尔查询

主线位置:查询主线的 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 依次做这些事:

  1. 对齐 Must。 create_aligned_scorers_for_intersection 用 scorer_danger 逐个建 Must 的 scorer,每个都从当前候选文档开始,轮流 seek_danger,直到所有 scorer 停在同一篇上;对不齐就返回空 scorer,整个段跳过。
  2. 建 Should 和 MustNot 的 scorer。
  3. 剔除特殊 scorer。 AllScorer(匹配全部)和 EmptyScorer(匹配不到)从三组里拿出来计数:Must 里有空的,整段为空;MustNot 里有全集,整段为空;Should 里的全集抵掉一个最少命中数。段里根本没有的词就在这一步消失,所以 old man 在没有这两个词的段上什么也不做。
  4. 决定 Should 的用法(ShouldScorersCombinationMethod):最少命中数为 0 且没有 Should 子句是 Ignored;为 0 是 Optional,只加分;为 1 是 Required,建并集;等于剩下的 Should 个数时并进 Must;其他情况是 Required,用 Disjunction 按命中数过滤。
  5. 组合,得到一个 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。

  1. 排除。 有 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 排序,每一轮:

  1. 找枢轴。 find_pivot_doc 从 doc id 最小的 scorer 开始累加整个词的上界,第一次超过门槛的那个 scorer 所在的文档就是枢轴:比它小的文档,就算前面几个词全中,也到不了门槛。累加到最后都没超过,整个段结束。
  2. 查块上界。 停在枢轴之前及枢轴上的每个 scorer 都 seek_block(pivot),只移动跳表、不解码,再把各自的块上界加起来。不超过门槛,就调 block_max_was_too_low_advance_one_scorer:挑上界最大的那个 scorer,跳到这些块里最早结束的块之后,但不越过枢轴之后那些 scorer 的当前文档。
  3. 对齐和打分。 块上界够了,才把枢轴之前的 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)counttop10[Basic]
the of(OR)99,79594232.0 µs803.4 µs388.3 µs674.9 µs
american football(OR)28,16876164.4 µs178.9 µs62.7 µs152.7 µs
river city county(OR)31,62875191.8 µs193.8 µs67.7 µs172.3 µs
music album band song(OR)23,61877298.1 µs161.4 µs61.2 µs146.5 µs
war army battle history empire(OR)21,34383263.5 µs135.8 µs44.6 µs124.0 µs
+the +of98,3899336.4 µs795.6 µs385.8 µs706.2 µs
+american +football3,2376026.0 µs150.7 µs60.5 µs139.6 µs
+river +city +county2183775.8 µs78.0 µs67.6 µs75.7 µs
+music +album +band +song2983974.7 µs81.4 µs62.0 µs77.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。
  • 后面的动脑筋问的是中间两行。
❗IMPORTANT
动脑筋: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。

📝NOTE
冷知识:Block-WAND 曾经悄悄把 dis_max 变成了求和

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 当作求和的问题。

💬 关联讨论

发起讨论
加载中...