# UNDF: UNDF-2026-000000001
# UNDF: (pending)
# doris-0003: EquivalenceClass.getEquivalenceSetList — O(N²) List.contains dedup

## CWE-407 — Algorithmic Complexity

| Field | Value |
|-------|-------|
| ID | doris-0003 |
| Severity | MEDIUM |
| Ecosystem | doris |
| Package | fe-core |
| File | `fe/fe-core/src/main/java/org/apache/doris/nereids/rules/exploration/mv/EquivalenceClass.java` |
| Lines | 130–146 |
| Complexity | O(N²) |
| Hot path | Called during materialized view rewrite in query planning (every query with MV candidates) |

## Defect

`getEquivalenceSetList()` deduplicates equivalence class lists using a `List<List<SlotReference>>`
as the visited set. `visited.contains(slotSet)` calls `ArrayList.contains()` which iterates the
entire visited list comparing lists element-by-element — O(N) per call. The outer loop also
iterates N times, making the total complexity O(N²) where N is the number of distinct equivalence
slot lists in `equivalenceSlotMap.values()`.

This runs on every query that touches materialized view rewrite logic in Doris Nereids.

```java
public List<List<SlotReference>> getEquivalenceSetList() {
    if (equivalenceSlotList != null) {
        return equivalenceSlotList;
    }
    List<List<SlotReference>> equivalenceSets = new ArrayList<>();
    List<List<SlotReference>> visited = new ArrayList<>();         // O(N) per contains
    equivalenceSlotMap.values().forEach(slotSet -> {
        if (!visited.contains(slotSet)) {                          // O(N) scan
            equivalenceSets.add(slotSet);
        }
        visited.add(slotSet);
    });
    this.equivalenceSlotList = equivalenceSets;
    return this.equivalenceSlotList;
}
```

## Fix

`equivalenceSlotMap` maps each `SlotReference` to its equivalence-class list (which is a shared
`List<SlotReference>` object). Deduplication by object identity is sufficient and correct because
the union-find structure ensures all members of an equivalence class share the same list reference.
Use `IdentityHashMap` or `Set` based on object identity:

```java
public List<List<SlotReference>> getEquivalenceSetList() {
    if (equivalenceSlotList != null) {
        return equivalenceSlotList;
    }
    // Use identity comparison: all slots in the same equivalence class share the same List object
    Set<List<SlotReference>> seen = Collections.newSetFromMap(new IdentityHashMap<>());
    List<List<SlotReference>> equivalenceSets = new ArrayList<>();
    for (List<SlotReference> slotSet : equivalenceSlotMap.values()) {
        if (seen.add(slotSet)) {                                    // O(1) identity hash
            equivalenceSets.add(slotSet);
        }
    }
    this.equivalenceSlotList = equivalenceSets;
    return this.equivalenceSlotList;
}
```

## Speedup

| N (equivalence classes) | Before (ops) | After (ops) | Speedup |
|-------------------------|-------------|-------------|---------|
| 10 | 100 | 10 | 10× |
| 50 | 2,500 | 50 | 50× |
| 100 | 10,000 | 100 | 100× |
| 500 | 250,000 | 500 | 500× |
