查询原理(五)终

  本文承接查询原理(四),继续介绍查询原理。

查询原理流程图

图1:

点击查看大图

合并查询结果

  该流程点遍历所有子收集器的结果,对这些进行结果进行合并,合并过程比较简单,即利用优先级队列,由于太过简单,故不详细展开了。

遗留问题

  在介绍这个遗留问题前,我们先说下在查询原理(三)的文章中,我们在介绍ReqExclBulkScorer时,有两个信息没有介绍,即cost、next,这两个信息用来选择哪些子查询进行处理。

图2:

图3:

  查询原理(四)的文章中,我们介绍了单线程下的查询原理的所有流程点,但还有一个很重要的逻辑没有介绍,那就是我们并没有介绍在还有未处理的子查询的情况下,如何选择哪个子查询进行处理,这个逻辑实际是个优化的过程,可能可以减少遍历区间(见查询原理(四))的处理,下面将填补这个坑。

  上文的描述可以拆分两个问题,以图3为例:

  这两个问题可以转化为一道面试算法题,来了解面试者对Lucene的熟悉程度:有N个int类型数组,其中所有数组的数组元素都是有序(升序)的,同一个数组内的数组元素都是不重复的,设计一种方法,从这N个数组中找出所有重复(minShouldMatch 大于等于2)的数组元素。

  对于上述的算法题,以图3为例,对于子查询1、子查询2、子查询3,总的时间复杂度至少为3个子查询的开销的和(子查询的开销即上文中的cost),即我们需要遍历每一个子查询对应的文档号。

  Lucene是如何处理的:

图4:

  BooleanQuery的开销最少可以是( numScores - minShouldMatch + 1)个子查询的开销和是怎么推算出来的:

图5:

点击查看大图

  在图5中,最后推导出BooleanQuery的总开销为 n-m+1个查询的开销,所以在Lucene中,它使用优先级队列head(大小为n-m+1)、tail(大小为m - 1)来存放子查询的信息(即查询原理(三)中的BulkScorerAndDoc),优先级队列的排序规则如下:

  当head中优先级最低的BulkScorerAndDoc的文档号不在遍历区间内,那么就可以跳过这个遍历区间,即使此时tail中还有其他的BulkScorerAndDoc。

  这里提供一个demo:https://github.com/LuXugang/Lucene-7.5.0/blob/master/LuceneDemo/src/main/java/lucene/query/BooleanQuerySHOULDNOTTEST.java,这个demo对应图3的内容,根据子查询4,我们会获得3个遍历区间(见查询原理(四)), 即[0,3)、[4,8)、[9,2147483647),但是实际只需要遍历[0,3)、[4,8),因为子查询1、子查询2会被放到head中,而这满足这两个查询的最大文档号为8,故不用处理[9,2147483647)的遍历区间,所以能降低时间复杂度,并且m的值越大,查询开销越小。

结语

  至此,BooleanQuery的其中一种组合模式介绍完毕,其他的组合方式在后面不会详细展开,只介绍文档合并的逻辑,比如文档号合并(SHOULD)文档号合并(MUST)

点击下载附件