# UNDF: UNDF-2026-000000560
# UNDF: (pending)
# trino-0001: StatementAnalyzer JOIN USING — O(C×J) ArrayList.contains for field dedup

## CWE-407 — Algorithmic Complexity

| Field | Value |
|-------|-------|
| ID | trino-0001 |
| Severity | MEDIUM |
| Ecosystem | trino |
| Package | trino-main |
| File | `core/trino-main/src/main/java/io/trino/sql/analyzer/StatementAnalyzer.java` |
| Lines | 3975–4030 |
| Complexity | O(C×J) |
| Hot path | Called for every SQL JOIN ... USING (...) query during analysis |

## Defect

When analyzing a `JOIN ... USING (col1, col2, ...)` clause, two `ArrayList<Integer>` lists
(`leftJoinFields`, `rightJoinFields`) are built from the USING column indices, then used as
membership test targets in loops over all fields of the left and right relation types:

```java
List<Integer> leftJoinFields = new ArrayList<>();
List<Integer> rightJoinFields = new ArrayList<>();

// build phase: O(J)
for (Identifier column : columns) {
    leftJoinFields.add(leftField.getRelationFieldIndex());
    rightJoinFields.add(rightField.getRelationFieldIndex());
}

// output phase: O(C × J) -- for each field, scan the list
for (int i = 0; i < left.getRelationType().getAllFieldCount(); i++) {
    if (!leftJoinFields.contains(i)) {   // O(J) linear scan per field
        outputs.add(...); leftFields.add(i);
    }
}
for (int i = 0; i < right.getRelationType().getAllFieldCount(); i++) {
    if (!rightJoinFields.contains(i)) {  // O(J) linear scan per field
        outputs.add(...); rightFields.add(i);
    }
}
```

Where C = total column count across both sides, J = number of USING columns. For wide tables
(C large) with many join keys (J large), this degrades to O(C²) in the worst case.

## Fix

Replace `ArrayList<Integer>` with `HashSet<Integer>` for O(1) membership lookup. The lists are
only used for contains checks in the output phase; the ordering is not required for that.

```java
Set<Integer> leftJoinFields = new HashSet<>();
Set<Integer> rightJoinFields = new HashSet<>();

// build phase
for (Identifier column : columns) {
    leftJoinFields.add(leftField.getRelationFieldIndex());
    rightJoinFields.add(rightField.getRelationFieldIndex());
    joinFields.add(Field.newUnqualified(column.getValue(), type.get()));
    // ... other logic unchanged
}

// output phase: O(C) total
for (int i = 0; i < left.getRelationType().getAllFieldCount(); i++) {
    if (!leftJoinFields.contains(i)) {   // O(1) hash lookup
        outputs.add(left.getRelationType().getFieldByIndex(i));
        leftFields.add(i);
    }
}
for (int i = 0; i < right.getRelationType().getAllFieldCount(); i++) {
    if (!rightJoinFields.contains(i)) {  // O(1) hash lookup
        outputs.add(right.getRelationType().getFieldByIndex(i));
        rightFields.add(i);
    }
}
// Pass sets to JoinUsingAnalysis (also accepts Collection<Integer>)
analysis.setJoinUsing(node, new Analysis.JoinUsingAnalysis(
    ImmutableList.copyOf(leftJoinFields), ImmutableList.copyOf(rightJoinFields),
    leftFields.build(), rightFields.build()));
```

## Speedup

| C (columns) | J (join keys) | Before (ops) | After (ops) | Speedup |
|-------------|--------------|-------------|-------------|---------|
| 50 | 5 | 250 | 50 | 5× |
| 200 | 20 | 4,000 | 200 | 20× |
| 500 | 50 | 25,000 | 500 | 50× |
| 1,000 | 100 | 100,000 | 1,000 | 100× |
