BulkScorer(一)(Lucene 9.6.0)
Lu Xugang Lv6

  本篇文章介绍在查询阶段,BulkScorer相关的知识点,在查询流程中的流程点如下红框所示:

图1:

父类BulkScorer

  BulkScorer类的定位是一个对满足查询条件的所有文档号进行收集的最初入口。在执行完该类的方法一后,Lucene就完成了一个段中文档号的收集工作。我们仅关注下BulkScorer类中下面的两个方法,如下所示:

方法一

图2:

  该方法说的是在某个文档号区间内,即参数minmax组成的区间,进行文档号的收集,同时使用参数acceptDocs过滤掉被删除的文档号,最终满足查询条件的文档号使用参数collector收集存储。

acceptDocs

  acceptDocs是一个基于位图实现,用来描述被删除的文档号信息的对象。由于在Lucene中执行删除文档操作时,并不会去修改现有的索引文件,而是额外的在名为.liv的索引文件中记录被删除的文档号。

  也就说,在方法一中依次处理满足查询条件的文档号时,有些文档号对应的文档尽管是满足查询条件的,但是它已经是被标记为删除的,故需要通过acceptDocs进行过滤。

collector

  满足查询条件的文档号会使用collector进行收集,在collector中会对文档号进行排序等操作,详细内容见Collector(一)。另外collectorLeafCollector对象,说的是对某个段进行收集。

min、max

  min和max用于指定一个待遍历的文档号区间,在有些子类实现中如果根据某些条件可以尽可能的降低区间的范围,那么可以降低整个查询时间(在介绍ReqExclBulkScorer时会介绍)。默认的实现中,min的值为0,max的值为Integer.MAX_VALUE。

方法二

图3:

  该方法描述的是遍历所有满足查询条件的文档号的开销,这个取决于不同的BulkScorer子类实现,在下文中再展开介绍。

BulkScorer的子类

  主要介绍下这几个最常见的子类:

图4:

DefaultBulkScorer

  DefaultBulkScorer子类中实现图2中方法一的流程图如下所示:

图5:

从Scorer中获取scorerIterator

图6:

  Scorer的概念会在以后的文章中详细介绍,在本篇文章中我们只需要暂时知道,该对象会提供一个DocIdSetIterator抽象类(下文中简称为DISI)的对象scorerIterator,通过该对象我们就可以获取到满足查询条件的所有文档号,并且在DocIdSetIterator类的不同实现中,获取每一个文档号的逻辑也是不同的。

DocIdSetIterator

  DISI是一个有状态的,对non-decreasing类型的文档号集合进行遍历的迭代器,并且集合中的文档号都是满足查询条件的(被删除的文档号也在集合中)。non-decreasing指的是集合中的每个文档号都大于等于排在它前面的文档号。例如下面的集合就是non-decreasing:

1
{1, 2, 2, 3, 4}

  这个类中有四个核心的方法:

方法一(DISI)

图7:

  该方法体现出DISI是具有状态的,它返回DISI当前的状态值,即目前遍历到的文档号。

  注释中说到,如果在调用nextDoc()或者advance(int)方法前就调用当前方法,会返回-1,意思是DISI的最初的状态值是-1,也就是文档号为-1,当然了,该值不是一个合法的文档号。另外如果遍历完所有的文档号,那么当前方法会返回一个NO_MORE_DOCS作为结束标志,该值即Integer.MAX_VALUE。

图11:

方法二(DISI)

图8:

  该方法会基于docID()中的文档号(当前状态值),返回在集合中排在它后面,下一个位置的文档号,随后将状态值更新为该位置的文档号。

  如果DISI当前的状态值已经是集合中的最后一个文档号,那么调用该方法会返回NO_MORE_DOCS,并且将状态值更新为NO_MORE_DOCS。注意的是,不应该在这种情况下继续调用该方法,否则会导致不可预测行为。

方法三(DISI)

图9:

  该方法会返回集合中第一个大于等于target的文档号,并且将状态值更新为这个文档号。

  如果未在集合中找到,那么会返回NO_MORE_DOCS。并且将状态值更新为NO_MORE_DOCS

方法四(DISI)

图10:

  该方法描述的是遍历DISI中的文档号集合的开销,在有些子类实现中该值就是集合中文档号数量的一个准确值,然而在有些实现则是一个估计值。

DocIdSetIterator的子类

  下图给出的是实现比较简单的一个子类:

图12:

是否可以获取实现Skip Docs的DISI?

图13:

  如果从数据集的角度去思考如何提高查询性能,通常可以通过以下两种方式实现:

  1. 减少数据集的规模
  2. 收集到足够的结果后,提前退出

  这里的第二点在图5的collector收集docId中实现,见Collector(四)。第一点则是通过可以实现Skip Docs的DISI对象competitiveIterator结合图6 Scorer中获取的scorerIterator,将这两个DISI对象组合成一个新的DISI对象filteredIterator来实现减少数据集的规模

  注意点:只有在获取TopN的查询中,才有可能获取到实现Skip Docs的DISI对象competitiveIterator

filteredIterator的实现逻辑

  在收集了TopN篇文档号,随后继续遍历scorerIterator时,如果根据排序规则,可以添加到TopN中时,就会尝试获取/更新competitiveIterator,通过competitiveIterator实现skip docs。

  目前Lucene中有基于BKD树(LUCENE-9280)以及基于倒排(LUCENE-10633)来获得competitiveIterator。见文章查询TopN的优化之NumericDocValues(一)查询TopN的优化之NumericDocValues(二)了解基于BKD树获取competitiveIterator。

  下面的例子中,主要是表达优化思想,并不是真实的实现逻辑

图14:

  图14中假设是Top3的查询,如果没能获取competitiveIterator,那么需要遍历集合中所有的文档号。优化后,在收集完Top3后,根据Top3中的竞争力最小的信息(基于排序规则对应的域值)获取一个集合为[7, 99]的competitiveIterator,意思是根据排序规则,在这个集合区间范围外的文档是没有竞争力(non-competitive),也就是没有必要去处理这些文档号。随后在处理完第56篇文档号,再次更新了competitiveIterator。

遍历filteredIterator

图15:

docId是否在区间内

  这里的区间指的是方法一中参数maxmin组成的区间,由于从filteredIterator中依次获得的文档号是递增的,所以当出现文档号不在区间内时,就可以直接退出遍历。

docId不是被删除的文档号并且满足二阶段遍历?

  在这个流程点,我们需要过滤被删除的文档号,尽管这些文档是满足查询条件的。

二阶段遍历

  二阶段遍历在大部分查询场景中不会出现,在此流程点如果二阶段遍历为空,则认为是满足条件的。在文章二阶段遍历(TwoPhaseIterator)中详细的介绍了为什么要使用二阶段遍历,以及给出了某个场景作为例子。这里就不展开介绍了。

collector收集docId

  在系列文章Collector(一)中介绍常见的几个Collector,这里就不赘述了。

结语

  基于篇幅,剩余的内容将在下一篇文章中展开介绍。

点击下载附件

 Comments
Comment plugin failed to load
Loading comment plugin
Powered by Hexo & Theme Keep
This site is deployed on
Total words 319.8k Unique Visitor