# UNDF: UNDF-2026-000000487
# opensearch-003: IndexShardRoutingTable O(n²) weightedRoutings.contains in filter stream

## Classification
- **CWE**: CWE-407 (Inefficient Algorithmic Complexity)
- **Severity**: HIGH
- **Path**: Shard routing — fired on every search/index request during weighted routing population

## Location
`server/src/main/java/org/opensearch/cluster/routing/IndexShardRoutingTable.java:1064-1067` (active shards)
`server/src/main/java/org/opensearch/cluster/routing/IndexShardRoutingTable.java:1100-1103` (initializing shards)

## Defect

```java
private void populateActiveShardWeightsMap(WeightedRouting weightedRouting, DiscoveryNodes nodes, double defaultWeight) {
    WeightedRoutingKey key = new WeightedRoutingKey(weightedRouting);
    List<ShardRouting> weightedRoutings = shardsOrderedByWeight(activeShards, weightedRouting, nodes, defaultWeight);
    List<ShardRouting> nonWeightedRoutings = activeShards.stream()
        .filter(shard -> !weightedRoutings.contains(shard))   // O(weightedRoutings.size()) per shard
        .collect(Collectors.toUnmodifiableList());
    ...
}
```

`weightedRoutings` is an `ArrayList<ShardRouting>`. Its `contains()` performs a linear scan using
`ShardRouting.equals()`. The `.filter()` stream runs over `activeShards.size()` elements, calling
`weightedRoutings.contains()` for each one → **O(n²)** where n = number of active shards.

The same defect exists in `populateInitializingShardWeightsMap` (lines 1100–1103).

Both methods are called lazily on the first routing request per `WeightedRouting` key, but with
many indices or frequent routing key changes this can trigger repeatedly on hot paths.

## Impact
- Each index has its own `IndexShardRoutingTable`; with many indices and many shards per index,
  this fires frequently under weighted routing load.
- For n=50 shards: ~2,500 ShardRouting.equals() calls instead of ~50
- For n=200 shards: ~40,000 calls instead of ~200 (200× overhead)

## Fix
Convert `weightedRoutings` to a `Set` for O(1) membership tests:

```java
List<ShardRouting> weightedRoutingsList = shardsOrderedByWeight(activeShards, weightedRouting, nodes, defaultWeight);
Set<ShardRouting> weightedRoutingsSet = new HashSet<>(weightedRoutingsList);   // O(n) build
List<ShardRouting> nonWeightedRoutings = activeShards.stream()
    .filter(shard -> !weightedRoutingsSet.contains(shard))   // O(1) per shard
    .collect(Collectors.toUnmodifiableList());
```

`ShardRouting` implements `equals()` and `hashCode()` correctly (it's a value object), so
`HashSet<ShardRouting>` is safe.

## Complexity
| Metric | Before | After |
|--------|--------|-------|
| Membership test | O(n) ArrayList.contains | O(1) HashSet.contains |
| Full populate | O(n²) | O(n) |
| Speedup at n=200 shards | — | ~200× |

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