# DuckDB — CWE-407 Disclosure Brief
**2026-03-27 · Patch available — awaiting upstream merge**

## Finding

One O(n²) defect in DuckDB's correlated subquery optimizer. `CorrelatedColumns::AddCorrelatedColumn()` uses `std::find` for deduplication, causing O(n²) total cost in `MergeCorrelatedColumns()` during correlated subquery planning. Patch ready for upstream review.

## The Defects

**duckdb-0001 (PATCHED — HIGH):** `src/optimizer/`

```cpp
// Inside CorrelatedColumns::AddCorrelatedColumn() — per merge call:
auto it = std::find(correlated_columns.begin(),
                    correlated_columns.end(),
                    col);
// O(n) per add; O(n²) in MergeCorrelatedColumns()
if (it == correlated_columns.end()) {
    correlated_columns.push_back(col);
}
```

`std::find` O(n) dedup scan per `AddCorrelatedColumn()` call. `MergeCorrelatedColumns()` calls this for every column in every correlated set: **O(n²) total**. Fix: `column_binding_set_t` shadow set.

## Complexity Proof

For N correlated columns across a subquery:
- `AddCorrelatedColumn()` called N times
- Each call: O(N) `std::find` scan
- Total: O(N²) in `MergeCorrelatedColumns()`

Fix: maintain a `column_binding_set_t` shadow set alongside the vector:
- Each `add`: O(1) set membership check
- Overall: O(N) instead of O(N²)

## Impact

All DuckDB deployments running queries with correlated subqueries — `EXISTS`, `IN (subquery)`, and correlated `WHERE` clauses. DuckDB is a widely used in-process analytical database used in data science workflows, Python analytics (polars, pandas alternatives), and embedded analytics. Complex analytical queries with many correlated columns hit O(N²) during subquery optimization.

## The Fix

Add a `column_binding_set_t` shadow set alongside `correlated_columns`:

```cpp
// Before
auto it = std::find(correlated_columns.begin(),
                    correlated_columns.end(), col);
if (it == correlated_columns.end()) {
    correlated_columns.push_back(col);
}

// After
// CWE-407 fix: column_binding_set_t shadow for O(1) dedup instead of O(n) std::find.
if (correlated_columns_set.insert(col).second) {
    correlated_columns.push_back(col);
}
```

## Patch

`defects/duckdb/patch/duckdb-0001-correlated-columns-set.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
2. Validate the patch against your optimizer and correlated subquery test suite.
3. Assess CVE eligibility — fires during correlated subquery planning with many columns.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

Contact: see cover email. This brief is confidential until coordinated disclosure.
