...
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
...
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.
Global Shared Priority Queue
The operation flow of global shared priority queue is as below:
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.
...
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.
...