# UNDF: UNDF-2026-000000178
# mysql-0004 — `dict_index_find_and_set_cols`: O(F²) linear dedup in InnoDB index field validation

## Status
PATCHED

## Severity
MEDIUM (>50× speedup at F=200 index fields; called at server startup and every CREATE INDEX / ALTER TABLE)

## Location
`storage/innobase/dict/dict0dict.cc`, function `dict_index_find_and_set_cols()`

## Description
`dict_index_find_and_set_cols()` resolves the column objects for each field of
an InnoDB index and detects duplicate column names. It maintains two `std::vector`
accumulators — `col_added` and `v_col_added` — and for each index field calls
`std::find` on the growing vector to detect duplicates:

```cpp
std::vector<ulint, ut::allocator<ulint>> col_added;
std::vector<ulint, ut::allocator<ulint>> v_col_added;

for (ulint i = 0; i < index->n_fields; i++) {
    ...
    for (j = 0; j < table->n_cols; j++) {
        if (!strcmp(table->get_col_name(j), field->name)) {
            /* O(|col_added|) scan on every match */
            bool exists = std::find(col_added.begin(), col_added.end(), j)
                          != col_added.end();
            if (exists)
                goto dup_err;
            col_added.push_back(j);   /* col_added grows */
            goto found;
        }
    }
    /* Same pattern for virtual columns with v_col_added */
    for (j = 0; j < table->n_v_cols; j++) {
        if (!strcmp(...)) {
            bool exists = std::find(v_col_added.begin(), v_col_added.end(), j)
                          != v_col_added.end();
            ...
            v_col_added.push_back(j);
        }
    }
}
```

With F regular-column index fields, `col_added` grows from 0 to F entries.
Each push is preceded by a scan of length 0, 1, 2, ..., F-1:
total = **O(F²)** comparisons.

The fix replaces both vectors with `std::unordered_set<ulint>`, turning each
`std::find` into an O(1) hash lookup: total **O(F)**.

### Hot path
`dict_index_find_and_set_cols()` is called from `dict_index_add_to_cache_w_vcol()`
which is called:
- **At server startup**: for every index of every InnoDB table loaded into the
  dictionary cache.
- **At DDL time**: `CREATE INDEX`, `ALTER TABLE ADD INDEX`, `CREATE TABLE`.

With F=200 (a 200-column covering index on a wide table), O(F²) = 40,000
comparisons per index. On a server with 10,000 indexes at startup, this
accumulates to 400M extra comparisons.

### Complexity table

| F (index fields) | Defective ops (O(F²)) | Fixed ops (O(F)) | Ratio |
|------------------|-----------------------|------------------|-------|
| 10               | 45                    | 10               | 4.5×  |
| 50               | 1,225                 | 50               | 24.5× |
| 100              | 4,950                 | 100              | 49.5× |
| 200              | 19,900                | 200              | 99.5× |

## Patch

```cpp
--- a/storage/innobase/dict/dict0dict.cc
+++ b/storage/innobase/dict/dict0dict.cc
@@ -2741,8 +2741,15 @@ static bool dict_index_find_and_set_cols(const dict_table_t *table,
                                          dict_index_t *index,
                                          const dict_add_v_col_t *add_v) {
-  std::vector<ulint, ut::allocator<ulint>> col_added;
-  std::vector<ulint, ut::allocator<ulint>> v_col_added;
+  /*
+   * CWE-407 fix (mysql-0004): replace linear-scan vectors with hash sets so
+   * duplicate-column detection is O(1) per field instead of O(|col_added|).
+   * Old code: O(F²) total for F-field index.
+   * New code: O(F) total.
+   */
+  std::unordered_set<ulint> col_added;
+  std::unordered_set<ulint> v_col_added;

   ...

@@ -2757,7 +2757,7 @@ static bool dict_index_find_and_set_cols(...) {
       if (!strcmp(table->get_col_name(j), field->name)) {
-        bool exists =
-            std::find(col_added.begin(), col_added.end(), j) != col_added.end();
+        bool exists = col_added.count(j) > 0;   /* O(1) hash lookup */
         if (exists) {
           goto dup_err;
         }
         field->col = table->get_col(j);
-        col_added.push_back(j);
+        col_added.insert(j);
         goto found;

@@ -2775,8 +2775,7 @@ static bool dict_index_find_and_set_cols(...) {
       if (!strcmp(dict_table_get_v_col_name(table, j), field->name)) {
-        bool exists = std::find(v_col_added.begin(), v_col_added.end(), j) !=
-                      v_col_added.end();
+        bool exists = v_col_added.count(j) > 0;  /* O(1) hash lookup */
         if (exists) {
           break;
         }
         ...
-        v_col_added.push_back(j);
+        v_col_added.insert(j);
```

## Speedup
At F=200 index fields (all distinct):
- Defective: 0+1+...+199 = 19,900 comparison ops
- Fixed: 200 hash lookup ops
- **Ratio: 99.5× speedup**

## Test
`defects/mysql/unit/MysqlTest.java` — `mysql-0004` section.
