From ad87bf355214c47221263825b3a541062c71aea7 Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Mon, 1 Nov 2021 16:24:40 -0400 Subject: Avoid some other O(N^2) hazards in list manipulation. In the same spirit as 6301c3ada, fix some more places where we were using list_delete_first() in a loop and thereby risking O(N^2) behavior. It's not clear that the lists manipulated in these spots can get long enough to be really problematic ... but it's not clear that they can't, either, and the fixes are simple enough. As before, back-patch to v13. Discussion: https://postgr.es/m/CD2F0E7F-9822-45EC-A411-AE56F14DEA9F@amazon.com --- src/backend/executor/nodeAgg.c | 17 +++++------------ 1 file changed, 5 insertions(+), 12 deletions(-) (limited to 'src/backend/executor') diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c index d48289ee862..31609c60fc6 100644 --- a/src/backend/executor/nodeAgg.c +++ b/src/backend/executor/nodeAgg.c @@ -2602,8 +2602,9 @@ agg_refill_hash_table(AggState *aggstate) if (aggstate->hash_batches == NIL) return false; - batch = linitial(aggstate->hash_batches); - aggstate->hash_batches = list_delete_first(aggstate->hash_batches); + /* hash_batches is a stack, with the top item at the end of the list */ + batch = llast(aggstate->hash_batches); + aggstate->hash_batches = list_delete_last(aggstate->hash_batches); hash_agg_set_limits(aggstate->hashentrysize, batch->input_card, batch->used_bits, &aggstate->hash_mem_limit, @@ -3182,7 +3183,7 @@ hashagg_spill_finish(AggState *aggstate, HashAggSpill *spill, int setno) new_batch = hashagg_batch_new(tapeset, tapenum, setno, spill->ntuples[i], cardinality, used_bits); - aggstate->hash_batches = lcons(new_batch, aggstate->hash_batches); + aggstate->hash_batches = lappend(aggstate->hash_batches, new_batch); aggstate->hash_batches_used++; } @@ -3197,8 +3198,6 @@ hashagg_spill_finish(AggState *aggstate, HashAggSpill *spill, int setno) static void hashagg_reset_spill_state(AggState *aggstate) { - ListCell *lc; - /* free spills from initial pass */ if (aggstate->hash_spills != NULL) { @@ -3216,13 +3215,7 @@ hashagg_reset_spill_state(AggState *aggstate) } /* free batches */ - foreach(lc, aggstate->hash_batches) - { - HashAggBatch *batch = (HashAggBatch *) lfirst(lc); - - pfree(batch); - } - list_free(aggstate->hash_batches); + list_free_deep(aggstate->hash_batches); aggstate->hash_batches = NIL; /* close tape set */ -- cgit v1.2.3