# UNDF: UNDF-2026-000000447
# kylin-0001: NDataflowManager.updateDataflowDetailsLayouts — O(L²) ArrayList.contains in layout update loop

## CWE-407 — Algorithmic Complexity

| Field | Value |
|-------|-------|
| ID | kylin-0001 |
| Severity | MEDIUM |
| Ecosystem | Apache Kylin |
| Package | `org.apache.kylin.metadata.cube.model` |
| File | `src/core-metadata/src/main/java/org/apache/kylin/metadata/cube/model/NDataflowManager.java` |
| Lines | 655–672 |
| Complexity | O(L²) — two nested list scans per segment layout update |
| Hot path | Called during index build / segment compaction for every segment when layouts are added or removed |

## Defect

```java
// DEFECT: toRemoveLayouts is List<Long> (ArrayList) passed by caller
// removeIf iterates all layouts, calling toRemoveLayouts.contains per element — O(S×R)
layouts.removeIf(layout -> toRemoveLayouts.contains(layout.getLayoutId()));

// DEFECT: existLayouts is ArrayList<Long> from Collectors.toList()
// for loop calls existLayouts.contains per candidate — O(T×L)
List<Long> existLayouts = layouts.stream()
    .map(NDataLayout::getLayoutId)
    .collect(Collectors.toList());
for (Long layoutId : toAddLayouts) {
    if (!existLayouts.contains(layoutId)) {   // O(L) per iteration
        layouts.add(NDataLayout.newDataLayout(copyForWrite, layoutId));
    }
}
```

Where S = current layout count, R = toRemoveLayouts.size(), T = toAddLayouts.size(), L = post-remove layout count.
In practice S, R, T, L all grow together with the number of indexes defined on a model — 100–1000 layouts per segment is common in Kylin deployments.

## Fix

```java
// AFTER: convert both lists to HashSet before the critical sections
Set<Long> toRemoveSet = new HashSet<>(toRemoveLayouts);
layouts.removeIf(layout -> toRemoveSet.contains(layout.getLayoutId()));  // O(1) per check

Set<Long> existLayoutSet = layouts.stream()
    .map(NDataLayout::getLayoutId)
    .collect(Collectors.toCollection(HashSet::new));
for (Long layoutId : toAddLayouts) {
    if (!existLayoutSet.contains(layoutId)) {   // O(1) per check
        layouts.add(NDataLayout.newDataLayout(copyForWrite, layoutId));
    }
}
```

## Speedup

| L (layouts per segment) | Before (ops) | After (ops) | Speedup |
|--------------------------|--------------|-------------|---------|
| 10 | 100 | 10 | 10× |
| 100 | 10,000 | 100 | 100× |
| 500 | 250,000 | 500 | 500× |
| 1,000 | 1,000,000 | 1,000 | 1,000× |

## Call chain

`ModelService.updateIndexes` → `NDataflowManager.updateDataflowDetailsLayouts` (per-segment, batched in a loop over all segments of the dataflow)

Each segment independently executes both list scans, so for a dataflow with M segments the total work is O(M × L²) before the fix, O(M × L) after.
