# UNDF: UNDF-2026-000000385
# elasticsearch-002: IngestDocument appendValues O(n²) list.contains

## Classification
- **CWE**: CWE-407 (Inefficient Algorithmic Complexity)
- **Severity**: HIGH
- **Path**: Hot ingest pipeline path — every document appended with allowDuplicates=false

## Location
`server/src/main/java/org/elasticsearch/ingest/IngestDocument.java:960`

## Defect

```java
private static Object appendValues(Object maybeList, Object value,
        boolean allowDuplicates, boolean ignoreEmptyValues) {
    List<Object> list = ...;

    if (value instanceof List<?> valueList) {
        for (Object val : valueList) {
            if ((allowDuplicates || list.contains(val) == false) ...) {  // O(n)
                list.add(val);
            }
        }
    }
}
```

When `allowDuplicates=false` and `value` is a List of M items, every iteration calls
`list.contains(val)` which is O(list.size()). As `list` grows, each subsequent check
is more expensive. For an existing list of N elements and M values to append:

Total comparisons = N + (N+1) + ... + (N+M-1) = **O(N×M)** — effectively O(n²)
when N and M are comparable.

This fires on every document processed by an Append processor with
`allow_duplicates: false` — a common ingest configuration for deduplicating tags,
categories, or enum-valued fields.

## Fix

Build a `HashSet` from the existing list once, then do O(1) lookups:

```java
Set<Object> seen = allowDuplicates ? null : new HashSet<>(list);

for (Object val : valueList) {
    if (allowDuplicates || seen.add(val)) {   // add() returns false if already present
        list.add(val);
        valuesWereAppended = true;
    }
}
```

`HashSet.add()` simultaneously tests membership and inserts — one pass, no separate
`contains()` call needed.

## Complexity
| Metric | Before | After |
|--------|--------|-------|
| Per-item check | O(N) where N=current list size | O(1) |
| Total for M appends | O(N×M) | O(N+M) |
| At N=M=10,000 | 100,000,000 comparisons | 20,000 |

## Affected Versions
Present in all versions with the Append ingest processor (since early Elasticsearch 5.x).
Also present in OpenSearch fork: `IngestDocument.java:671`.
