# UNDF: UNDF-2026-000000381
# doris-0001: BindExpression.processNonStandardAggregate — List.contains per projection → O(P×G)

## Classification
- **Severity**: MEDIUM
- **CWE**: CWE-407 (Algorithmic Complexity — Inefficient Algorithmic Complexity)
- **Component**: `fe/fe-core/src/main/java/org/apache/doris/nereids/rules/analysis/BindExpression.java`
- **Method**: `processNonStandardAggregate()`

## Defect

`processNonStandardAggregate()` accepts `Collection<Expression> groupingExprs`. It is called from
two sites:

- Line 1401: `processNonStandardAggregate(boundProjections, boundGroupBy)` where `boundGroupBy` is
  a `List<Expression>` (built by `ImmutableList.Builder` in `bindGroupBy()`).
- Line 1578: `processNonStandardAggregate(boundOutput, flatBoundGroupingSet)` where
  `flatBoundGroupingSet` is a `Set<Expression>` — this call is safe.

For the first (List) call-site:

```java
for (NamedExpression projection : originalProjections) {   // P projections
    if (projection instanceof SlotReference && !groupingExprs.contains(projection)) {  // O(G) List scan
        ...
    }
}
```

Each of P projections calls `groupingExprs.contains()` which is O(G) for a `List`. Total: **O(P × G)**.

In non-FULL_GROUP_BY SQL mode (MySQL-compatible mode), this code path is taken for every aggregate
query. Wide SELECT lists with many GROUP BY keys degrade quadratically.

## Root Cause

`bindGroupBy()` returns `List<Expression>`. The result is passed directly to
`processNonStandardAggregate()` without converting to a `Set`. The `Collection<>` parameter type
masks the problem at the call site.

## Fix

Wrap `groupingExprs` in a `HashSet` at the start of `processNonStandardAggregate()` when it is not
already a `Set`, or tighten the API to accept `Set<Expression>` and update call sites.

Option A (minimal, defensive):
```java
private List<NamedExpression> processNonStandardAggregate(
        List<NamedExpression> originalProjections, Collection<Expression> groupingExprs) {
    if (SqlModeHelper.hasOnlyFullGroupBy()) {
        return originalProjections;
    }
    // Ensure O(1) membership: convert to Set if caller passed a List
    Set<Expression> groupingSet = (groupingExprs instanceof Set)
            ? (Set<Expression>) groupingExprs
            : new HashSet<>(groupingExprs);
    ImmutableList.Builder<NamedExpression> finalProjectionsBuilder = ImmutableList.builder();
    for (NamedExpression projection : originalProjections) {
        if (projection instanceof SlotReference && !groupingSet.contains(projection)) {
            finalProjectionsBuilder.add(new Alias(projection, projection.getName()));
        } else {
            finalProjectionsBuilder.add(projection);
        }
    }
    return finalProjectionsBuilder.build();
}
```

## Complexity

| Before | After |
|--------|-------|
| O(P × G) | O(P + G) |

With P=50 projections, G=40 group-by keys: Before = 2 000 comparisons. After = 90. **~22× reduction**.

## Patch

```diff
--- a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/analysis/BindExpression.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/analysis/BindExpression.java
@@ -1598,9 +1598,13 @@ public class BindExpression extends OneRewriteRuleFactory {
     private List<NamedExpression> processNonStandardAggregate(
             List<NamedExpression> originalProjections, Collection<Expression> groupingExprs) {
         if (SqlModeHelper.hasOnlyFullGroupBy()) {
             return originalProjections;
         } else {
+            // Ensure O(1) membership — callers may pass List<Expression>
+            Set<Expression> groupingSet = (groupingExprs instanceof Set)
+                    ? (Set<Expression>) groupingExprs
+                    : new HashSet<>(groupingExprs);
             ImmutableList.Builder<NamedExpression> finalProjectionsBuilder = ImmutableList.builder();
             for (NamedExpression projection : originalProjections) {
                 // we do a trick here
-                if (projection instanceof SlotReference && !groupingExprs.contains(projection)) {
+                if (projection instanceof SlotReference && !groupingSet.contains(projection)) {
                     finalProjectionsBuilder.add(new Alias(projection, projection.getName()));
                 } else {
                     finalProjectionsBuilder.add(projection);
```
