# UNDF: UNDF-2026-000000487
# opensearch-004: TransportSegmentReplicationStatsAction O(n²) shardsToFetch.contains in response loop

## Classification
- **CWE**: CWE-407 (Inefficient Algorithmic Complexity)
- **Severity**: MEDIUM
- **Path**: Segment replication stats API — fires on every `GET /_cat/segment_replication` or stats request

## Location
`server/src/main/java/org/opensearch/action/admin/indices/replication/TransportSegmentReplicationStatsAction.java:109`
`server/src/main/java/org/opensearch/action/admin/indices/replication/TransportSegmentReplicationStatsAction.java:116`

## Defect

```java
final List<Integer> shardsToFetch = Arrays.stream(shards).map(Integer::valueOf).collect(Collectors.toList());

for (SegmentReplicationShardStatsResponse response : responses) {
    if (response != null) {
        if (response.getReplicaStats() != null) {
            final ShardRouting shardRouting = response.getReplicaStats().getShardRouting();
            if (shardsToFetch.isEmpty() || shardsToFetch.contains(shardRouting.shardId().getId())) {  // O(F) per response
                replicaStats.putIfAbsent(...);
            }
        }
        if (response.getPrimaryStats() != null) {
            final ShardId shardId = response.getPrimaryStats().getShardId();
            if (shardsToFetch.isEmpty() || shardsToFetch.contains(shardId.getId())) {  // O(F) per response
                primaryStats.compute(...);
            }
        }
    }
}
```

`shardsToFetch` is a `List<Integer>`. Its `contains()` is a linear O(F) scan.
The outer loop runs `responses.size()` times (one per shard across all nodes).
Total complexity: **O(S × F)** where S = shard response count, F = requested shard IDs.

In a cluster with 1000 shards and a request for 50 specific shards, this performs
~100,000 integer comparisons instead of ~2,000.

## Impact
- Stats API requests on large clusters (many shards) with a shard filter run quadratically
- Each call to `GET /_cat/segment_replication?shards=1,2,3,...` degrades quadratically

## Fix
Convert `shardsToFetch` to a `Set<Integer>` for O(1) membership tests:

```java
final Set<Integer> shardsToFetch = Arrays.stream(shards)
    .map(Integer::valueOf)
    .collect(Collectors.toCollection(HashSet::new));

for (SegmentReplicationShardStatsResponse response : responses) {
    if (response != null) {
        if (response.getReplicaStats() != null) {
            final ShardRouting shardRouting = response.getReplicaStats().getShardRouting();
            if (shardsToFetch.isEmpty() || shardsToFetch.contains(shardRouting.shardId().getId())) {  // O(1)
                ...
            }
        }
        ...
    }
}
```

## Complexity
| Metric | Before | After |
|--------|--------|-------|
| Membership test | O(n) List.contains | O(1) HashSet.contains |
| Full response loop | O(S × F) | O(S + F) |
| Speedup at S=1000, F=50 | — | ~50× |

## Status
PATCHED (unit test confirms behaviour, see `defects/opensearch/unit/SegmentReplicationShardsToFetchContains.java`)
