查询原理（四）
Lu Xugang Lv6
  2019-08-27 00:00:00 2019-08-27 00:00   2023-10-08 22:09:07      2.3k Words  

  本文承接查询原理（三），继续介绍查询原理。

查询原理流程图

图1：

点击查看大图

  图2、图3是BooleanQuery的查询实例，在查询原理（三）中我们根据这个例子介绍了生成BulkScorer的流程点，本篇文章根据这个例子，继续介绍图1中剩余的流程点。

图2：

图3：

Collector处理查询结果

  在查询原理（三）文章中的生成BulkScorer流程点，我们获得了每一个子查询对应的文档号跟词频，见图4，结合查询原理（二）文章中的生成Weight流程点，我们就可以在当前流程点获得满足查询条件（图3）的文档集合及对应的文档打分值。

图4：

Collector处理查询结果的流程图

图5：

是否还有遍历区间？

图6：

  图4中的子查询4，该查询对应的文档号集合不是用户期望返回的，那么可以根据这些文档号划分出多个左闭右开的遍历区间。

  满足子查询4条件的文档号集合为3、8，故可以划分出3个遍历区间：

  • [0，3)
  • [4，8)
  • [9，2147483647)：2147483647即 Integer.MAX_VALUE

  随后从每个遍历区间中找到满足子查询1、子查询2、子查询3且minShouldMatch为2的文档号，minShouldMatch通过图3中的builder.setMinimumNumberShouldMatch方法设置，描述的是用户期望的文档必须至少满足子查询1、子查询2、子查询3中的任意两个（minShouldMatch）的查询条件。

  为什么要使用遍历区间：

  • 降低时间复杂度：通过左闭右开实现过滤子查询4中的文档号（时间复杂度O(n)），否则当我们找出根据子查询1、子查询2、子查询3且minShouldMatch为2文档号集合后，每一个文档号都要判断是否满足子查询4的条件（时间复杂度O(n*m)），其中n跟m都为满足每一个子查询条件的文档数量，在图4中的例子中，n值为17（6 + 4 + 7，3个docDeltaBuffer数组的元素个数的和值），m值为2

处理子查询的所有文档号

图7：

  该流程处理子查询的所有文档号，先看下Bucket数组，该数组的数组下标用来描述文档号，数组元素是Bucket对象，它用来记录该文档的打分值跟满足子查询条件的查询个数，Bucket类如下所示：

1
2
3
4
static class Bucket {
    double score;
    int freq;
}
  • score：文档打分值
  • freq：满足子查询条件的查询个数
freq

  我们先说下freq，freq描述的是满足子查询条件的查询个数，例如图2中的文档8（文档号为8），因为文档号8中包含了"h"、“f”、“a”，所以它满足子查询1、子查询2、子查询3的三个查询条件，故文档号8对应的Bucket对象的freq值为3。

score

  图8为BM25模型的理论打分公式：

图8：

  图17源自于<<这就是搜索引擎>>，作者：张俊林。

  图9为在Lucene7.5.0版本中BM25模型的具体实现BM25Similarity的公式：

图9：

  从图9的公式可以看出，一篇文档的打分值是一个累加值，累加的过程即更新Bucket数组的流程，如果一篇文档满足多个子查询的条件，那么该文档的打分值是每个子查询对这篇文档打分的和值。

  例如图2中的文档0，该文档包含了两种term，分别是 “a”，“h”，故文档0满足图3中的两个子查询的条件，分别是子查询1、子查询3，所以文档0的打分值是两个查询对这篇文档打分的和值，最后将这个和值添加到Bucket数组的数组下标为0（因为文档0的文档号是0）的数组元素Bucket对象中，该对象的freq的值同理会被赋值为2。

BM25Similarity打分公式

图10：

  • Idf、boost、avgdl、docCount、docFreq：这些值在查询原理（二）中计算SimWeight时获得，不赘述
  • freq：子查询条件中的域值在文档（正在计算打分的文档）中的词频，即图4中的freqBuffer数组的数组元素
  • k1k_1、b：BM25模型的两个调节因子，这两个值都是经验参数，默认值为k1k_1 = 1.2、b = 0.75。k1k_1值用来控制非线性的词频标准化（non-linear term frequency normalization）对打分的影响，b值用来控制文档长度对打分的影响
  • norm：该值描述的是文档长度对打分的影响，满足同一种查询的多篇文档， 会因为norm值的不同而影响打分值

图11：

  图11中，横坐标为文档长度值，纵坐标为dl，由于数据跨度太大，无法看出文档长度值较小的区间的趋势图，故图12给出的是文档长度值在[1，100]区间的映射图

图12：

  图13中，文档长度值在[1，50]区间的映射图，能进一步看出文档长度值小于等于40时，dl正比于文档长度值

图13：

  图10中的normValue根据文档号从索引文件.nvd中获得，图14中用红框标识了一篇文档的文档号及其对应的normValue。

图14：

处理Bucket数组

图15：

  处理Buck数组的过程就是找出所有满足图3中minShouldMatch的文档，然后分别将文档号交给Collector收集器处理

  某个遍历区间内的生成Bucket数组的过程在文档号合并（SHOULD）的文章中已经介绍，不过注意的是，在那篇文档中，没有考虑文档的打分值，故Bucket数组只介绍了freq。由于那篇中没有类似图3中的子查询4，所以遍历区间为[0，2147483647]。

  对于本篇文章中图2、图3的例子，在遍历区间为[0，3)对应生成的Bucket数组如下所示，相比较文档号合并（SHOULD）中的内容，我们增加每篇文档的打分值，列出遍历区间为[0，3)的Bucket数组：

遍历区间[0，3)

图16：

  在图16中，文档0跟文档2的freq 大于等于minShouldMatch（2），故这两篇文档满足图3中的查询要求。

结语

  至此，我们介绍了单线程下的查询原理的所有流程点，但还有一个很重要的逻辑没有介绍，那就是在图5的是否还有未处理的子查询流程点，我们并没有介绍在还有未处理的子查询的情况下，如何选择哪个子查询进行处理，这个逻辑实际是个优化的过程，可能可以减少遍历区间的处理，以图2、图3为例，尽管根据子查询4，我们得出3个遍历区间，实际上我们只要处理[0，3)、[4，8)这两个逻辑区间，至于原因会在下一篇文档中展开。

  图2.、图3的demo点击这里：https://github.com/LuXugang/Lucene-7.5.0/blob/master/LuceneDemo/src/main/java/lucene/query/BooleanQuerySHOULDNOTTEST.java。

  另外对于多线程的情况，图1中的合并查询结果流程也留到下一篇文章中介绍。

点击下载附件

 Comments
  1. 1. 查询原理流程图
    1. 1.1. Collector处理查询结果
      1. 1.1.1. Collector处理查询结果的流程图
        1. 1.1.1.1. 是否还有遍历区间？
        2. 1.1.1.2. 处理子查询的所有文档号
          1. 1.1.1.2.1. freq
          2. 1.1.1.2.2. score
            1. 1.1.1.2.2.1. BM25Similarity打分公式
        3. 1.1.1.3. 处理Bucket数组
          1. 1.1.1.3.1. 遍历区间[0，3)
  2. 2. 结语