Rust in Everything
基于 tantivy 0.27.0

一次查询

主线位置:查询主线全程。从打开 reader 到拿回原文;每一步只讲到看清全貌的深度,细节链到 05 查询。索引就是一次写入提交出来的那个目录:三篇文档、三个段。

sequenceDiagram
  participant U as 你的代码
  participant R as IndexReader
  participant S as Searcher
  participant Q as BooleanQuery
  participant G as 每个段
  participant C as TopDocs
  U->>R: reader_builder try_into
  U->>S: reader searcher
  U->>Q: QueryParser parse_query
  U->>S: search query collector
  S->>Q: weight 用全局统计
  S->>G: 逐段 collect_segment
  G->>C: for_each_pruning 前 10
  S->>C: merge_fruits
  U->>S: doc 取原文

程序

实验 intro-run 的 search 子命令(release),打开一次写入写出的目录:

fn search(dir: &Path) -> tantivy::Result<()> {
  let index = Index::open_in_dir(dir)?;
  let s = index.schema();
  let (title, body) = (s.get_field("title").unwrap(), s.get_field("body").unwrap());
  let reader = index.reader_builder().reload_policy(ReloadPolicy::Manual).try_into()?;
  let searcher = reader.searcher();
  // ... 打印每个段的 id 和 max_doc
  let qp = QueryParser::for_index(&index, vec![title, body]);
  let q = qp.parse_query("old man")?;
  println!("query: {q:?}");
  let top = searcher.search(&q, &TopDocs::with_limit(10).order_by_score())?;
  for (score, addr) in &top {
    let d: TantivyDocument = searcher.doc(*addr)?;
    println!("{score:.6} {addr:?} {}", d.to_json(&s));
  }
  if let Some((_, addr)) = top.first() {
    println!("{}", q.explain(&searcher, *addr)?.to_pretty_json());
  }
  Ok(())
}

输出的前几行:

segments: 3
  seg 0: 39699d13823c45e2b5242220a91259a6 max_doc=1
  seg 1: 592a496b97fb426e8d5b469a16aa5dd0 max_doc=1
  seg 2: ed3c66cec91d4a719a28f4e54c98a532 max_doc=1
query: BooleanQuery { subqueries: [(Should, TermQuery(Term(field=0, type=Str, "old"))), (Should, TermQuery(Term(field=1, type=Str, "old"))), (Should, TermQuery(Term(field=0, type=Str, "man"))), (Should, TermQuery(Term(field=1, type=Str, "man")))], minimum_number_should_match: 1 }
4.297436 DocAddress { segment_ord: 1, doc_id: 0 } {"title":["The Old Man and the Sea"]}

三篇里只有《老人与海》命中。下面按顺序走一遍这几行背后的代码。

IndexReader 与 Searcher:一组段的快照

reader_builder().try_into() 打开 meta.json 里列出的每个段,建一个 SegmentReader,再把它们装进一个 Searcher。searcher() 返回的是这组 SegmentReader 的快照:之后有新的提交、合并、GC,这个 Searcher 看到的段都不变,删段的 GC 也不会删掉它正在用的文件。三个段在 Searcher 里按 meta.json 的顺序编号 0、1、2,结果里的 DocAddress { segment_ord: 1, doc_id: 0 } 就是「第 1 个段的第 0 篇」。Searcher 建好时已经为每个段打开了文档存储的读取器(SearcherInner::new),所以后面的 doc 不用再打开文件。

程序用的是 ReloadPolicy::Manual。默认的 ReloadPolicy::OnCommitWithDelay 多一个线程。实验 readerthreads 在同一个目录上依次建两种 reader,用 sample 看线程:

== threads after open_in_dir: 1 ==
   com.apple.main-thread  (serial)
== threads after Manual reader: 1 ==
   com.apple.main-thread  (serial)
== threads after default reader(): 2 ==
   com.apple.main-thread  (serial)
   thread-tantivy-meta-file-watcher

这个线程每 500 ms(POLLING_INTERVAL)算一次 meta.json 的 crc32,变了就回调 reload。所以「提交后多久能查到」取决于这次轮询什么时候发生,commit() 返回时并不保证已经 reload;0.27.0 在 ReloadPolicy 的文档里把这一点写明了(#3057),要确定性就用 Manual 加显式的 reader.reload()。打开、reload、warmer 和快照的生命周期见 IndexReader 与 Searcher。

QueryParser:old man 变成四个子句

QueryParser::for_index(&index, vec![title, body]) 记下两个默认字段。parse_query 分两步:子 crate query-grammar 用 nom 把字符串解析成与 schema 无关的 UserInputAst(两个不带字段名的词);QueryParser 再结合 schema 展开:没写字段的词在每个默认字段上各生成一个子句,文本用该字段的分词器切词(default 分词器把 old 和 man 原样小写),默认的连接方式是 OR。于是 old man 成了上面输出里的四个 Should 子句,minimum_number_should_match: 1:四个词项里命中任意一个就算匹配。

这就是默认 OR 的后果:用户输入两个词,只命中其中一个的文档也会进结果。要改成「每个词都要出现」,用 set_conjunction_by_default()。语法、LogicalAst 和容错解析见查询解析器。

weight:BM25 的统计在整个 Searcher 上算

Searcher::search 先判断收集器要不要分数(TopDocs 按分数排序,要),再进 search_with_executor:

        let weight = query.weight(enabled_scoring)?;
        collector.check_schema(self.schema())?;
        let segment_readers = self.segment_readers();
        let fruits = executor.map(
            |(segment_ord, segment_reader)| {
                collector.collect_segment(weight.as_ref(), segment_ord as u32, segment_reader)
            },
            segment_readers.iter().enumerate(),
        )?;
        collector.merge_fruits(fruits)

query.weight() 只调一次,对象是整个查询;它为每个 TermQuery 算出 BM25 里与文档无关的部分:总文档数 N、含这个词的文档数 n、字段的平均长度。这些数都从 Searcher 取,是三个段加起来的值,不是某一个段的。Query 只描述「查什么」,Weight 是绑定了这些统计之后的版本,可以在任意一个段上生成 Scorer。三层各自的职责见 Query、Weight、Scorer,公式见 BM25。

❗IMPORTANT
动脑筋:一个段和三个段,分数一样吗?

同样三篇文档,一种是一次写入里 3 个线程写出的 3 个段,每段一篇;另一种用 writer_with_num_threads(1, 15_000_000) 写成 1 个段。两个索引都查 old man,《老人与海》的分数是否相同?如果不同,哪个高?答案在动脑筋答案。

每个段跑一遍,再合并

executor 是 Index 上的 Executor,默认是 SingleThread:三个段在调用 search 的线程上依次处理。Index::set_default_multithread_executor 才会换成一个 rayon 线程池,按段并行;一个大段的索引因此快不了。

每个段上,TopDocs::order_by_score() 走 collect_segment_top_k:维护一个大小为 10 的堆,调 weight.for_each_pruning(...),每收下一篇就把当前第 10 名的分数作为门槛还给 scorer。BooleanQuery 的 for_each_pruning 先在这个段上为每个子句建 scorer,然后看形状:

  • 段里根本没有的词,TermWeight::specialized_scorer 返回空 scorer,complex_scorer 把空 scorer 从 Should 里剔掉;《人鼠之间》和《弗兰肯斯坦》那两个段四个子句全空,整段直接跳过。
  • 剩下的全是读词频的 TermScorer 时,组成 TermUnion,交给 block_wand:利用倒排表每块记下的分数上界,跳过不可能进前 10 的块。

三篇文档的例子里剪枝无事可做,但走的是同一条路。Block-Max WAND 和其他形状的布尔查询见布尔查询,TopDocs 的堆和门槛见收集器。

各段的前 10 收齐后,merge_fruits 调 merge_top_k 再取一次全局前 10。最后 Searcher::doc 用 segment_ord 找到那个段的 StoreReader,解压文档所在的块,反序列化出 TantivyDocument。结果里只有 title:body 没有 STORED,文档存储里根本没有它。块的格式和缓存见文档存储。

explain:4.297436 是怎么来的

Query::explain 重新建一次 weight,在文档所在的段上逐子句算分并记下每一项。输出有 218 行,四个子句的结构相同,这里保留前两个:

{
  "value": 4.2974358,
  "description": "BooleanClause. sum of ...",
  "details": [
    {
      "value": 0.8781843,
      "description": "TermQuery, product of...",
      "details": [
        {
          "value": 2.2,
          "description": "(K1+1)"
        },
        {
          "value": 0.9808292,
          "description": "idf, computed as log(1 + (N - n + 0.5) / (n + 0.5))",
          "details": [
            {
              "value": 1.0,
              "description": "n, number of docs containing this term"
            },
            {
              "value": 3.0,
              "description": "N, total number of docs"
            }
          ]
        },
        {
          "value": 0.40697676,
          "description": "freq / (freq + k1 * (1 - b + b * dl / avgdl))",
          "details": [
            {
              "value": 1.0,
              "description": "freq, occurrences of term within document"
            },
            {
              "value": 1.2,
              "description": "k1, term saturation parameter"
            },
            {
              "value": 0.75,
              "description": "b, length normalization parameter"
            },
            {
              "value": 6.0,
              "description": "dl, length of field"
            },
            {
              "value": 4.6666665,
              "description": "avgdl, average length of field"
            }
          ]
        }
      ],
      "context": [
        "Term=Term(field=0, type=Str, \"old\")"
      ]
    },
    {
      "value": 1.2705336,
      "description": "TermQuery, product of...",
...
            {
              "value": 27.0,
              "description": "dl, length of field"
            },
            {
              "value": 61.0,
              "description": "avgdl, average length of field"
            }
...
      "context": [
        "Term=Term(field=1, type=Str, \"old\")"
      ]
    },
...

逐项对:

  • idf:old 在三篇里只出现在一篇,log(1 + (3 - 1 + 0.5) / (1 + 0.5)) = log(2.667) = 0.98083。man 也是一篇,所以四个子句的 idf 一样。
  • title 子句:《The Old Man and the Sea》切出 6 个词,dl = 6;三篇的 title 长度是 6、4(Of Mice and Men)、4(Frankenstein 加 The Modern Prometheus 两个值,1 + 3),avgdl = 14 / 3 = 4.667。词频项是 1 / (1 + 1.2 × (0.25 + 0.75 × 6 / 4.667)) = 0.40698,乘上 (k1 + 1) = 2.2 和 idf,得 0.87818。
  • body 子句:body 是 27 个词,比平均的 61 短,长度惩罚小,词频项 0.58880,子句分 1.27053。
  • 合计:old 和 man 各两个子句,2 × 0.87818 + 2 × 1.27053 ≈ 4.2974。

k1 = 1.2、b = 0.75 是 bm25.rs 里的常量,不能配置;dl 来自 .fieldnorm,每篇每字段一个字节,长文档的长度会被量化;这里的 6 和 27 是精确值,一个段里能看到文件中存的就是这两个字节。avgdl 不从 fieldnorm 算,用的是字段的总词数除以文档数。逐项推导和量化见 BM25。

动脑筋答案

完全相同。同一个程序查一次写入的三段索引和用一个线程写出的单段索引,两份输出用 diff 比,只有段的清单和 segment_ord 不同:

1,2c1,4
< segments: 1
<   seg 0: 0da44b1601a146fd8142ee36fa955622 max_doc=3
---
> segments: 3
>   seg 0: 54b8db32a1d94d94a36fa15ab78c57dd max_doc=1
>   seg 1: 6e260b41f440454eba28afc7288c881c max_doc=1
>   seg 2: 948c91d593b4478eaedc103a36fdd1e7 max_doc=1
4c6
< 4.297436 DocAddress { segment_ord: 0, doc_id: 0 } {"title":["The Old Man and the Sea"]}
---
> 4.297436 DocAddress { segment_ord: 2, doc_id: 0 } {"title":["The Old Man and the Sea"]}

(这次对比用的三段索引是同一程序的另一次运行,段 id 和上文不同。)分数都是 4.297436,explain 的 218 行逐字相同。原因就是 weight 那一节:N、n、avgdl 在 query.weight() 里按整个 Searcher 统计,和文档被分到哪个段无关。如果改成每段各算各的,三段索引里每个段 N = 1,old 的 idf 会变成 log(1 + 0.5 / 1.5) = 0.288,分数会低得多,而且同一篇文档的分数会随着合并变化。需要自己控制这些统计(比如跨多个索引的分布式查询)时,用 search_with_statistics_provider 传一个 Bm25StatisticsProvider。

小结

  • Searcher 是一组 SegmentReader 的快照;建好时已为每个段打开文档存储。默认 OnCommitWithDelay 多一个 thread-tantivy-meta-file-watcher,每 500 ms 查一次 meta.json 的 crc32。
  • QueryParser 先用 query-grammar 解析,再按默认字段展开,默认 OR:old man 在两个字段上是四个 Should 子句、至少命中一个。
  • query.weight() 只调一次,BM25 的 N、n、avgdl 来自整个 Searcher;一段和三段的分数完全相同。
  • 默认 Executor 单线程,段依次处理;按分数取前 K 时走 for_each_pruning,全是 TermScorer 的 OR 用 Block-Max WAND,没命中的段直接跳过。
  • 各段前 10 用 merge_top_k 合并,doc 按 segment_ord 从文档存储解压原文;没 STORED 的字段取不回来。
  • explain 把 4.297436 拆成四个子句:idf 0.98083,(k1+1) = 2.2,词频项按 dl/avgdl 惩罚长字段;k1、b 是常量。

💬 关联讨论

发起讨论
加载中...