[Feature Request] Multi-Field DocValues skip coordination

[sgup432]

Is your feature request related to a problem? Please describe

As of now, Lucene's DocValues fields maintain a multi-level skip list structure (DocValuesSkipper) that stores min/max value statistics for fixed-size blocks of documents (default 4,096 docs per block, grouped into 4 levels with 8x fanout). Range queries use this skip list to classify entire blocks as YES (all docs match), NO (no docs match), or MAYBE (need per-doc evaluation), avoiding expensive per-document value reads for YES and NO blocks.

Today, when a query ANDs multiple range filters on different fields (e.g., price:[10,50] AND rating:[4,5] AND date:[2024-01-01, 2024-12-31]), each field's skip list is evaluated independently. If the price skip list determines a block has no matching documents, the rating and date skip lists still read and evaluate their metadata for that same block, only for the conjunction(ConjunctionDISI) later on to discard it at the document level anyway.

Describe the solution you'd like

This proposal coordinates the skip list evaluation across fields. All fields' skip metadata is checked together at the block level, short-circuiting on the first field that says NO. When one field eliminates a block, the other fields skip it entirely, no skip reads, no per-doc evaluation.

This obviously will only operate if we have 2+ numeric range filters on different fields.

One way would be to rewrite and wrap multiple range queries and coordinator their skip evaluation via MultiFieldDocValuesRangeIterator. MultiFieldDocValuesRangeIterator that wraps the per-field skip iterators and advance them together ie when the lead field skips past a block, all other fields jump to the same position without reading their skip data for the skipped blocks.

Related component

Search:Performance

Describe alternatives you've considered

None at this point

Additional context

No response

[sgup432]

Tagging @jainankitk who helped me validate this idea.

Will open a PR soon. And benchmark

[sandeshkr419]

[Search Triage] Thanks @sgup432 for working on this, looking forward for the PR/POC. If it make sense to add this in Lucene, lets check that as well.

[sgup432]

Yeah this change is more suited to be added in lucene itself.

[kkhatua]

Nice !
Actually, if you are implementing, it might be worth providing the evaluation order as a hint as well. If the calling component has heuristics around selectivity, it will actually make it easier to evaluate and skip with the first field itself. An obvious example where this might not be needed is if one of the filter fields are already sorted, and evaluating that first makes sense irrespective of the hint.

[jainankitk]

Thanks @sgup432 for getting this started. After having some discussion with @mikemccand and giving it some more thought, this approach has few other merits that I did not think of earlier:

• Unlike BKD inverted index, this approach is very intra segment search friendly as the docId space can be easily partitioned across threads
• When search request expects sorted results, we should be able to tighten the query filter bounds (using priority queue approach) once we have enough to satisfy the size requirement
• Once we get into optimizing the on disk docValues format, in addition to combining the skip lists across field, we can consider, vector encoding the data block allowing faster access and processing