# UNDF: UNDF-2026-000000422
# hudi-0002 — InternalSchemaUtils.pruneInternalSchema ArrayList.contains O(N²) + pruneType O(F×D)

## File
`hudi-common/src/main/java/org/apache/hudi/internal/schema/utils/InternalSchemaUtils.java`
Lines 66–72 (topParentFieldIds dedup) and 105–160 (pruneType)

## Defect — Part A: topParentFieldIds dedup (O(N²))

```java
List<Integer> topParentFieldIds = new ArrayList<>();
names.stream().forEach(f -> {
    int id = schema.findIdByName(f.split("\\.")[0]);
    if (!topParentFieldIds.contains(id)) {      // O(N) scan of ArrayList per call
        topParentFieldIds.add(id);
    }
});
```

`topParentFieldIds` is `ArrayList<Integer>`. `.contains(id)` is O(N) — called once per name.
Total: O(N²) where N = names.size(). For a schema with many projected columns this becomes quadratic.

## Defect — Part B: pruneType field membership (O(F×D))

```java
private static Type pruneType(Type type, List<Integer> fieldIds) {
    // ...RECORD case:
    for (Types.Field f : fields) {
        Type newType = pruneType(f.type(), fieldIds);
        if (fieldIds.contains(f.fieldId())) {    // O(D) scan per field
            newTypes.add(f.type());
        }
    }
    // ...ARRAY case:
    if (fieldIds.contains(array.elementId())) {  // O(D) per array
    // ...MAP case:
    if (fieldIds.contains(map.valueId())) {      // O(D) per map
```

`fieldIds` is `List<Integer>`. Called recursively over the full schema tree (F nodes).
Total: O(F × D) where F = total schema fields, D = projected field count.

## Fix

```java
// Part A: use LinkedHashSet to preserve insertion order and deduplicate in O(1)
Set<Integer> topParentFieldIdSet = new LinkedHashSet<>();
names.stream().forEach(f -> {
    int id = schema.findIdByName(f.split("\\.")[0]);
    topParentFieldIdSet.add(id);   // HashSet.add deduplicates — O(1) amortized
});
List<Integer> topParentFieldIds = new ArrayList<>(topParentFieldIdSet);
```

```java
// Part B: convert fieldIds to HashSet before entering pruneType
private static Type pruneType(Type type, Set<Integer> fieldIds) {
    // ...same logic, but fieldIds.contains() is O(1)
}
// Call site: pruneType(schema.getRecord(), new HashSet<>(fieldIds))
```

## Complexity

| | Before | After |
|-|--------|-------|
| topParentFieldIds dedup | O(N²) | O(N) |
| pruneType per-field check | O(D) | O(1) |
| full pruneType traversal | O(F × D) | O(F) |

At F=D=500 fields: 250 000 comparisons → 500. **500x fewer operations.**

## Severity

MEDIUM — triggered on every call to `pruneInternalSchema()`, which is called during query
projection pushdown, Spark read, and schema evolution. Schemas with many nested columns amplify
both defects simultaneously.
