[Feature Request] Add segment sorter to `ShuffleForcedMergePolicy` instead of name-based segment sorting

[prudhvigodithi]

Is your feature request related to a problem? Please describe

Currently, when OpenSearch performs a forced merge (ex _forcemerge?max_num_segments=1), it wraps the underlying merge policy with ShuffleForcedMergePolicy.

From my understanding the ShuffleForcedMergePolicy – a special merge policy that interleaves documents from the oldest and newest segments during the merge. “Interleaves” means mixing things together by alternating them. By shuffling documents from old and new segments, the ShuffleForcedMergePolicy breaks the ordering pattern, enabling more uniform distribution of data during force merge.

Now for time-series index and using LogByteSizeMergePolicy where merges always combine adjacent segments and assign the result a new Lucene name (via a global counter), but that name doesn’t reflect the segment’s true timestamp range. Because the current shuffle logic sorts segments by these Lucene names (info.name), the interleaving can drift from real time order.

Coming from #17404 seen a variance with desc_sort_timestamp after force merge. After some investigation the main cause (#17404 (comment)) is Document ID Reassignment after the force merge which is coming from ShuffleForcedMergePolicy. More tests done here #17737 (comment).

A high level example with _6 (Jan 1–4), _8 (Jan 4–6), _5 (Jan 6–7), _7 (Jan 7–8), _9 (Jan 8–9)], with current logic when sorted by name its [_5, _6, _7, _8, _9]. Now the resulting merge order is [_5, _9, _6, _8, _7].

Describe the solution you'd like

Allow supplying a segment comparator (use this for time-series index) pulled from the index’s own LeafSorter. So that the data is now evenly interleaved and sort queries dont pay a penalty by skipping Lucene’s BKD optimization .

Now from above high level example with _6 (Jan 1–4), _8 (Jan 4–6), _5 (Jan 6–7), _7 (Jan 7–8), _9 (Jan 8–9)]. The merge order should be [_6, _9, _8, _7, _5]. The gives more predictable DocID assignment and newest and oldest data is interleaved properly.

Related component

Search

Describe alternatives you've considered

No response

Additional context

No response

[prudhvigodithi]

Adding @bowenlan-amzn @expani @rishabhmaurya @msfroh to take a look and add some thoughts.
Thanks
@getsaurabh02 @asimmahmood1

[msfroh]

Now for time-series index and using LogByteSizeMergePolicy where merges always combine adjacent segments and assign the result a new Lucene name (via a global counter), but that name doesn’t reflect the segment’s true timestamp range. Because the current shuffle logic sorts segments by these Lucene names (info.name), the interleaving can drift from real time order.

Note that you could end up with the same behavior with TieredMergePolicy as well, but you're less likely to notice it. With TieredMergePolicy, the background merges are already not preserving segment adjacency, so you're less likely to notice. That said, regardless of merge policy, if we have a field that will commonly be implicated in sorting (like @timestamp), it's better to get a mix of high and low values early in the merged segment.

[mch2]

@prudhvigodithi are you currently working on this?

[prudhvigodithi]

Hey @mch2 I have just shared the proposal on how we can have a better ShuffleForcedMergePolicy, which gives us fixed shuffle pattern during force merge. Having this we dont have to spend time analyzing the DocID reassignment which can be the cause of the variance especially for sorts (similar to #17404).

I'm open for thoughts and I will prioritize this.

Thanks
@getsaurabh02