# UNDF: UNDF-2026-000000560
# trino-0001: PushDownDereferenceThroughJoin — List.contains in stream filter → O(N²)

## Classification
- **Severity**: HIGH
- **CWE**: CWE-407 (Algorithmic Complexity — Inefficient Algorithmic Complexity)
- **Component**: `core/trino-main/src/main/java/io/trino/sql/planner/iterative/rule/PushDownDereferenceThroughJoin.java`
- **Method**: `apply()`

## Defect

`PlanNode.getOutputSymbols()` returns `List<Symbol>`. In `apply()`, this list is searched with
`.contains()` (O(N)) in two distinct hot loops:

**Loop 1** (lines 127–139): `dereferenceAssignments.entrySet().forEach(entry -> { ... if (joinNode.getLeft().getOutputSymbols().contains(baseSymbol)) ... })`.
Each iteration re-invokes `getOutputSymbols()` returning the same List and calls `.contains()` on it — O(D × S) where D = dereference count, S = output symbol count.

**Loop 2** (lines 152–158): `referredSymbolsInAssignments.stream().filter(symbol -> leftNode.getOutputSymbols().contains(symbol))` and the mirrored right-side filter.
For each of R referred symbols, `.contains()` scans up to S symbols — O(R × S).

Both sides of the join are affected. In a wide JOIN with many projected columns and deep dereference chains (common in analytical queries over denormalized schemas), this rule runs repeatedly inside the iterative optimizer's rule-application loop, multiplying the cost.

**Affected lines**:
- Line 130: `joinNode.getLeft().getOutputSymbols().contains(baseSymbol)` — `List.contains` O(S)
- Line 133: `joinNode.getRight().getOutputSymbols().contains(baseSymbol)` — `List.contains` O(S)
- Line 153: `.filter(symbol -> leftNode.getOutputSymbols().contains(symbol))` — `List.contains` O(S) per symbol
- Line 157: `.filter(symbol -> rightNode.getOutputSymbols().contains(symbol))` — `List.contains` O(S) per symbol

## Root Cause

`PlanNode.getOutputSymbols()` is declared to return `List<Symbol>` (abstract method in
`PlanNode.java`). All concrete plan nodes return `ImmutableList<Symbol>`. The caller uses `.contains()`
for membership tests without first converting to a `Set`.

## Fix

Snapshot both output symbol lists as `ImmutableSet` before the loops. Each `ImmutableSet.copyOf()`
is O(S), paid once. All subsequent `.contains()` calls are O(1), reducing both loops to O(D) and O(R).

```java
// Before apply():
//   joinNode.getLeft().getOutputSymbols().contains(baseSymbol)   — O(S) per call
//   joinNode.getRight().getOutputSymbols().contains(baseSymbol)  — O(S) per call
//   leftNode.getOutputSymbols().contains(symbol)                  — O(S) per call
//   rightNode.getOutputSymbols().contains(symbol)                 — O(S) per call

// After (snapshot sets once before the loops):
Set<Symbol> leftSymbols  = ImmutableSet.copyOf(joinNode.getLeft().getOutputSymbols());
Set<Symbol> rightSymbols = ImmutableSet.copyOf(joinNode.getRight().getOutputSymbols());
// … use leftSymbols.contains / rightSymbols.contains in the forEach …

Set<Symbol> leftNodeSymbols  = ImmutableSet.copyOf(leftNode.getOutputSymbols());
Set<Symbol> rightNodeSymbols = ImmutableSet.copyOf(rightNode.getOutputSymbols());
// … use leftNodeSymbols.contains / rightNodeSymbols.contains in the stream filters …
```

## Complexity

| Before | After |
|--------|-------|
| O(D×S + R×S) per rule invocation | O(S + D + R) per rule invocation |

With D=50 dereferences, R=80 referred symbols, S=200 output symbols per side:
Before: ~26 000 list-scans. After: 400 operations. **65× reduction**.

## Patch

```diff
--- a/core/trino-main/src/main/java/io/trino/sql/planner/iterative/rule/PushDownDereferenceThroughJoin.java
+++ b/core/trino-main/src/main/java/io/trino/sql/planner/iterative/rule/PushDownDereferenceThroughJoin.java
@@ -120,9 +120,12 @@ public class PushDownDereferenceThroughJoin
         Assignments.Builder leftAssignmentsBuilder = Assignments.builder();
         Assignments.Builder rightAssignmentsBuilder = Assignments.builder();

+        // Snapshot output symbol sets O(S) once — avoids O(S) List.contains per entry
+        Set<Symbol> leftOutputSet  = ImmutableSet.copyOf(joinNode.getLeft().getOutputSymbols());
+        Set<Symbol> rightOutputSet = ImmutableSet.copyOf(joinNode.getRight().getOutputSymbols());
+
         // Separate dereferences coming from left and right nodes
         dereferenceAssignments.entrySet()
                 .forEach(entry -> {
                     Symbol baseSymbol = getOnlyElement(extractAll(entry.getValue()));
-                    if (joinNode.getLeft().getOutputSymbols().contains(baseSymbol)) {
+                    if (leftOutputSet.contains(baseSymbol)) {
                         leftAssignmentsBuilder.put(entry.getKey(), entry.getValue());
                     }
-                    else if (joinNode.getRight().getOutputSymbols().contains(baseSymbol)) {
+                    else if (rightOutputSet.contains(baseSymbol)) {
                         rightAssignmentsBuilder.put(entry.getKey(), entry.getValue());
                     }

@@ -140,10 +144,13 @@ public class PushDownDereferenceThroughJoin
         PlanNode leftNode  = createProjectNodeIfRequired(joinNode.getLeft(),  leftAssignments,  context.getIdAllocator());
         PlanNode rightNode = createProjectNodeIfRequired(joinNode.getRight(), rightAssignments, context.getIdAllocator());

+        // Snapshot post-project output sets O(S) once
+        Set<Symbol> leftNodeSet  = ImmutableSet.copyOf(leftNode.getOutputSymbols());
+        Set<Symbol> rightNodeSet = ImmutableSet.copyOf(rightNode.getOutputSymbols());
+
         // Prepare new output symbols for join node
         List<Symbol> referredSymbolsInAssignments = newAssignments.expressions().stream()
                 .flatMap(expression -> extractAll(expression).stream())
                 .collect(toList());

         List<Symbol> newLeftOutputSymbols = referredSymbolsInAssignments.stream()
-                .filter(symbol -> leftNode.getOutputSymbols().contains(symbol))
+                .filter(leftNodeSet::contains)
                 .collect(toList());

         List<Symbol> newRightOutputSymbols = referredSymbolsInAssignments.stream()
-                .filter(symbol -> rightNode.getOutputSymbols().contains(symbol))
+                .filter(rightNodeSet::contains)
                 .collect(toList());
```
