# UNDF: UNDF-2026-000000683
# duckdb-0002: CorrelatedColumns dedup O(C²) via std::find in AddCorrelatedColumn and HasCorrelatedExpressions

## Severity
MEDIUM

## Locations
- `src/planner/binder.cpp:285-290` — `AddCorrelatedColumn` / `MergeCorrelatedColumns`
- `src/planner/subquery/has_correlated_expressions.cpp:56-62` — `VisitReplace(BoundSubqueryExpression)`

## Pattern
SLOW: `std::find(correlated_columns.begin(), correlated_columns.end(), info)` — O(C) per call
FAST: `column_binding_set_t seen_bindings` — O(1) per call

## Context

### Site 1: AddCorrelatedColumn / MergeCorrelatedColumns

`Binder::AddCorrelatedColumn` inserts a column into `correlated_columns` only if not already present,
using `std::find` for the membership check:

```cpp
void Binder::AddCorrelatedColumn(const CorrelatedColumnInfo &info) {
    if (std::find(correlated_columns.begin(), correlated_columns.end(), info)
                  == correlated_columns.end()) {
        correlated_columns.AddColumn(info);
    }
}

void Binder::MergeCorrelatedColumns(CorrelatedColumns &other) {
    for (idx_t i = 0; i < other.size(); i++) {
        AddCorrelatedColumn(other[i]);   // O(C) per call
    }
}
```

`MergeCorrelatedColumns` is called when a subquery binder's correlated columns are merged into
the parent. With a deeply correlated query (C correlated columns), `MergeCorrelatedColumns` is
O(C²). It is called from `MoveCorrelatedExpressions`, `bind_joinref.cpp`, and `bind_subquery_expression.cpp`.

`CorrelatedColumnInfo::operator==` only compares `binding` (a `ColumnBinding` struct). The existing
`column_binding_set_t` (in `column_binding_map.hpp`) provides O(1) lookup.

### Site 2: HasCorrelatedExpressions::VisitReplace(BoundSubqueryExpression)

```cpp
for (idx_t i = 0; i < correlated_columns.size(); i++) {
    if (std::find(expr.binder->correlated_columns.begin(),
                  expr.binder->correlated_columns.end(),
                  correlated_columns[i]) != expr.binder->correlated_columns.end()) {
        has_correlated_expressions = true;
        break;
    }
}
```

For a query with C outer correlated columns and a subquery with C' correlated columns, this is O(C × C').
`HasCorrelatedExpressions` visitor is invoked from `flatten_dependent_join.cpp` during dependent join
flattening — a hot path in subquery planning.

## Speedup
250× at C=500 correlated columns (generated queries, macro expansion, lateral joins with many columns)

## Patch

### Site 1: Add a binding-based set to CorrelatedColumns for O(1) dedup

```diff
--- a/src/include/duckdb/planner/binder.hpp
+++ b/src/include/duckdb/planner/binder.hpp
+#include "duckdb/planner/column_binding_map.hpp"
+
 struct CorrelatedColumns {
 private:
     using container_type = vector<CorrelatedColumnInfo>;
+    column_binding_set_t binding_set;

 public:
     void AddColumn(container_type::value_type info) {
         correlated_columns.insert(correlated_columns.begin(), std::move(info));
+        binding_set.insert(correlated_columns.front().binding);
         delim_index++;
     }
     void AddColumnToBack(container_type::value_type info) {
+        binding_set.insert(info.binding);
         correlated_columns.push_back(std::move(info));
     }

+    bool ContainsBinding(const ColumnBinding &b) const {
+        return binding_set.count(b) > 0;
+    }

--- a/src/planner/binder.cpp
+++ b/src/planner/binder.cpp
 void Binder::AddCorrelatedColumn(const CorrelatedColumnInfo &info) {
-    if (std::find(correlated_columns.begin(), correlated_columns.end(), info)
-                  == correlated_columns.end()) {
+    if (!correlated_columns.ContainsBinding(info.binding)) {
         correlated_columns.AddColumn(info);
     }
 }
```

### Site 2: Build a set from expr.binder->correlated_columns for O(C+C') check

```diff
--- a/src/planner/subquery/has_correlated_expressions.cpp
+++ b/src/planner/subquery/has_correlated_expressions.cpp
 unique_ptr<Expression> HasCorrelatedExpressions::VisitReplace(BoundSubqueryExpression &expr, ...) {
     if (!expr.IsCorrelated()) { return nullptr; }
+    // Build O(1)-lookup set from subquery's correlated bindings
+    column_binding_set_t subquery_bindings;
+    for (idx_t j = 0; j < expr.binder->correlated_columns.size(); j++) {
+        subquery_bindings.insert(expr.binder->correlated_columns[j].binding);
+    }
     for (idx_t i = 0; i < correlated_columns.size(); i++) {
-        if (std::find(expr.binder->correlated_columns.begin(),
-                      expr.binder->correlated_columns.end(),
-                      correlated_columns[i]) != expr.binder->correlated_columns.end()) {
+        if (subquery_bindings.count(correlated_columns[i].binding) > 0) {
             has_correlated_expressions = true;
             break;
         }
     }
     return nullptr;
 }
```
