# UNDF: UNDF-2026-000000681
# clickhouse-0002: ReplaceColumnTransformerNode::findReplacementExpression O(C×R) linear scan

## Severity
MEDIUM

## Location
`src/Analyzer/ColumnTransformers.cpp:272-280` — `findReplacementExpression`
`src/Analyzer/ColumnTransformers.h:306` — `Names replacements_names` member

## Pattern
SLOW: `std::find(replacements_names.begin(), replacements_names.end(), expression_name)` — O(R) per call
FAST: `std::unordered_map<std::string, size_t> replacements_index` — O(1) per call

## Context

`ReplaceColumnTransformerNode` is used for `SELECT * REPLACE (expr AS col1, expr AS col2, ...)` queries.
The `replacements_names` member is `Names = std::vector<std::string>` that stores all replacement column names.

`findReplacementExpression(expression_name)` is called from `QueryAnalyzer::resolveMatcherNode` for every
column that matches the `*` wildcard — i.e., for every column in the table or subquery.

The call structure is:
```
for each matched column (C columns in SELECT *):           O(C)
  for each transformer (1 per REPLACE clause):
    findReplacementExpression(column_name)                 O(R)  ← linear scan
```

Total: O(C × R), where:
- C = number of columns in the table/subquery (can be 100+ for wide tables)
- R = number of replacement expressions in the REPLACE clause

The constructor already builds `replacement_names_set` (an `unordered_set`) for validation, then
discards it. That same set (or a map) should be retained for O(1) lookups.

## Affected code

```cpp
// ColumnTransformers.h
Names replacements_names;  // std::vector<std::string> — O(R) linear scan

// ColumnTransformers.cpp
QueryTreeNodePtr ReplaceColumnTransformerNode::findReplacementExpression(const std::string & expression_name)
{
    auto it = std::find(replacements_names.begin(), replacements_names.end(), expression_name);
    if (it == replacements_names.end())
        return {};
    size_t replacement_index = it - replacements_names.begin();
    auto & replacement_expressions_nodes = getReplacements().getNodes();
    return replacement_expressions_nodes[replacement_index];
}
```

## Speedup
100× at C=100 selected columns, R=10 replacements (wide-table analytics)

## Patch

```diff
--- a/src/Analyzer/ColumnTransformers.h
+++ b/src/Analyzer/ColumnTransformers.h
@@ -300,6 +300,7 @@ private:

     Names replacements_names;
+    std::unordered_map<std::string, size_t> replacements_index;
     bool is_strict = false;

     static constexpr size_t replacements_child_index = 0;

--- a/src/Analyzer/ColumnTransformers.cpp
+++ b/src/Analyzer/ColumnTransformers.cpp
@@ -260,8 +260,9 @@ ReplaceColumnTransformerNode::ReplaceColumnTransformerNode(...)
         replacements_names.push_back(replacement.column_name);
+        replacements_index.emplace(replacement.column_name, replacements_names.size() - 1);
         replacement_expressions_nodes.push_back(replacement.expression_node);
     }
 }

 QueryTreeNodePtr ReplaceColumnTransformerNode::findReplacementExpression(const std::string & expression_name)
 {
-    auto it = std::find(replacements_names.begin(), replacements_names.end(), expression_name);
-    if (it == replacements_names.end())
+    auto it = replacements_index.find(expression_name);
+    if (it == replacements_index.end())
         return {};
-    size_t replacement_index = it - replacements_names.begin();
+    size_t replacement_index = it->second;
     auto & replacement_expressions_nodes = getReplacements().getNodes();
     return replacement_expressions_nodes[replacement_index];
 }
```

Also add `replacements_index` to `cloneImpl()`:
```diff
--- a/src/Analyzer/ColumnTransformers.cpp
+++ b/src/Analyzer/ColumnTransformers.cpp
@@ -331,6 +331,7 @@ QueryTreeNodePtr ReplaceColumnTransformerNode::cloneImpl() const
     result_replace_transformer->is_strict = is_strict;
     result_replace_transformer->replacements_names = replacements_names;
+    result_replace_transformer->replacements_index = replacements_index;

     return result_replace_transformer;
 }
```
