# UNDF: UNDF-2026-000000607
# UNDF: (pending)
# doris-0002: PlanNode.addConjunct — ArrayList.contains() O(C²) dedup

## CWE-407 — Algorithmic Complexity

| Field | Value |
|-------|-------|
| ID | doris-0002 |
| Severity | MEDIUM |
| Ecosystem | doris |
| Package | fe-core/planner |
| File | `fe/fe-core/src/main/java/org/apache/doris/planner/PlanNode.java` |
| Lines | 308–324 |
| Complexity | O(C²) — C conjuncts, each `addConjuncts()` call scans the list |
| Hot path | Query planning — `addConjunctsToPlanNode` in PhysicalPlanTranslator |

## Defect

`PlanNode.conjuncts` is an `ArrayList<Expr>`. The `addConjunct` method deduplicates
by calling `ArrayList.contains()`, which is O(C):

```java
// PlanNode.java
protected List<Expr> conjuncts = Lists.newArrayList();

public void addConjuncts(List<Expr> conjuncts) {
    if (conjuncts == null) return;
    for (Expr conjunct : conjuncts) {    // O(C_new)
        addConjunct(conjunct);
    }
}

public void addConjunct(Expr conjunct) {
    if (conjuncts == null) {
        conjuncts = Lists.newArrayList();
    }
    if (!conjuncts.contains(conjunct)) {  // O(C_existing) scan
        conjuncts.add(conjunct);
    }
}
```

`PhysicalPlanTranslator.addConjunctsToPlanNode` calls this from a double loop:

```java
// PhysicalPlanTranslator.java:3039-3047
private void addConjunctsToPlanNode(PhysicalFilter<? extends Plan> filter,
        PlanNode planNode, PlanTranslatorContext context) {
    for (Expression conjunct : filter.getConjuncts()) {                     // O(F)
        for (Expression singleConjunct : ExpressionUtils.extractConjunctionToSet(conjunct)) { // O(K)
            planNode.addConjunct(ExpressionTranslator.translate(singleConjunct, context)); // O(C)
        }
    }
}
```

Total: O(F × K × C) — with F=filter conjuncts, K=sub-conjuncts per predicate,
C=existing conjuncts in node. At C=100 conjuncts, each `addConjunct` call costs
100 equality comparisons instead of O(1).

## Fix

Replace `conjuncts` with a `LinkedHashSet<Expr>` (preserves insertion order,
O(1) contains):

```java
// Before:
protected List<Expr> conjuncts = Lists.newArrayList();

public void addConjunct(Expr conjunct) {
    if (conjuncts == null) {
        conjuncts = Lists.newArrayList();
    }
    if (!conjuncts.contains(conjunct)) {
        conjuncts.add(conjunct);
    }
}

// After:
protected Set<Expr> conjunctSet = new LinkedHashSet<>();
protected List<Expr> conjuncts = null; // lazy view, computed on demand

public void addConjunct(Expr conjunct) {
    conjunctSet.add(conjunct);  // O(1) via hashCode/equals
}

public List<Expr> getConjuncts() {
    return new ArrayList<>(conjunctSet);
}
```

If `Expr` does not implement `hashCode`/`equals`, a `LinkedHashMap<Expr, Boolean>`
keyed by identity (`System.identityHashCode`) is the alternative.

## Speedup

| C (conjuncts) | addConjuncts calls | Before (ops) | After (ops) | Speedup |
|---|---|---|---|---|
| 20 | 20 | 400 | 20 | 20× |
| 100 | 100 | 10,000 | 100 | 100× |
| 500 | 500 | 250,000 | 500 | 500× |
