# UNDF: UNDF-2026-000000487
# opensearch-002: MustToFilterRewriter O(n²) mustClausesToMove.contains in copy loop

## Classification
- **CWE**: CWE-407 (Inefficient Algorithmic Complexity)
- **Severity**: MEDIUM
- **Path**: Query rewrite phase — fires on every bool query with must clauses

## Location
`server/src/main/java/org/opensearch/search/query/rewriters/MustToFilterRewriter.java:104`

## Defect

```java
List<QueryBuilder> mustClausesToMove = new ArrayList<>();

// Phase 1: identify clauses to move (O(n))
for (QueryBuilder clause : boolQuery.must()) {
    QueryBuilder rewrittenClause = rewriteIfNeeded(clause, context);
    rewrittenMustClauses.add(rewrittenClause);
    if (isClauseIrrelevantToScoring(rewrittenClause, context)) {
        mustClausesToMove.add(rewrittenClause);
    }
}

// Phase 2: copy must clauses except moved ones (O(n) × O(n) = O(n²))
for (QueryBuilder rewrittenClause : rewrittenMustClauses) {
    if (!mustClausesToMove.contains(rewrittenClause)) {   // O(mustClausesToMove.size())
        rewritten.must(rewrittenClause);
    }
}
```

`mustClausesToMove` is an `ArrayList`. The copy loop iterates all `rewrittenMustClauses`
(up to M items) and for each calls `mustClausesToMove.contains()` which is O(K) where K
is the number of clauses to move.

Total: **O(M × K)** — worst case O(n²) when half the clauses are moved.

This fires on every search request that includes a bool query with must clauses, which is
the majority of structured OpenSearch queries.

## Fix

```java
Set<QueryBuilder> mustClausesToMoveSet = new HashSet<>(mustClausesToMove);
// ...
for (QueryBuilder rewrittenClause : rewrittenMustClauses) {
    if (!mustClausesToMoveSet.contains(rewrittenClause)) {   // O(1) identity hash
        rewritten.must(rewrittenClause);
    }
}
```

Note: `QueryBuilder` identity equality via `HashSet` is appropriate here since
`rewrittenMustClauses` contains the same object references added to `mustClausesToMove`.

## Complexity
| Metric | Before | After |
|--------|--------|-------|
| contains() | O(K) | O(1) |
| Full copy phase | O(M×K) | O(M+K) |

## Affected Versions
All OpenSearch versions with the MustToFilterRewriter (added in query rewriter framework).
