# 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

```java
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.

```java
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

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