# UNDF: UNDF-2026-000000696
# doris-0004: NormalizeRepeat.buildContextWithAlias — List.contains O(S×G) for GROUPING SETS

## Classification
- **CWE**: CWE-407 (Inefficient Algorithmic Complexity)
- **Severity**: MEDIUM
- **Component**: Apache Doris — `fe-core` (Nereids optimizer)
- **File**: `fe/fe-core/src/main/java/org/apache/doris/nereids/rules/analysis/NormalizeRepeat.java`
- **Method**: `buildContextWithAlias(Repeat, Map, Collection)`
- **Complexity**: O(S × G) where S = sourceExpressions count, G = total flattened grouping-set expressions

## Description

`buildContextWithAlias` normalizes expressions in a `GROUPING SETS`, `ROLLUP`, or `CUBE`
query by checking whether each source expression appears in the list of grouping set
expressions. The check uses `groupingSetExpressions.contains(expression)`, where
`groupingSetExpressions` is an `ImmutableList` returned by
`ExpressionUtils.flatExpressions(repeat.getGroupingSets())`.

`ImmutableList.contains()` performs a linear O(N) scan. It is called once per element in
`sourceExpressions`, giving O(S × G) total operations.

`CUBE(c1..c10)` generates 2^10 = 1,024 grouping sets; `flatExpressions` flattens them
into ~5,120 entries. For a query with 50 output expressions, this is O(50 × 5,120) =
O(256,000) comparisons per query.

## Defect Code

```java
// fe/fe-core/src/main/java/org/apache/doris/nereids/rules/analysis/NormalizeRepeat.java
private static NormalizeToSlotContext buildContextWithAlias(
        Repeat<? extends Plan> repeat,
        Map<Expression, Alias> existsAliasMap,
        Collection<? extends Expression> sourceExpressions) {

    List<Expression> groupingSetExpressions =
            ExpressionUtils.flatExpressions(repeat.getGroupingSets());   // ImmutableList — O(G) scan below

    Map<Expression, NormalizeToSlotTriplet> normalizeToSlotMap = Maps.newLinkedHashMap();
    for (Expression expression : sourceExpressions) {
        Optional<NormalizeToSlotTriplet> pushDownTriplet;
        if (groupingSetExpressions.contains(expression)) {               // O(G) per iteration → O(S×G) total
            pushDownTriplet = toGroupingSetExpressionPushDownTriplet(expression, existsAliasMap.get(expression));
        } else {
            pushDownTriplet = Optional.of(
                    NormalizeToSlotTriplet.toTriplet(expression, existsAliasMap.get(expression)));
        }
        pushDownTriplet.ifPresent(
                normalizeToSlotTriplet -> normalizeToSlotMap.put(expression, normalizeToSlotTriplet));
    }
    return new NormalizeToSlotContext(normalizeToSlotMap);
}
```

## Fix

Convert `groupingSetExpressions` to a `Set` before the loop to get O(1) lookup:

```java
private static NormalizeToSlotContext buildContextWithAlias(
        Repeat<? extends Plan> repeat,
        Map<Expression, Alias> existsAliasMap,
        Collection<? extends Expression> sourceExpressions) {

    // Use a Set for O(1) membership test instead of O(G) ImmutableList scan
    Set<Expression> groupingSetExpressions =
            new HashSet<>(ExpressionUtils.flatExpressions(repeat.getGroupingSets()));

    Map<Expression, NormalizeToSlotTriplet> normalizeToSlotMap = Maps.newLinkedHashMap();
    for (Expression expression : sourceExpressions) {
        Optional<NormalizeToSlotTriplet> pushDownTriplet;
        if (groupingSetExpressions.contains(expression)) {               // O(1)
            pushDownTriplet = toGroupingSetExpressionPushDownTriplet(expression, existsAliasMap.get(expression));
        } else {
            pushDownTriplet = Optional.of(
                    NormalizeToSlotTriplet.toTriplet(expression, existsAliasMap.get(expression)));
        }
        pushDownTriplet.ifPresent(
                normalizeToSlotTriplet -> normalizeToSlotMap.put(expression, normalizeToSlotTriplet));
    }
    return new NormalizeToSlotContext(normalizeToSlotMap);
}
```

## Patch

```diff
--- a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/analysis/NormalizeRepeat.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/analysis/NormalizeRepeat.java
@@ -297,8 +297,8 @@ public class NormalizeRepeat extends OneAnalysisRuleFactory {
         Map<Expression, Alias> existsAliasMap,
         Collection<? extends Expression> sourceExpressions) {

-        List<Expression> groupingSetExpressions = ExpressionUtils.flatExpressions(repeat.getGroupingSets());
+        // Use HashSet for O(1) contains; ImmutableList.contains is O(G) per call → O(S×G) total
+        Set<Expression> groupingSetExpressions =
+                new HashSet<>(ExpressionUtils.flatExpressions(repeat.getGroupingSets()));

         Map<Expression, NormalizeToSlotTriplet> normalizeToSlotMap = Maps.newLinkedHashMap();
         for (Expression expression : sourceExpressions) {
```

## Complexity Comparison

| Query | groupingSets G (flattened) | sourceExprs S | Old O(S×G) | New O(G+S) |
|-------|---------------------------|---------------|-----------|-----------|
| ROLLUP(c1..c5) | 15 | 20 | 300 | 35 |
| CUBE(c1..c5) | 160 | 20 | 3,200 | 180 |
| CUBE(c1..c8) | 2,048 | 50 | 102,400 | 2,098 |
| CUBE(c1..c10) | 10,240 | 100 | 1,024,000 | 10,340 |

At CUBE(c1..c8): **49x** speedup.

## Hot Path

Called during Nereids query analysis (`NormalizeRepeat` rule) for every `GROUPING SETS`,
`ROLLUP`, or `CUBE` query. Executed once per query, but for analytics workloads with many
concurrent CUBE queries this becomes the bottleneck.
