执行段的合并(五)
Lu Xugang Lv6

  本文承接执行段的合并(四),继续介绍执行段的合并的剩余的流程,下面先给出执行段的合并的流程图:

图1:

点击查看大图

提交合并

MergeState

在文章执行段的合并(四)中我们说到,生成MergeState的过程中完成了几个任务,根据IndexWriter是否设置了IndexSort(见文章索引文件之si中关于IndexSort的介绍)可以将任务划分为如下两类::

  • 设置了IndexSort
    • 任务一:对每一个待合并的段进行段内排序
    • 任务二:对合并后的新段进行段内排序
    • 任务三:获得所有待合并的段的被删除的文档号与段内真正的文档号的映射DocMap[ ]
  • 未设置IndexSort
    • 任务三:获得所有待合并的段的被删除的文档号与段内真正的文档号的映射DocMap[ ]

任务一:对每一个待合并的段进行段内排序

  执行任务一的目的其实是为了任务二准备的,因为只有每一个待合并的段是段内有序的,才能实现将这些段合并为一个段内有序的新段。

  我们先通过一个例子来介绍段内排序对搜索结果的影响:

图2:

图3:

  图2中描述了IndexWriter的段内排序规则,定义了两个排序规则:

  • sortField1:根据域名为"age"的域值进行从小到大排序
  • sortField2:根据域名为"label"的域值按照字典序排序

  图2中的第45行代码,定义SortField[]数组时,sortField1相比sortField2有更小的数组下标,故总的排序规则为先按照sortField1进行排序,如果无法通过sortField1比较出两篇文档的先后关系,那么再使用sortField2来区分,如果两个排序规则都无法区分文档的先后关系,那么根据文档被添加的先后顺序来判断,即图3中 文档0、文档1的编号。

图4:

图5:

  图3中的文档都被添加到索引之后会生成一个段,我们通过图4的代码来打印该段的文档信息,即图5的内容,可以看出当使用了IndexSort后,段内的文档按照图2中的排序规则正确的排序了,通过图5我们可以知道下面的内容:

  • docId为0的文档,它对应图3中的文档4,由于这篇文档没有"age"、“lable"的DocValues域,故它被认为是"最小的”,即排在最前面
  • docId为3、docId为4的文档,它们分别对应图3中的文档1跟文档3,可以看出它们是先按照sortField1而不是sortField2进行排序,否则文档3根据域名"lable"的域值"a",它应该比文档1"较小"
  • docId为2,docId为3的文档,它们分别对应图3中的文档2跟文档1,可以看出这两篇文档根据sortField1无法区分大小关系,再根据sortField2能比较出文档2"较小"
  • dociId为4,docId为5的文档,它们分别对应图3中的文档3,文档5,可以看出这两篇文档根据sortField1跟sortField2都无法区分大小关系,所以只能根据文档被添加的先后顺序来判断,文档3先被添加,所以它"较小"

  如果我们不设置IndexSort,图4的打印结果如下所示:

图6:

  从图6中可以看出,如果不设置IndexSort,那么段内的文档顺序就是文档被添加的顺序。

  另外在设置了IndexSort后,Collector的collect(int doc)方法依次收到的文档号也是排序的,故如果业务中对查询性能有较高要求,并且返回的结果有固定的排序规则的要求,那么我们可以将这个排序规则通过IndexSort来实现,将排序的开销扔到索引阶段。

  上文的例子demo可以点这里查看:https://github.com/LuXugang/Lucene-7.5.0/blob/master/LuceneDemo/src/main/java/lucene/docValues/SegmentInnerSort.java

  在索引阶段通过IndexSort进行段内排序,即对段内的文档进行排序,实际上不是真正的改变文档在段中的位置,因为在性能上来讲是不可能的,段内排序的实质是生成一个映射,下文中将详细的介绍段内排序的过程。

  在索引阶段,什么时候进行段内排序:

  • flush生成一个段的过程中进行段内排序,具体的见文章文档提交之flush(三)中流程点将DWPT中收集的索引信息生成一个段newSegment的流程图的介绍。
段内排序流程图

  为了便于描述,图7中的流程图是按照从小到大的顺序进行排序。

图7:

段内文档

图8:

  待排序的对象是段内所有的文档。

判断段内文档是否已经有序

图9:

  从段内的第二篇文档(因为要跟上一篇文档进行比较)开始,根据IndexWriter提供的段内排序规则比较当前文档是否小于上一篇文档,如果所有的文档都满足这个关系,说明段内已经有序,那么直接退出即可,否则只要有某任意两篇文档不满足上述关系,说明段内不是按照IndexWriter提供的段内排序规则有序的,故需要进行排序。

生成映射newToOld

图10:

  如果待排序的文档没有按照IndexWriter提供的段内排序规则有序,那么需要进行排序,并且这里使用TimSort进行排序,本篇文章中不会对介绍TimSort的逻辑,我们只关心排序结束后,会生成一个映射newToOld,当然在源码中它是一个经过压缩处理的对象,为了便于介绍,我们可以简单的理解为newToOld是一个数组,对于图3中的例子,它对应的newToOld数组如下所示:

图11:

  new指的是数组下标值,old指的是数组元素,newToOld数组实现了new到old的映射,所以段内排序并没有真正的去"移动"文档。如果图3中的文档都满足搜索条件,那么Collector的collect(int doc)方法依次收到的文档号即图11中的docId。

  另外,如果阅读过文档的增删改的系列文章,图11中的数组元素,即文档编号,它是根据文档被添加到DWPT(见文档的增删改(二))中的顺序赋值的,即文章文档的增删改(四)中的numDocsInRAM。

生成映射oldToNew

图12:

  根据映射newToOld生成一个相反的映射,如下所示:

图13:

任务二:对合并后的新段进行段内排序

  该任务的逻辑相对复杂,基于篇幅,在下一篇文档中展开介绍。

结语

  无

点击下载附件

 Comments