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²))

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))

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

// 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);

// 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.

2.6 KiB Raw Permalink Blame History Unescape Escape