# UNDF: UNDF-2026-000000487
# opensearch-001: ImmutableCacheStatsHolder O(n²) levelsList.contains in filterLevels

## Classification
- **CWE**: CWE-407 (Inefficient Algorithmic Complexity)
- **Severity**: MEDIUM
- **Path**: Cache stats reporting — called on every stats API request

## Location
`server/src/main/java/org/opensearch/common/cache/stats/ImmutableCacheStatsHolder.java:232-235`

## Defect

```java
private List<String> filterLevels(String[] levels, List<String> dimensionNames) {
    if (levels == null) {
        return dimensionNames;
    }
    List<String> levelsList = Arrays.asList(levels);       // backed array — O(n) contains
    List<String> result = new ArrayList<>();
    for (String dimensionName : dimensionNames) {
        if (levelsList.contains(dimensionName)) {           // O(levels.length) per iteration
            result.add(dimensionName);
        }
    }
    return result;
}
```

`Arrays.asList()` returns a fixed-size list backed by the array — `contains()` is a
linear O(levels.length) scan. The outer loop runs `dimensionNames.size()` times.

Total: **O(dimensionNames × levels)** = O(n²) when both grow proportionally.

For a cluster with D dimensions and L requested levels this fires on every
`/_nodes/stats` or cache stats request.

## Fix

```java
Set<String> levelsSet = new HashSet<>(Arrays.asList(levels));  // O(L) build
for (String dimensionName : dimensionNames) {
    if (levelsSet.contains(dimensionName)) {                    // O(1)
        result.add(dimensionName);
    }
}
```

## Complexity
| Metric | Before | After |
|--------|--------|-------|
| contains() | O(L) | O(1) |
| Full filter | O(D×L) | O(D+L) |

## Affected Versions
All OpenSearch versions with the multi-tier cache stats feature.
