Prune non competitive docs in NumericComparator by making use of numHits to collect from Collector
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
### Description
TopFieldCollector, where the number of hits to collect is known before hand, can we make use of it to only collect most competitive hits collected by NumericCollector? Competitive iterator in NumericCollector makes use of BKD (when defined criteria is met) and will traverse the points in ascending order and if the query sort order is ascending too it works pretty well, as most competitive hits would be collected first and rest of them can be discarded fast. When query sort order is descending, it can cause priority queue churning and read amplification because of doc values retrieval because of collection of non-competitive in the beginning, as most competitive docs are towards the end of BKD.
If we know how many hits we need to collect, can we directly move to the right node of the tree (in a cheaper manner) and start collecting competitive docs thereafter?
This could be helpful for the cases where segment is big and numHits << docs in segment (matching query) as it could prune large set of non competitive docs.
BKD and numeric comparator code is new to me and I might be missing few critical cases, but here is my best effort to implement something closest - https://github.com/rishabhmaurya/lucene/pull/2
Contributor guide
Research direction
Start by reading the TopFieldCollector, NumericCollector, and NumericComparator entry points, then study the BKD traversal described in the issue and compare the external pull request. Establish the safe cases for using numHits to prune non-competitive hits; the work is done when behavior is validated for both ascending and descending sort orders.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- search
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 30/100