block-max WAND(一)(Lucene 8.4.0)

  从Lucene 8.0.0开始,Lucene新增了block-max WAND(Weak AND)算法,用于优化TopN的查询。该算法的引入可谓是一波三折,可以查看作者Adrien Grand对该算法的介绍:https://www.elastic.co/cn/blog/faster-retrieval-of-top-hits-in-elasticsearch-with-block-max-wand,下文中将围绕这篇博客展开介绍。

TopN查询(Lucene 7.5.0)

  我们先介绍下在Lucene 8.0.0之前,如果实现TopN查询,假设有以下的搜索条件:

图1:

  图1中,第57行、58行、59行描述了只要文档中至少包含一个域名为"author"、域值为"lily"或者"lucy"的信息,那么该文档就满足查询条件;第60行代码描述了,我们只需要根据文档打分返回Top3的结果。

  假设索引目录中一共有六篇文档,每篇文档的打分如下所示:

表一:

文档号Score1(lily)Score2(Lucy)文档打分值(总分)
0000
1549
26713
33811
4268
5336

  表一中,Score1描述的是域名为"author"、域值为"lily"对应的文档打分值,同理Score2,最终文档的打分值为Score1跟Score2的和值。

  结合图1跟表一可知,当我们处理到文档3,已经获得了Top3的搜索结果,即文档1、文档2、文档3。然而在Lucene 8.0.0之前,需要对所有满足图1的查询条件的文档进行打分,然后在Collector中使用根据score排序的优先级队列来维护Top3(见文章Collector(二))。

  通过上文的描述我们可以知道, 在查询过程中,一些打分值很低的文档号也被处理了,那有没有什么方式可以使得尽量跳过那些打分值较低的文档。

MAXSCORE

  在2012,Stefan Pohl介绍了MaxScore算法,该算法大意为:如果我们想查找一些文档,查询条件为这些文档中至少包含"elasticsearch"或者"kibana",并且根据文档打分值排序获得Top10。如果能知道根据elasticsearch关键字的文档打分最大值为3、根据kibana关键字的文档打分最大值为5,当Top10中的第10篇文档,即分数最低的那篇文档的的打分值为3时,那么在随后的处理中,我们就只需要处理包含"kibana"的文档集合(因为那些包含"elasticsearch"的文档肯定是进不了Top10的),并且只需要判断"elasticsearch"是否在这些文档集合中,如果在那么参与打分,并且可能更新Top10。

  实现该算法需要两个集合:

  随着更多的文档的被处理,TopN中最低的文档打分值如果变高了,那么对于第一个集合中的某些term,如果它们在文档中的打分最高值比TopN中的最小值小,就将它们从第一个集合中移除,并添加到第二个集合中,这样使得进一步减少待处理的文档数量。

  该算法在Lucene中无法直接应用,原因如下所示:

  上文中,Lucene团队不接受这种Stefan提出的issues主要是该算法需要在索引(index)阶段需要计算所有term在所有包含它的文档的文档打分值、需要变更已经生成的段文件。

  感兴趣的同学可以看这里的详细介绍:https://issues.apache.org/jira/browse/LUCENE-4100

WAND

  WAND(Weak AND)同样是一种可用于查询TopN的算法,然而该算法的实现同Lucene中的MinShouldMatchSum(minShouldMatch > 1)是相同的。我们简单的介绍下MinShouldMatchSum的实现方式,例如以下的查询条件将会使用MinShouldMatchSum:

图2:

  图2中的查询条件有三个子查询组成,描述的是:满足查询条件的文档中必须至少域名为"author",域值为"lily"、"lucy"、"good"中的任意2个(即代码64行设置的minShouldMatch为2)。

  MinShouldMatchSum算法实现中有三个核心的容器,分别是lead、head、tail,由于源码中关于这几个容器的注释,我怎么翻译都感觉不行😅,随意还是贴上原文朋友们自己品下:

图3:

  图3中,sub scorers中的每一个scorer可以简单的理解为满足某个子查询的文档信息,以图2为例,对于代码61行的子查询,他对应的scorer描述的是包含域名为"author"、域值为"lily"的文档信息。

  在继续介绍之前,我们先理解下源码中的这么一段注释:

图4:

  图4的源码中说到,如果有n个SHOULD查询(比如图2中就是3个SHOULD查询),其中minShouldMatch的值为m,那么这种查询的开销为 n - m + 1个scorer的遍历开销,即我们不需要遍历n个scorer的文档信息就可以获得查询结果。另外图4中的某个查询的cost描述的是满足该查询的文档数量。

  其推导思想说的是,包含n个子查询c1,c2,... cn且minShouldMatch为m的BooleanQuery,它可以转化为:

图5:

  图5的推导图中的最后一个步骤中的描述的是一个包含 m 个子查询且minShouldMatch为m的子BooleanQuery,那么很明显我们只要遍历任意1个子查询对应的文档集合即可。

  故最后得出我们只需要处理 n - m + 1个scorer。

  基于这个理论就设计出了上文中说到的head跟tail,我们先看下源码中如何定义这两个容器:

图6:

  我们不用关心DisiWrapper跟DisiPriorityQueue是什么,统称为容器即可。初始化head时的容器大小即 n - m + 1(scorers.size() - minShouldMatch + 1),而tail的大小为 m - 1,即剩余的scorer丢到tail中,head跟size中的元素数量和为n。

  结合上文介绍跟图3的注释就可以明白了,head中存放了用于遍历的scorers(注释中的in order to move quickly to the next candidate正说明了这点),而lead中存放了head中每一个scorer目前正在处理的相同的文档信息,并计算相同的文档信息的数量,如果该值大于等于minShouldMatch的值的话,说明文档满足查询条件。

  上文的描述只是粗略的介绍了MinShouldMatchSum,在后面的文章中会详细介绍。在本中我们只需要理解为什么要设计head、tail既可以。

block-max WAND

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

结语

  

点击下载附件