UNDF: UNDF-2026-000000177

mysql-0003 — `setup_fields()`: O(F²) std::find iterator recovery inside item loop

Status

PATCHED

Severity

MEDIUM (conditional path — only triggers when split_sum_func fires; bounded in practice to aggregate-heavy queries with wide SELECT lists)

Location

sql/sql_base.cc, function setup_fields(), line ~9496

Description

setup_fields iterates over the fields deque (size F) to fix and resolve each Item. After calling item->split_sum_func(...), the deque may grow (new items appended), invalidating the range-based iterator it. The current recovery code is:

if (old_size != fields->size()) {
    it = std::find(fields->begin(), fields->end(), item);
}

std::find performs an O(F) linear scan to rediscover the current item's position. In a query with F columns where every column has an aggregate that triggers split_sum_func, this recovery fires F times, each scanning O(F) elements — O(F²) total.

Fix

Replace the std::find recovery with an index-based approach: replace the range-for with an explicit index loop. After split_sum_func fires, the new items are always appended to the end, so the current item's physical position is unchanged — we only need to update the end sentinel. With an index loop, no re-scan is necessary.

// Replace:
for (auto it = fields->begin(); it != fields->end(); ++it) {
    ...
    if (old_size != fields->size()) {
        it = std::find(fields->begin(), fields->end(), item);  // O(F)
    }
}

// With:
for (size_t idx = 0; idx < fields->size(); ++idx) {
    Item *item = (*fields)[idx];
    // split_sum_func may append to fields; idx stays valid because
    // mem_root_deque is stable for existing indices after push_back.
    // No re-scan needed.
}

Patch file

See mysql-0003-setup-fields-find.patch

1.8 KiB Raw Permalink Blame History