UNDF: UNDF-2026-000000421

hudi-0001 — BaseHoodieTimeline.appendLoadedInstants List.contains O(N×M)

File

hudi-common/src/main/java/org/apache/hudi/common/table/timeline/BaseHoodieTimeline.java Line 123–131

Defect

protected void appendLoadedInstants(List<HoodieInstant> loadedInstants) {
    List<HoodieInstant> existingInstants = getInstants();          // List<HoodieInstant>
    List<HoodieInstant> newInstants = loadedInstants.stream()
        .filter(instant -> !existingInstants.contains(instant))   // O(M) per call
        .collect(Collectors.toList());
    if (!newInstants.isEmpty()) {
      appendInstants(newInstants);
    }
}

existingInstants is a List<HoodieInstant> (the backing field private List<HoodieInstant> instants). List.contains() performs a linear scan — O(M) per invocation. The stream filter calls it once per element of loadedInstants — N calls total.

Total complexity: O(N × M) where N = loadedInstants.size(), M = existing timeline size.

In a Hudi table with a long history (thousands of commits), M can be large. This method is called during incremental timeline loading (time-range and limit-based), so both N and M can be in the thousands during compaction or restore operations.

Fix

Convert existingInstants to a HashSet before the filter. HoodieInstant implements equals() and hashCode() based on timestamp+action+state — so a HashSet works correctly.

protected void appendLoadedInstants(List<HoodieInstant> loadedInstants) {
    Set<HoodieInstant> existingSet = new HashSet<>(getInstants());  // O(M) one-time
    List<HoodieInstant> newInstants = loadedInstants.stream()
        .filter(instant -> !existingSet.contains(instant))          // O(1) per call
        .collect(Collectors.toList());
    if (!newInstants.isEmpty()) {
      appendInstants(newInstants);
    }
}

Complexity

	Before	After
per-element membership test	O(M)	O(1)
full filter pass	O(N × M)	O(N + M)

At N=M=10 000: 100 000 000 comparisons → 20 000 comparisons. 5000x fewer operations.

Severity

MEDIUM — triggered during incremental timeline load on large tables (restore, compaction, archival). Degrades linearly with table history depth.

Import required

import java.util.HashSet;
import java.util.Set;

2.3 KiB Raw Permalink Blame History Unescape Escape