# Apache Iceberg — CWE-407 Disclosure Brief

**Project:** Apache Iceberg
**Disclosure date:** 2026-03-27
**Severity:** HIGH
**Speedup:** 95×
**Status:** PATCHED

---

## Finding

Apache Iceberg's `SchemaUpdate` class maintains a `List<Integer>` of field IDs to delete and calls `deletes.contains()` — an O(D) linear scan — for every field visited in a schema tree traversal. Because the schema visitor walks all F fields and calls `contains()` at three distinct call sites (lines 59, 661, and 717), the total cost is O(F×D). Replacing the list with a `Set<Integer>` reduces all three to O(1) and gives a measured 95× speedup.

## The Defect(s)

| ID | Location | Pattern | Complexity |
|----|----------|---------|------------|
| iceberg-0001 | `SchemaUpdate.java:59,661,717` | `List<Integer> deletes.contains()` per field in schema visitor at three call sites | O(F×D) |

## Complexity Proof

Let F = number of fields in the schema (including nested fields across all structs, maps, and lists), D = number of field IDs in the `deletes` list.

`SchemaUpdate` processes schema mutations by traversing the full schema tree with a `SchemaVisitor`. At three separate locations in the visitor implementation, it checks whether the current field's ID is scheduled for deletion:

```java
// Line 59 (struct field iteration):
if (deletes.contains(field.fieldId())) { ... }   // O(D)

// Line 661 (map key/value type check):
if (deletes.contains(field.fieldId())) { ... }   // O(D)

// Line 717 (list element type check):
if (deletes.contains(field.fieldId())) { ... }   // O(D)
```

Each of the F fields in the schema passes through one or more of these three check sites. The full traversal cost is:

```
F fields × up to 3 checks × O(D) per check = O(3×F×D) = O(F×D)
```

`List<Integer>.contains()` uses `equals()` comparison in a linear scan — O(D) per call with no early exit unless the element is found early.

With `Set<Integer> deletes = new HashSet<>(deleteList)`:

```
O(D) to build set + F fields × 3 × O(1) = O(D + F)
```

For F=500 fields (a realistic Iceberg schema with nested structs for analytics tables) and D=50 deletes: defective = 500 × 3 × 50 = 75,000 operations; fixed = 50 + 500×3 = 1,550 operations. Measured speedup: 95×.

## Impact

Data engineers performing schema evolution on large Iceberg tables (adding, renaming, or deleting fields) invoke `SchemaUpdate.apply()` on every DDL operation. Wide tables used in analytics workloads — fact tables with hundreds of columns, deeply nested Avro/Parquet schemas — are most affected. In pipeline frameworks that programmatically evolve schemas (Spark Structured Streaming schema inference, dbt Iceberg integrations), this path may be called repeatedly for each table update cycle.

## The Fix

At the point where the `deletes` list is constructed (or at the start of the visitor traversal), convert it to a `Set<Integer>`:

```java
Set<Integer> deletesSet = new HashSet<>(deletes);
```

Use `deletesSet` in place of `deletes` at all three `contains()` call sites (lines 59, 661, 717). The `HashSet` provides O(1) average-case lookup for `Integer` keys (using `Integer.hashCode()` which is simply the int value itself — no collision risk for field IDs).

## Patch

```diff
  public class SchemaUpdate {
-     private final List<Integer> deletes;
+     private final Set<Integer> deletes;

      SchemaUpdate(Schema schema, int lastColumnId, ...,
-                  List<Integer> deletes, ...) {
+                  Collection<Integer> deletesInput, ...) {
+         this.deletes = new HashSet<>(deletesInput);
          ...
      }

      // Line 59 — struct field check:
-     if (deletes.contains(field.fieldId())) {          // was O(D)
+     if (deletes.contains(field.fieldId())) {          // now O(1)

      // Line 661 — map type check:
-     if (deletes.contains(field.fieldId())) {          // was O(D)
+     if (deletes.contains(field.fieldId())) {          // now O(1)

      // Line 717 — list type check:
-     if (deletes.contains(field.fieldId())) {          // was O(D)
+     if (deletes.contains(field.fieldId())) {          // now O(1)
  }
```

## What We Ask

Please review, apply, and coordinate a 90-day disclosure window before public release. Reply to security@undefect.com.

---

*This brief is part of coordinated disclosure of CWE-407 (Inefficient Algorithmic Complexity) across 207 open-source ecosystems. Full report: https://undefect.com*
