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

## Finding

Two O(n²) defects in MariaDB's query optimizer. Both fire during query planning phase. Patches ready for upstream review.

## The Defects

**mariadb-0001 (PATCHED — HIGH):** `sql/sql_select.cc`

```cpp
// find_item_in_list() — called in setup_order() and setup_group():
// O(O×S) per ORDER item in setup_order()/setup_group()
for (Item **item = fields->begin(); item != fields->end(); ++item) {
    if ((*item)->eq(find, true)) { ... }  // O(S) scan per ORDER item
}
// Called O(O) times: O(O²) total at query plan
```

`find_item_in_list()` scans the field list for each ORDER BY / GROUP BY item. For O order items and S select items: **O(O × S)**. With O ≈ S: **O(O²)**. **Measured ratio: 125×.**

**mariadb-0002 (PATCHED — HIGH):** `sql/sql_select.cc`

```cpp
// find_item_in_list() called in setup_new_fields():
// O(N×S) per new field in field setup
for (Item **item = field_list->begin(); item != field_list->end(); ++item) {
    if ((*item)->eq(find, true)) { ... }  // O(S) scan per new field
}
// Called O(N) times: O(N×S) total
```

`find_item_in_list()` O(S) scan per new field in `setup_new_fields()`. **O(N × S) total at query planning**. Fix: `unordered_map`. PATCHED.

## Complexity Proof

For O=125 ORDER BY items, S=125 SELECT items:
- O(O×S) = 15,625 comparisons per query plan
- Fixed: pre-built `item_name → item*` map → O(O + S)
- **125× measured ratio.**

**mariadb-0002:** For N new fields and S field list entries:
- Per new field: O(S) `find_item_in_list()` scan
- Total: **O(N × S)** — fixed: `unordered_map<name, Item*>`.

## Impact

All MariaDB deployments running queries with ORDER BY or GROUP BY on many columns — reporting queries, analytics, complex joins. mariadb-0001 fires in `setup_order()`/`setup_group()` for every such query. mariadb-0002 fires in `setup_new_fields()` during query planning for queries that add new fields to an existing field list. MariaDB is a widely deployed open-source relational database used as a MySQL replacement. Reporting workloads with many-column sorts hit both defects on every query plan.

## The Fix

Pre-build a name-indexed map before the ORDER BY scan:

```cpp
// Before
for (Item **item = fields->begin(); item != fields->end(); ++item) {
    if ((*item)->eq(find, true)) { ... }  // O(S) per ORDER item
}

// After
// CWE-407 fix: unordered_map<name, Item*> for O(1) lookup instead of O(S) scan.
std::unordered_map<std::string, Item*> fields_map;
for (Item **item = fields->begin(); item != fields->end(); ++item)
    fields_map[(*item)->full_name()] = *item;
// Then: fields_map[find->full_name()] — O(1)
```

**mariadb-0002:** Pre-build `unordered_map<string, Item*>` in `setup_new_fields()` before the field scan loop.

## Patch

`defects/mariadb/patch/mariadb-0001-setup-order-map.patch`
`defects/mariadb/patch/mariadb-0002-setup-new-fields-map.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or JIRA reference.
2. Validate the patch against your query planning and ORDER BY test suite.
3. Assess CVE eligibility — fires on every query with many ORDER BY / GROUP BY items.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

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