UNDF: UNDF-2026-000000219

postgresql-0007 — `add_new_columns_to_pathtarget`: O(E·T) list_member scan inside loop

Status

PATCHED

Severity

HIGH (>10× speedup at E=T=500)

Location

src/backend/optimizer/util/tlist.c, function add_new_columns_to_pathtarget() and its leaf add_new_column_to_pathtarget()

Description

add_new_columns_to_pathtarget iterates over exprs (E items) and for each calls add_new_column_to_pathtarget, which calls list_member(target->exprs, expr) — a full O(T) linear scan using structural equal() over all T existing PathTarget expressions.

Total cost: O(E·T), same pattern as postgresql-0006 but operating on a PathTarget rather than a flat tlist.

Hot callers (from planner.c)

make_group_input_target()   line 5688
make_partial_grouping_target()  line 5774
make_window_input_target()  line 6330, 6632

All are called during the grouping/window-function planning phase of every aggregated query.

Patch (conceptual — C)

Before the foreach loop in add_new_columns_to_pathtarget, build a pointer set of target->exprs entries. For each candidate expr, do O(1) pointer lookup (sufficient for canonical Var nodes); fall back to list_member only for non-canonical nodes.

Patch file

See postgresql-0007-add-new-columns-hash.patch

1.3 KiB Raw Permalink Blame History Unescape Escape