Improve clause ordering for multi-field DocValues range conjunctions
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
### Description
After #15954, SortedNumericDocValuesRangeQuery uses SkipBlockRangeIterator as its two-phase approximation. I see that `SkipBlockRangeIterator.cost()` currently returns `NO_MORE_DOCS`, which means when multiple DV range queries are combined in a FILTER conjunction, both DenseConjunctionBulkScorer and ConjunctionDISI will sort the clauses in arbitrary order as they all report the same cost?
I wonder if we should have a better way to do this. That is, we choose the most selective field(the one which can eliminate most docs) as the lead iterator, as this will allow us to skip most of the docs. This might help in performance depending on the number of fields in range conjunctions, higher the no. of fields, better ordering will give better performance.
The DocValuesSkipper already has metadata that could help estimate selectivity ie global minValue()/maxValue(), per-block min/max, and docCount(). Some ideas to do this:
- Use skipper.docCount() as cost. Though only differentiate b/w sparse vs dense fields.
- Estimate selectivity from queryRange / fieldRange * docCount. Rough but differentiates narrow vs wide queries
- Count NO blocks by walking the skip tree at scorer creation. This is more accurate, O(num_blocks) but requires extra work ahead.
Contributor guide
Research direction
Start with SortedNumericDocValuesRangeQuery and its SkipBlockRangeIterator.cost() implementation, then read DenseConjunctionBulkScorer and ConjunctionDISI to understand how clause costs determine ordering. Review the DocValuesSkipper metadata mentioned in the issue and compare the proposed selectivity approaches. Done means multi-field DocValues range conjunctions choose a more selective lead iterator and the performance trade-off is validated.
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
- Quiet
- Clarity
- Needs clarification
- Newbie friendliness
- 45/100