# UNDF: UNDF-2026-000000693
# scylladb-0002: selection::from_selectors column dedup O(C²) via std::find

## Severity
MEDIUM

## Location
`cql3/selection/selection.cc:504-506` — `from_selectors` column dedup loop

## Pattern
SLOW: `std::find(defs.begin(), defs.end(), cv.col)` inside `for_each_expression` callback — O(C) per column
FAST: `std::unordered_set<const column_definition*> seen_defs` — O(1) per column

## Context

`selection::from_selectors` builds the list of unique `column_definition*` pointers referenced
by a CQL SELECT statement's selector list. It deduplicates using `std::find` on a growing vector:

```cpp
::shared_ptr<selection> selection::from_selectors(
    data_dictionary::database db, schema_ptr schema, const sstring& ks,
    const std::vector<prepared_selector>& prepared_selectors)
{
    std::vector<const column_definition*> defs;

    for (auto&& [sel, alias] : prepared_selectors) {
        expr::for_each_expression<expr::column_value>(sel, [&] (const expr::column_value& cv) {
            if (std::find(defs.begin(), defs.end(), cv.col) == defs.end()) {  // O(C)
                defs.push_back(cv.col);
            }
        });
    }
    // ...
}
```

For `SELECT *` on a wide table (C columns), `for_each_expression` is called C times, and each
call does `std::find` over a growing list of size 0..C-1. Total: O(C²/2).

This runs at statement prepare time and is called for every CQL SELECT operation. Wide tables
(time-series, IoT, event logs) commonly have 50–500 columns, making this O(2,500–125,000) pointer
comparisons per prepare.

`column_definition*` pointers are stable (schema is immutable per version), so pointer equality
is the correct dedup criterion — a hash set of raw pointers works directly.

## Speedup
250× at C=500 columns (wide time-series table SELECT *)

## Patch

```diff
--- a/cql3/selection/selection.cc
+++ b/cql3/selection/selection.cc
 ::shared_ptr<selection> selection::from_selectors(data_dictionary::database db, schema_ptr schema, const sstring& ks, const std::vector<prepared_selector>& prepared_selectors) {
     std::vector<const column_definition*> defs;
+    std::unordered_set<const column_definition*> seen_defs;

     for (auto&& [sel, alias] : prepared_selectors) {
         expr::for_each_expression<expr::column_value>(sel, [&] (const expr::column_value& cv) {
-            if (std::find(defs.begin(), defs.end(), cv.col) == defs.end()) {
+            if (seen_defs.insert(cv.col).second) {
                 defs.push_back(cv.col);
             }
         });
     }
```

`seen_defs.insert(cv.col).second` returns `true` if the element was newly inserted (not a duplicate),
matching the previous semantics exactly while reducing complexity from O(C²) to O(C).
