在上一篇文章的结尾，我们总结了使用NumericDocValues优化查询TopN的原理：假设查询TopN的排序规则为按照正排值从小大小的顺序，即正排值越小，优先级越高。故在开启优化后，当收集器收到一个文档号，先根据文档号从正排索引中拿到正排值，在满足某些条件后，根据正排值，通过查询BKD树获取所有小于该正排值的文档集合，该文档集合用于生成一个新的迭代器。随后每次传入到收集器的文档号将会从新的迭代器中获取，达到所谓的skip non-competitive documents的效果。
上文的描述中，我们需要对两个问题进一步展开介绍：
- 问题一：满足什么条件后会生成一个新的迭代器
- 问题二：如何生成一个新的迭代器
问题一：满足什么条件后会生成一个新的迭代器
满足的条件很苛刻，本文中只挑选出部分条件，且这些条件必须同时满足。完整的内容可以阅读源码：NumericComparator类中的updateCompetitiveIterator()方法。
条件一：Collector已经收集了N个文档号
只有在收集器收集了N个文档号后才会考虑是否需要生成一个新的迭代器。对应代码中通过判断用于收集文档信息的优先级队列queue是否full来判断。
条件二：是否允许使用PointValues来优化
在上一文章中说过，开启优化的其中一点是需要显示指定开启优化。在显示指定后，对应代码中一个布尔类型的enableSkipping会被置为true。
条件三：Collector是否已经处理了totalHitsThreshold个文档号
totalHitsThreshold是创建实现TopN的Collector（TopFieldCollector类的create方法）时，允许用户指定的一个int类型参数。totalHitsThreshold描述的是Collector至少处理了totalHitsThreshold个文档号后才会开启优化。本文介绍的优化是其中一种。另外还有基于IndexSort优化会在后续的文章中介绍。
在Lucene 7.2.0之后，查询TopN首次引入了允许提前结束Collector收集文档号的优化（见文章Collector（三）），即在已经收集到了全局最具competitive的N个文档号，Collector不用再处理剩余的文档号。这个优化会导致一个用户体验的问题，有些用户使用的场景需要记录hit count ，即命中的文档数量（满足用户设置的查询条件的文档数量），提前退出会导致没法将所有满足查询条件的文档号传入到Collector，使得Collector中的totalHits（传入到Collector的文档号数量）的值总是小于等于hit count的，最终使得用户无法通过Collector获得精确的（accurate）hit count。
所以在这次优化中同时增加了一个用户可以配置的布尔参数trackTotalHits，如果参数为true，那么当Collector已经收集到了TopN的文档号，并且即使这N个文档号已经是全局最具competitive的集合，Collector仍然继续收集其他的文档号（只统计totalHits），最终使得totalHits的数量能等于hit count。
随后在LUCENE-8060讨论下，最终在Lucene8.0.0之后，用int类型的参数totalHitsThreshold替换了trackTotalHits，使得既能让用户获得想要的hit count，又能在开启优化后，减少一定的Collector中处理的文档号数量。当totalHitsThreshold的值大于等于满足查询条件的文档数量时，其相当于trackTotalHits置为true。
条件四：是否超过迭代器的更新次数
在Collector收集文档号期间，当达到条件三或者达到条件一并且当前需要更新queue中堆顶元素时，Collector会尝试更新迭代器。每次尝试更新迭代器会使用一个int类型的updateCounter统计尝试更新的次数。如果满足下列的条件，那么不会生成一个新的迭代器：
1 | updateCounter > 256 && (updateCounter & 0x1f) != 0x1f |
条件五：估算新的迭代器中的文档号数量是否低于阈值
在上文四个条件都满足的情况下，才需要考虑最后一个条件。从条件五中可知我们需要了解两个内容：如何估算新的迭代器中的文档号数量、如何设定阈值。
如何估算新的迭代器中的文档号数量
如果当前的排序规则是从小到大的升序，那么条件一中提到的queue中的堆顶元素，即堆中竞争力最低的（weakest competitive ）的正排值，它就是堆中的最大值，我们称之为maxValueAsBytes。估算的逻辑为从BKD树中统计出比maxValueAsBytes小的正排值的数量estimatedNumberOfMatches，注意的是estimatedNumberOfMatches是一个估算值。
统计estimatedNumberOfMatches的逻辑就是深度遍历BKD树，其详细遍历过程见文章索引文件的读取（一）之dim&&dii的介绍，我们通过一个例子简单的概述下。
例子
BKD树中存放了[1, 100]共100个正排值，其中maxValueAsBytes的值为60。
图1：
访问根节点
maxValueAsBytes与根节点的关系是CELL_CROSSES_QUERY（见文章索引文件的读取（一）之dim&&dii的介绍），那么依次访问根节点的左右子节点：节点一、节点八。
访问节点一
由于maxValueAsBytes比节点一的最大值还要大，即maxValueAsBytes与节点一的关系是CELL_INSIDE_QUERY。此时可以累加计算estimatedNumberOfMatches的值，该值为节点三、节点四、节点六、节点七四个叶子节点中点数据的数量总和。在源码中，默认每个子节点中的点数据数量最大值为512，故计算方式为：512 * 叶子节点数量。
访问节点八
由于节点一以及它所有子节点都处理结束，故下一个访问节点为节点八。
maxValueAsBytes与节点八的关系是CELL_CROSSES_QUERY，那么将依次访问节点八的左右子节点：节点九、节点十二。
访问节点九
maxValueAsBytes与节点九的关系是CELL_CROSSES_QUERY，那么将以此访问节点十跟节点十一。
访问节点十
maxValueAsBytes与节点十的关系是CELL_CROSSES_QUERY，注意的是由于节点十是叶子节点，在源码中，不会通过遍历叶子节点中的点数据来获得一个准确的estimatedNumberOfMatches，其计算方式为叶子节点中的默认点数据数量最大值的一半，即(512 + 1) / 2。
访问节点十一、十二
maxValueAsBytes与节点十一、节点十二的关系是CELL_OUTSIDE_QUERY，即maxValueAsBytes比节点十一、节点十二的最小值还要小，故直接返回。
最终，累加在各个节点获得的estimatedNumberOfMatches作为新的迭代器中的文档号数量的估算值。
如何设定阈值
阈值threshold的计算基于当前迭代器的开销值iteratorCost（见文章迭代器中关于开销cost的介绍），如果获取了新的迭代器，那么iteratorCost会被更新为新的迭代器的开销值：
1 | final long threshold = iteratorCost >>> 3; |
如果estimatedNumberOfMatches的值大于等于，那么将不会更新迭代器。
问题二：如何生成一个新的迭代器
当问题一中所有条件都满足后，那么随后将根据maxValueAsBytes再次遍历BDK树，这次的遍历将精确的获取所有大于maxValueAsBytes的正排值对应的文档号。在遍历的过程中，使用文档号收集器获取一个文档集合，并用这个集合生成一个新的迭代器。随后下一次传给Collector收集器的文档号将会从新的迭代器中获取。
一些其他细节
另外使用了一个int类型的maxDocVisited记录了Collector目前处理过的最大文档号，使得新的迭代器不会收集Collector已经处理过的文档号。
结语
无
点击下载附件