Investigate the document order variance for benchmark

[bowenlan-amzn]

When indexing large datasets like big5, we use the log merge policy. This policy ensures that only adjacent segments are merged, with the merged segments being inserted at the position of the first segment involved in the merge. These two conditions should theoretically result in perfectly aligned document order both within and across segments.

In this context, document order alignment means that the docId order of documents in the indexed data should perfectly match the order in the source data. We can read DocValues on the @timestamp field to check the alignment. This alignment is expected under the condition of using a single bulk indexing client and refreshing the index before sending the next bulk request.

However, an issue has been discovered (see GitHub issue #17404) where forcing a merge to a single segment results in significant document order disruption. Specifically, while the source data for big5 starts with documents from 2023-01-01, the single merged segment can begin with documents from dates like 01-13 or 01-12.

We hypothesize that this problem may be due to some unique logic applied during force merges to a single segment. Also some further investigation is needed to determine if this issue persists when force merging to an arbitrary number of segments greater than one.

Why we want to do this

Force merge to 1 segment is a common operation when we want to compare the search performance between 2 vesions of code that use different Lucene codec.
Without force merge to 1, the segment size and number are not easily controllable and cause variance in performance results. (Previous investigation opensearch-project/opensearch-benchmark#398)

This issue is expected to give us deeper understanding of the behavior of log merge policy and help us isolate the performance result variance from indexing/merge or search.

[prudhvigodithi]

High level explanation for document order variance with force merge

Coming from #17404 (comment) and as described in this issue, the unexpected document reordering we are observing after a force merge is caused by ShuffleForcedMergePolicy, which OpenSearch automatically enables during force merge operations — including _forcemerge?max_num_segments=1.

Even though with LogByteSizeMergePolicy we know it will merge the contiguous segments, but with force merge triggers the ShuffleForcedMergePolicy which is a special merge policy that interleaves (mixing things) documents from the oldest and newest segments during the merge.

In a normal merge (without shuffling) using LogByteSizeMergePolicy, Lucene would combine segments in sequence, so the merged segment’s document IDs preserve the original time ordering which is seen in Lucene university example https://github.com/msfroh/lucene-university/pull/28/files. This means in a fully merged index, doc IDs end up sorted by time, with the oldest documents first and the newest last.

AFAIK the shuffle is introduced because time-based indices usually have older documents first in segment order, a descending timestamp sort can be expensive if all the newest data is at the very end of a huge segment. The shuffle merge policy ensures that after a force merge, recent documents are interleaved among older ones in the segment, rather than all piled at the end and so time-range queries (e.g. filtering by a timestamp range) are not impacted.

Also coming from https://github.com/opensearch-project/OpenSearch/blob/main/server/src/main/java/org/opensearch/index/engine/InternalEngine.java#L2351 I see System.getProperty("opensearch.shuffle_forced_merge", Boolean.TRUE.toString()) the default is true, we should disable this as see the behavior once (may be as -Dopensearch.shuffle_forced_merge=false) and see if it falls back to default configured LogByteSizeMergePolicy. @shreyah963 @bowenlan-amzn

Some of these concepts are discussed in past issue https://github.com/opensearch-project/OpenSearch/issues/924.

FYI I will try to post an example here explaining the ShuffleForcedMergePolicy and how does it shuffle today, looking at the code at high level it looks like it will shuffle sorted by segment name.

Thanks
@getsaurabh02

[shreyah963]

Testing document order variance

Test Setup

• OpenSearch Version: 2.19.1
• Environment: EC2 instance
• Workload: big5
• Initial state: Index with default segmentation (17 segments)
• Test objective: Compare document timestamp ordering after force merging to different segment counts

Test Methodology

1. Created initial index using opensearch-benchmark:

sudo docker run -v $HOME/benchmarks:/opensearch-benchmark/.benchmark \
    opensearchproject/opensearch-benchmark:latest execute-test \
    --pipeline=benchmark-only \
    --workload=big5 \
    --include-tasks="delete-index,create-index,check-cluster-health,index-append,refresh-after-index" \
    --target-hosts=<OpenSearch Endpoint>:80 \
    --workload-params="distribution_version:2.19.1,
                       number_of_replicas:0,
                       bulk_indexing_clients:1"

2. Force merge to N segments where N = {10,5,2,1}

curl -X POST "localhost:9200/big5/_forcemerge?max_num_segments=N&pretty"

3. Compared document ordering using custom Java tools:

• Index to Index Comparison Tool
• Extracting TimeStamp for JSON Comparison
• JSON to Index Comparison Tool
• Setup Instructions

Results

Comparison with Default (17) Segments

Default to 10 segments: 1.10% documents reordered
Default to 5 segments:  71.96% documents reordered
Default to 2 segments:  99.99% documents reordered
Default to 1 segment:   82.71% documents reordered

Sequential Merge Comparisons

Big5 JSON to Default (17): 0% documents reordered
Default to 10 segments: 1.10% documents reordered
10 to 5 segments:    72.35% documents reordered
5 to 2 segments:     100% documents reordered
2 to 1 segment:      100% documents reordered

Upon investigation, ShuffleForcedMergePolicy does show to be the cause of the document ordering behavior we're seeing. ShuffleForcedMergePolicy is a specialized merge policy designed to improve query performance for time-series data. According to its class documentation in ShuffleForcedMergePolicy.java:

"A FilterMergePolicy that interleaves eldest and newest segments picked by MergePolicy#findForcedMerges and MergePolicy#findForcedDeletesMerges. This allows time-based indices, that usually have the eldest documents first, to be efficient at finding the most recent documents too."

The core functionality is in the interleaveList method. The method:

• Sorts segments by name
• Uses a two-pointer approach (left from start, right from end) to interleave the oldest and newest segments
• Additionally considers segment size, placing the smaller segment first in each pair
• Since recent documents are distributed throughout segments this distribution improves performance for time-range queries, especially when querying recent data

The merge policy configuration in InternalEngine.java follows a decorator pattern:

// 1. Start with base policy (e.g., LogByteSizeMergePolicy)
MergePolicy mergePolicy = config().getMergePolicy();

// 2. Add core functionality layers
mergePolicy = new RecoverySourcePruneMergePolicy(
    SourceFieldMapper.RECOVERY_SOURCE_NAME,
    softDeletesPolicy::getRetentionQuery,
    new SoftDeletesRetentionMergePolicy(
        Lucene.SOFT_DELETES_FIELD,
        softDeletesPolicy::getRetentionQuery,
        new PrunePostingsMergePolicy(mergePolicy, IdFieldMapper.NAME)
    )
);

// 3. Optional: Add shuffle capability for force merges
if (shuffleForcedMerge) {
    mergePolicy = new ShuffleForcedMergePolicy(mergePolicy);
}

// 4. Optional: Add merge-on-flush policy
if (config().getIndexSettings().isMergeOnFlushEnabled()) {
    // ... merge-on-flush configuration
    if (mergeOnFlushPolicy.isPresent()) {
        mergePolicy = mergeOnFlushPolicy.get().apply(mergePolicy);
    }
}

// 5. Final wrapper
iwc.setMergePolicy(new OpenSearchMergePolicy(mergePolicy));

Each wrapper adds specific functionality while maintaining the core merging behavior. This modular approach allows easy addition/removal of features like document shuffling.

The system property opensearch.shuffle_forced_merge determines whether ShuffleForcedMergePolicy is added to the merge policy chain (default: true). When disabled (-Dopensearch.shuffle_forced_merge=false):

• ShuffleForcedMergePolicy is skipped in the merge policy chain
• Documents maintain their original ordering during force merges without the shuffling behavior

[bowenlan-amzn]

Thanks @shreyah963 for the thorough report. We have good clarify on this problem and I'm closing this issue.