IndexSortSortedNumericDocValuesRangeQuery(一)(Lucene 9.0.0)

  我们先通过IndexSortSortedNumericDocValuesRangeQuery类的注释了解下这个Query。

图1:

  图1中红框标注的注释说到,范围查询可以通过利用Index Sort来提高查询效率。如果查询条件的域field正好是用于段内排序的域,那么就可以通过二分法找到满足查询条件的两个文档号。这两个文档号分别作为一个区间的上下界,满足查询条件的文档号肯定都在这个区间内。

  对于红框注释有两个细节需要注意:

  下文中,我们将会这两个注意的细节作出详细的介绍。

  图1中蓝框标注的注释说到,只有同时满足下面的条件才能实现这种优化执行策略(optimized execution strategy):

  条件三的限制换个说话就是:一篇文档中要么不包含SortedNumericDocValues或者NumericDocValues,要么只能包含一个。具体原因在下文中说明。

  如果上述三个条件不同时满足,那么就无法使用这个优化执行策略,这次查询就会交给fallbackQuery(下文会介绍)去执行。

  图1中灰框标注的注释说道,fallbackQuery的查询条件必须跟IndexSortSortedNumericDocValuesRangeQuery一致,返回的结果必须是相同的文档集合并且每篇文档的分数是固定的。

  因为IndexSortSortedNumericDocValuesRangeQuery的查询逻辑是先尝试用IndexSort机制进行查询,如果无法同时满足上文中说道的三个条件,那么就将这次查询委托(delegate)给fallbackQuery。

  灰框标注的例子中可以看出,代码66行的LongPoint.newRangeQuery即fallbackQuery,它的查询条件跟代码67行的IndexSortSortedNumericDocValuesRangeQuery是一样的。

  从这个例子也可以看出,fallbackQuery跟IndexSortSortedNumericDocValuesRangeQuery的查询条件保持一致需要使用者自己来保证,意味着用户想要自己编写一个效率较高的数值范围查询有较高的学习成本,他至少要了解并且在索引阶段写入SortedNumericDocValues或者NumericDocValues,还要了解各种数值类型范围查询,比如IndexOrDocValuesQueryPointRangeQuery(一)等等。所以社区已经开始着手开发一些"sugar"域跟Query(见LUCENE-10162),使得用户能简单透明的使用数值类型的范围查询,让Lucene来帮助用户生成一个高效的Query。

  我们看下Elasticsearch 8.0的NumberFieldMapper类中是如何生成一个高效的数值类型范围查询Query的,以Mapping类型为int的字段为例:

图2:

  图2描述了生成一个用于int类型的字段的范围查询的过程:首先通过IntPoint.newRangeQuery生成一个PointRangeQuery,我们称之为indexQuery;如果该字段开启了DocValues,那么通过SortedNumericDocValuesField.newSlowRangeQuery生成一个DocValues的范围查询,我们称之为dvQuery, 然后将indexQuery跟dvQuery封装为一个IndexOrDocValuesQuery;最后如果分片的索引根据查询域排序了,那么进一步将IndexOrDocValuesQuery封装为IndexSortSortedNumericDocValuesRangeQuery,此时IndexOrDocValuesQuery即上文中的fallbackQuery。

  在文章IndexOrDocValuesQuery中详细的介绍了这个Query,本文中我们简单的提一下:IndexOrDocValuesQuery既利用了倒排中根据term快速获取满足查询条件的文档号集合能力,又利用了正排中根据文档号能快速check是否存在某个term的能力。使得IndexOrDocValuesQuery不管作为leader iterator还是follow iterator都能获得不错的读取性能。

  回到图2中构造过程,的确需要相当大的学习成本才能构造成一个高效的Query。LUCENE-10162的目标在于期望用户通过编写类似IntField.NumericRangeQuery(String field, long lowerValue, long upperValue)这种方式就可以获得图2中的Query。

利用IndexSort实现高效查询

  不管是哪种Query的实现,其需要解决的最重要的核心问题是这个Query如何提供一个迭代器DocIdSetIterator,迭代器中包含了满足查询条件的文档号集合,以及定义了读取这些文档号的方式。查询性能取决于迭代器的实现方式。

BoundedDocSetIdIterator

  BoundedDocSetIdIterator即在利用了IndexSort后,IndexSortSortedNumericDocValuesRangeQuery实现的迭代器,注意的是这个迭代器的名字有书写错误typo,应该是BoundedDocIdSetIterator,也许会在这个LUCENE-10458合并后修正。

  我们看下这个迭代器中包含的信息,即该类的成员变量:

图3:

  图3中的firstDoc、lastDoc中用来描述一个左闭右开的文档号集合的区间,这个区间内至少包含了满足查询条件的所有文档号。对于firstDoc跟lastDoc是如何计算的,我们将在下一篇文章中展开。

为什么说BoundedDocSetIdIterator中至少包含了满足查询条件的所有文档号

  因为某些文档中虽然不包含查询条件对应的域的信息,但是Lucene会给这篇文档添加一个默认值来参与段内的文档排序。该默认值就是MissingValue。这些被设置了MissingValue的文档号就有可能被统计到迭代器中。

例子

我们通过一个例子介绍下上述的问题,demo地址:https://github.com/LuXugang/Lucene-7.5.0/blob/master/LuceneDemo9.0.0/src/main/java/facet/MissingValueTest.java

图4:

图5:

图6:

  图4中,我们定义了一个IndexSortSortedNumericDocValuesRangeQuery的范围查询,其中代码66、67定义了查询条件的上下界分别为 1, 100,代码72行定义了查询条件的域名为"number",显然,只有文档1跟文档2中包含"number"域,并且其域值满足查询条件,而文档0中不包含"number"域的信息,所以在图6中,满足查询条件的文档号分别是文档1跟文档2。

  图4的例子满足了利用IndexSort的三个条件,故IndexSortSortedNumericDocValuesRangeQuery会生成图5中的BoundedDocSetIdIterator迭代器。但是通过断点可以看到firstDoc跟lastDoc组成的左闭右开的区间中的文档号集合包含了文档0、文档1、文档2。这是因为在图4中我们定义了MissingValue的值为3,所以文档0也被BoundedDocSetIdIterator收集了(其被收集的原因也会在下一篇文章中展开介绍)。

  如果图4中不设置MissingValue,那么BoundedDocSetIdIterator的信息是这样的:

图7:

图8:

  由于在设置了MissingValue后,BoundedDocSetIdIterator中可能会包含不满足查询条件的文档号,所以在BoundedDocSetIdIterator中,如图8所示,它还包含一个成员变量delegate,它是上文中fallbackQuery对应的迭代器。因为fallbackQuery的迭代器中包含的文档号肯定是满足查询条件的,所以在读取BoundedDocSetIdIterator的文档号时,每次都会去delegate中检查是否存在这个文档号,来保证返回数据的准确性。

结语

  剩余内容将在下一篇文章中展开。

点击下载附件