# UNDF: UNDF-2026-000000543
# starrocks-0001: MaterializedViewRewriter.getTableToRelationid — List.contains in column-ref loop → O(N×T)

## Classification
- **Severity**: HIGH
- **CWE**: CWE-407 (Algorithmic Complexity — Inefficient Algorithmic Complexity)
- **Component**: `fe/fe-core/src/main/java/com/starrocks/sql/optimizer/rule/transformation/materialization/MaterializedViewRewriter.java`
- **Method**: `getTableToRelationid()`

## Defect

`getTableToRelationid()` iterates over every column-ref-to-table mapping in the `ColumnRefFactory`
(up to N entries for wide schemas) and calls `tableList.contains(entry.getValue())` where `tableList`
is the `List<Table>` parameter.

```java
private Map<Table, Set<Integer>> getTableToRelationid(
        OptExpression optExpression, ColumnRefFactory refFactory, List<Table> tableList) {
    ...
    for (Map.Entry<ColumnRefOperator, Table> entry : refFactory.getColumnRefToTable().entrySet()) {
        if (!tableList.contains(entry.getValue())) {   // <-- O(T) List.contains
            continue;
        }
        ...
    }
}
```

`List.contains()` is O(T) where T is the number of tables. The loop runs N times (one per column ref).
Total: **O(N × T)**.

The method is called **twice** per MV rewrite candidate — once for the query expression and once for
the MV expression (lines 2645 and 2656). MV rewrite is attempted for every applicable MV on every
query, so in workloads with many columns and multiple MVs this compounds quickly.

A production StarRocks deployment with 500 column refs and 20 candidate tables performs 10 000
list-scans per call, repeated for every MV candidate at query-compilation time.

## Root Cause

The caller (`rewrite()`/`generateRelationIdMap()`) has `List<Table> queryTables` / `mvTables` which
are passed directly to `getTableToRelationid`. The lists are never converted to sets before the call.

## Fix

Convert `tableList` to a `HashSet` once before the loop. Each `.contains()` becomes O(1).

```java
// Before:
if (!tableList.contains(entry.getValue())) {   // O(T) per iteration

// After:
Set<Table> tableSet = new HashSet<>(tableList); // O(T) once, before loop
...
if (!tableSet.contains(entry.getValue())) {     // O(1) per iteration
```

Alternatively, change the parameter type from `List<Table>` to `Set<Table>` and update callers to
pass `new HashSet<>(queryTables)` / `new HashSet<>(mvTables)`.

## Complexity

| Before | After |
|--------|-------|
| O(N × T) per call | O(N + T) per call |

With N=500 column refs, T=20 tables: Before = 10 000 comparisons. After = 520. **~19× reduction**.
Called twice per MV candidate; with 10 MVs = 200 000 → 10 400 comparisons total.

## Patch

```diff
--- a/fe/fe-core/src/main/java/com/starrocks/sql/optimizer/rule/transformation/materialization/MaterializedViewRewriter.java
+++ b/fe/fe-core/src/main/java/com/starrocks/sql/optimizer/rule/transformation/materialization/MaterializedViewRewriter.java
@@ -2777,9 +2777,11 @@ public class MaterializedViewRewriter {
     private Map<Table, Set<Integer>> getTableToRelationid(
             OptExpression optExpression, ColumnRefFactory refFactory, List<Table> tableList) {
         Map<Table, Set<Integer>> tableToRelationId = Maps.newHashMap();
         Set<ColumnRefOperator> validColumnRefs = MvUtils.collectScanColumn(optExpression);
+        // Convert to HashSet once — avoids O(T) List.contains per column-ref iteration
+        Set<Table> tableSet = new HashSet<>(tableList);
         for (Map.Entry<ColumnRefOperator, Table> entry : refFactory.getColumnRefToTable().entrySet()) {
-            if (!tableList.contains(entry.getValue())) {
+            if (!tableSet.contains(entry.getValue())) {
                 continue;
             }
```
