# UNDF: UNDF-2026-000000425
# iceberg-0001 — SchemaUpdate.ApplyChanges List<Integer> deletes O(F×D)

## File
`core/src/main/java/org/apache/iceberg/SchemaUpdate.java`
Lines 59, 661, 717

## Defect

```java
// Line 59 — field declaration
private final List<Integer> deletes = Lists.newArrayList();  // ArrayList

// Line 660–663 — field() visitor — called ONCE PER SCHEMA FIELD
@Override
public Type field(Types.NestedField field, Type fieldResult) {
    int fieldId = field.fieldId();
    if (deletes.contains(fieldId)) {    // O(D) scan per field visit
        return null;
    }
    // ...
}

// Line 716–718 — map() visitor
public Type map(Types.MapType map, Type kResult, Type valueResult) {
    int keyId = map.fields().get(0).fieldId();
    if (deletes.contains(keyId)) {      // O(D) scan per map
        throw new IllegalArgumentException("Cannot delete map keys: " + map);
    }
```

`TypeUtil.visit(schema, new ApplyChanges(...))` walks every field in the schema tree —
O(F) calls to `field()`. Each call does `deletes.contains()` on a `List<Integer>` — O(D) per call.

Also in the outer `applyChanges()` (line 533–588), the loop over `identifierFieldNames` calls
`deletes.contains()` twice per identifier field (lines 549, 556) plus a while-loop over parent
chain — in total O(I × depth × D) for the validation pass.

Total schema visitor cost: **O(F × D)** where F = schema field count, D = delete count.

## Fix

Change the backing store of `deletes` from `ArrayList` to `HashSet`. The field is only ever
used for `contains()` checks and `add()` — no index-based access — so a `HashSet<Integer>` is
a drop-in replacement.

```java
// Before:
private final List<Integer> deletes = Lists.newArrayList();

// After:
private final Set<Integer> deletes = Sets.newHashSet();
```

The `ApplyChanges` inner class also holds a `List<Integer> deletes` at line 591. Change it to
`Set<Integer>` and update the constructor parameter at line 597.

```java
// Before (line 591):
private final List<Integer> deletes;

// After:
private final Set<Integer> deletes;
```

All `.contains()` calls become O(1). No other code changes required — `add()` and `contains()`
are both valid `Set` operations.

## Complexity

| | Before | After |
|-|--------|-------|
| deletes.contains() per field | O(D) | O(1) |
| full schema traversal | O(F × D) | O(F) |

At F=1000 fields, D=100 deletes: 100 000 comparisons → 1000. **100x fewer operations.**
For Iceberg tables with wide schemas (Parquet files with 500+ columns), this is significant.

## Severity

HIGH — `applyChanges()` is called on every `updateSchema()` transaction commit and on every
`SchemaUpdate.apply()` in the table metadata path. Wide schemas with batch deletes amplify
the O(F×D) factor. Schema evolution on large analytical tables hits this on every DDL operation.
