[SparseIndex] Support for Skiplist in aggregation queries

[animodak7]

Is your feature request related to a problem? Please describe

As part of enabling SkipList for doc_values in OpenSearch, we came across BKD uses in aggregation computations.

Comparing search query latency to get date histogram on @timestamp field of big5 dataset, with plain changes query took 3-5ms but with disabling tryPrecomputeAggregationForLeaf for dateHistogram and using skiplist latency went up to 2sec.

To set default experience on skiplist for users, we want to evaluate using skiplist instead of BDK while querying aggregation.

Describe the solution you'd like

Implement aggregations to make use skiplist.

Related component

Search

Describe alternatives you've considered

No response

Additional context

No response

[animodak7]

tagging @bharath-techie to review

[kkewwei]

@animodak7 Can you elaborate on the specific modifications you have in mind? The values of 1 Dim BKD leaf are sorted, which are very effective for range filtering. Not sure which code you will modify and if it makes sense to use skiplist instead of BDK.

[bharath-techie]

So when we look at primary sort field, already IndexSortSortedNumericDocValuesRangeQuery uses DocValues and performs binary search and is faster than the Points query. BKD index is not utilized during this query.

But we still need BKD even for primary sort field for optimizations done on DateHistogramAggregation and RangeAggregation

So since BKD consumes more space than sparse index, one idea is to replace BKD with skip index for primary sort fields.

We can do similar changes as present in https://github.com/apache/lucene/blob/d7b2afce1f32a2556e5aa0dd0596eb9be0374b82/lucene/core/src/java/org/apache/lucene/search/IndexSortSortedNumericDocValuesRangeQuery.java#L207 where the index sort optimization is used.

1. If performance is satisfactory , then we can use skip lists instead of BKD for primary sort fields.
2. If there is a performance gap, still this should be faster than just traversing through the entire doc values and will be useful for scenarios where user has disabled BKD index and enabled skip list for instance.

@msfroh @rishabhmaurya @mch2 do you have any thoughts ? Please feel free to add if I'm missing any details / scenarios.

[bowenlan-amzn]

@bharath-techie The BKD based optimization on date histogram and range aggregation has limitations like it doesn't support query other than match all or range query on the same aggregated field.
And it generally doesn't work well when the data is sparse, meaning the average documents of a range is low (that's why we see regression on pmc dataset, but it works well on big5 which is much denser, so you should verify on both dataset)
These limitations seem not a problem for doc values.

I'm curious about the main use case that we envision sparse doc values can help with. Assuming it can only be enabled if user set a primary sort field (correct if I'm wrong), then maybe the most common use case is the timestamp field of time series data? Or do we have other common use case in mind.

[bharath-techie]

Thanks @bowenlan-amzn for providing more information about the optimization. Yes I'm aware that there are specific conditions where we precompute and exit early but was not aware about the sparse case.

it can only be enabled if user set a primary sort field

Primary sort is the main use case but It can be enabled for any sort fields.
For background, the Lucene PR for this feature had testing done on primary sort field and secondary sort field. With primary sort field, it was already faster than BKD and with secondary sort field it was faster than doc values but still slower than BKD.

@animodak7 did benchmarks in primary sort field and found the performance to be close to IndexSortSortedNumericDocValuesRangeQuery. [ refer https://github.com//issues/17710 ]
but IndexSortSortedNumericDocValuesRangeQuery was faster.

So one thought process is that skipList's uses will come in optimizing aggregations and if we see good improvements / no regression , to start with - we can replace BKD with skip lists for primary sort field.

the most common use case is the timestamp field of time series data

This is definitely the top use case. And this comment summarizes other possible use cases.

[bharath-techie]

I see that Lucene has sparse index used as part of histogram collector already here.

I also see that the sparse index optimization is not as fast as BKD optimization in apache/lucene#14439 [ comment ref ]

Tagging @jainankitk to get more insights for this issue.