# UNDF: UNDF-2026-000000423
# hudi-0003 — HoodieTableMetadataUtil.getRevivedAndDeletedKeysFromMergedLogs List.contains O(N×M)

## File
`hudi-common/src/main/java/org/apache/hudi/metadata/HoodieTableMetadataUtil.java`
Line 1005–1007

## Defect

```java
public static <T> Pair<Set<String>, Set<String>> getRevivedAndDeletedKeysFromMergedLogs(
    ..., List<String> logFilePaths, ..., List<String> currentLogFilePaths, ...) {

    List<String> logFilePathsWithoutCurrentLogFiles = logFilePaths.stream()
        .filter(logFilePath -> !currentLogFilePaths.contains(logFilePath))  // O(M) per element
        .collect(toList());
```

`currentLogFilePaths` is a `List<String>` (constructed at line 925 via `Collectors.toList()`).
`List.contains()` does a linear scan — O(M) per call where M = currentLogFilePaths.size().
The stream filter applies this once per element of `logFilePaths` — N calls total.

Total complexity: **O(N × M)** where N = total log file paths, M = current log file paths count.

This method is called during every Record-Level Index (RLI) update, which happens on each delta
commit. In a table with many log files per partition (large MOR tables, frequent compaction), both
N and M can be in the hundreds.

## Fix

Convert `currentLogFilePaths` to a `HashSet<String>` before the filter. String equality is
well-defined and path strings are unique identifiers.

```java
Set<String> currentLogFilePathSet = new HashSet<>(currentLogFilePaths);  // O(M) once
List<String> logFilePathsWithoutCurrentLogFiles = logFilePaths.stream()
    .filter(logFilePath -> !currentLogFilePathSet.contains(logFilePath))   // O(1) per element
    .collect(toList());
```

The call site (line 925–927) creates `currentLogFilePaths` as a List and passes it to this method.
Alternatively, build it as a `HashSet` at the call site.

## Complexity

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

At N=M=500 log files: 250 000 comparisons → 1000. **250x fewer operations.**

## Severity

MEDIUM — triggered on every delta commit when RLI is enabled. MOR (Merge-on-Read) tables with
high write frequency and many log files per filegroup amplify this significantly.

## Import required

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