Lucene BooleanQuery相关算法

BooleanQuery对两种不同查询场景执行不同的算法：

场景1：

所有的子句都必须满足，而且所有的子句里没有嵌套BooleanQuery。

例：

a    AND    b    AND    c

上面语句表示要同时包含a，b，c三个字符(词元)的文档，假如现在索引里包含a的文档有4，6，8；b的文档有：2，4，6；c的文档有：3，4，5，这个语句就是找出编号为4的这个文档。

注：在倒排索引里存储的包含某个词元的文档列表都是从小到大排列的。

初始状态如下：

a	b	c
-> 4	-> 2	-> 3
6	4	4
8	6	5

指针表示当前遍历到哪个文档

第一步：按照每个词元文档列表的第一个文档对词元排序。排序以后的状态如下：

b	c	a
-> 2	-> 3	-> 4
4	4	6
6	5	8

第二步：判断第一个词元(b)的当前遍历文档(2)是否小于最后一个词元(a)的当前遍历文档(4)。如果小于，则表示第一个词元的当前遍历文档不是符合的文档，如果是符合的最后一个词元的当前文档应该和第一个词元的相同。

第三步：第一个词元文档位置(2)跳转到最后一个词元的当前遍历的文档(4)，跳转以后的状态如下：

b	c	a
2	-> 3	-> 4
-> 4	4	6
6	5	8

第四步：将第一个词元放到词元列表最后，重置位置后状态如下：

c	a	b
-> 3	-> 4	2
4	6	-> 4
5	8	6

重复第二、三、四步，直到找到第一个词元的当前遍历文档ID和最后一个词元的相同，则这个文档就是符合查询要求的文档。

这种场景的代码实现在ConjunctionScorer类里，主要的代码逻辑在方法doNext里：

 while (more && first().doc() < last().doc()) { // find doc w/ all clauses

      more = first().skipTo(last().doc());      // skip first upto last

      scorers.addLast(scorers.removeFirst());   // move first to last

    }

这里会不断的判断第一个词元的当前文档是否小于最后一个词元的当前文档，如果不相同，则第一个词元的文档跳转到最后一个词元的文档位置。

排序是在第一次进去的时候在init方法里做的。

场景2：

除了上面第一种场景就是第二种场景，第一种场景因为排序的原因，不需要遍历所有的文档，第二种场景需要遍历所有的文档。

第二种场景的实现在BooleanScorer类里，

每次往BooleanScorer类里添加一个子句，会记录当前这个子句的序号和这个子句的定义，是必须满足还是必须不满足。这个数据记录在requiredMask和prohibitedMask中，这两个数是int类型，里面每一位都代表一个子句。requiredMask记录了哪些子句必须满足；prohibitedMask记录了哪些子句必须不能满足。比如一共有5个子句，1、3、5必须满足，2、4必须不能满足，则requiredMask二进制的值为： 10101。prohibitedMask的值为: 01010。

当调用next的时候会批量从各子句中取出符合这些子句的部分文档(文档ID批范围，1024为一批)到内存中的一个缓存BucketTabke里，在这个缓存里会根据文档ID进行聚合(Bucket)，每个文档ID都有个满足哪些子句的属性bits。

然后遍历这些文档，那些bits里包含所有必须符合子句且不包含所有必须排查子句的文档是最终符合的文档。这个判断是通过bits和上面requiredMask和prohibitedMask做位运算实现的。

if ((current.bits & prohibitedMask) == 0 &&

            (current.bits & requiredMask) == requiredMask) {

          return true;

}

巴特西

Lucene BooleanQuery相关算法

最新文章

热门文章