This document entails the design of concurrent early termination when the index is sorted by either relevance or a set of features.
There are three different use cases, each with a separate solution. User needs to check and choose the relevant solution for his/her use case.
Solution Description
This section contains the proposed solutions and their detailed descriptions.
Note that these solutions are not mutually exclusive — all of them need to be present in order for different use cases to be executed correctly and the performance be consistent even in case of different query configurations.
Shared Hit count Based Early Termination
Targeted Use case: When number of hits collected > number of hits requested.
We introduce a global shared hit count which is updated globally by all collectors and serves as the golden benchmark of how many hits have been globally collected. In contrast to today, when all collectors collect N hits independently, we will now collect N hits globally. Post collection of N hits globally, hit filtering will start and only competitive hits will make their way in the priority queues.
Pro: Point accurate hit counting with minimum synchronization overhead
Con: Only covers the case when the total number of hits collected exceeds the number of hits requested
Current Status: Committed in upstream: https://github.com/apache/lucene-solr/commit/4d82665625a168747f31441a8478abf3778e5649
Shared Global Priority Queue Based Early Termination
Targeted Use case: When actual number of hits <= number of hits requested and precise counting is required
This solution is based on top of the first solution. The proposed solution in this scenario is a multi phase solution:
In the first phase, all collectors will collect hits in their thread local priority queue and update the global shared hit count. Post the collection of requested number of hits, a global shared priority queue will be allocated. Each collector will then publish their hits in the global priority queue, thus setting the bottom value of the global priority queue. Once the collector is done, it will then start filtering further hits with the bottom of the global priority queue.
The point of synchronization is at the update of the global priority queue and the corresponding bottom feature value.
An important point to note here is that a regular CollectorManager will perform a merge step post completion of collection. However, in this scenario, that is not required since the global priority queue can be used to supply the top hits post completion of collection for all collectors.
Pro: Point accurate early termination for all cases, thus not collecting any redundant hits
Con: Global shared priority queue can become a bottleneck during filtering phase as it requires an exclusive lock.
Current Status: PR raised: https://github.com/apache/lucene-solr/pull/854
Global Shared Bottom Score/Feature Based Early Termination
Targeted Use case: When actual number of hits <= number of hits requested with some leverage of a few extra hits collected
In this scenario, each collector will collect documents until globally, number of hits requested are collected. Post that, each collector will publish the minimal value of its hit queue, and the worst of all will become the global minimum. Any further document will be filtered against the global worst hit score as the parameter.
The score mentioned here can be either relevance in case the index is sorted by relevance, or features if sorted by such.
Pro: Requires lesser amount of synchronization
Con: Can count redundant hits in some scenarios (such as when data is skewed to a large extent), thus performs sub optimally as compared to shared priority queue based early termination.
Current Status: JIRA: LUCENE-8974 - Getting issue details... STATUS
Trade off Between solutions 2 and 3
As described, solutions 2 and 3 seem to be tackling the same set of use cases. However, a key differentiator is the way hits are filtered, and subsequently the requirement for coordination and consistency across all collectors. Solution 2 allows precise, to the point accurate counting at the cost of higher synchronization at global priority queue level whereas solution 3 allows a few extra hits (dependent on data distribution) at the advantage of lesser synchronization since each thread maintains their thread local priority queue throughout the execution of the search.