From: Frank Heikens <frank@elevarq.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Scott Carey <scott.carey@algonomy.com>
Cc: Jeff Davis <pgsql@j-davis.com>
Cc: David Rowley <dgrowleyml@gmail.com>
Cc: pgsql-performance@lists.postgresql.org <pgsql-performance@lists.postgresql.org>
Subject: Re: Significant performance issues with array_agg() + HashAggregate plans on Postgres 17
Date: Fri, 3 Apr 2026 04:19:34 +0000
Message-ID: <540A0AD2-7CAA-4535-82F7-FC9055437B20@elevarq.com> (raw)
In-Reply-To: <3579239.1775151498@sss.pgh.pa.us>
References: <CA+vubOGaanYaGGb98etJPeJCbN=RAawx652MdmJVRK8+BeEP0w@mail.gmail.com>
<CAApHDvq5fMzhK7OwGOhOgqRF-wErGNsT75yie5LtobSir1HhnA@mail.gmail.com>
<CA+vubOE6feEWh7XxoWqdPh634SUVjHKW7s9BgMD755wJTqQFPw@mail.gmail.com>
<CA+vubOHgrdkm+3wgC0FPcStDeMS9ZQ_Du9vUXWjxN9MN9CO2uw@mail.gmail.com>
<2764544.1774985169@sss.pgh.pa.us>
<CA+vubOEbfm5+BxtuFGb_tTj3sSX1u0Y+=zHUxoF1Q9feGpRfNg@mail.gmail.com>
<2897039.1775051081@sss.pgh.pa.us>
<CA+vubOGqg7f2E0_OW8EMruAObejnCS1gCgguT+cnwHG9bRxMDQ@mail.gmail.com>
<3579239.1775151498@sss.pgh.pa.us>
Hi,
I've been investigating a performance problem with user-defined aggregates
that use array_append as the transition function (SFUNC = array_append,
STYPE = bigint[]). These aggregates become catastrophically slow with
HashAggregate when many groups are present -- a workload demonstrated.
Root cause
----------
hash_agg_check_limits() calls MemoryContextMemAllocated(ctx, true) after
every new group addition. The recursive flag causes it to traverse all
child memory contexts, which is O(C) per call.
array_append creates an expanded-array object per group, each owning a
private AllocSet child context. With N groups, the total traversal cost
becomes O(N * C) ≈ O(N^2). This completely dominates the actual
aggregate computation once the group count reaches tens of thousands.
Reproducer (Tom's test case)
---------------------------------
CREATE AGGREGATE array_agg(
BASETYPE = bigint, SFUNC = array_append,
STYPE = bigint[], INITCOND = '{}');
CREATE TABLE array_agg_test(
product_id bigint NOT NULL,
region_id bigint NOT NULL,
available boolean NOT NULL);
INSERT INTO array_agg_test
SELECT generate_series(1, 50000),
(ARRAY[1,2,3,4])[floor(random()*4)+1], true;
-- (repeat 3 more times with region arrays [11..14], [111..114], [1111..1114])
VACUUM ANALYZE array_agg_test;
SET work_mem = '200MB';
EXPLAIN (ANALYZE, BUFFERS)
SELECT product_id, array_agg(region_id)
FROM array_agg_test GROUP BY product_id;
-- 50K groups, ~4 rows per group
-- Without patch: ~5 seconds
-- With patch: ~150 ms
-- Built-in array_agg: ~100 ms
Fix
---
The attached patch throttles the recursive memory check: once the group
count exceeds 1024, the full check only runs every 1024th new group.
Below 1024 groups, behavior is unchanged.
This caps the spill-detection latency to at most 1024 groups' worth of
memory. For typical work_mem settings, that's a few megabytes of
potential overshoot -- well within the existing tolerance of the check,
which was already described as "imperfect" in its own comments.
The patch is purely local to hash_agg_check_limits() in nodeAgg.c:
about 15 lines of functional change plus comments.
Benchmarks (PG 19devel, debug build, -O0)
------------------------------------------
Tom Lane reproducer (50K groups):
custom array_agg 200MB: 4.6 s -> 152 ms (30x)
custom array_agg 4MB: 388 ms -> 283 ms (no regression)
built-in array_agg: 102 ms -> 103 ms (unchanged)
Synthetic (100K groups x 50 elems):
custom 256MB: 35.0 s -> 2.9 s (12x)
custom 4MB: 6.1 s -> 5.9 s (unchanged)
Extreme (500K groups x 2 elems):
custom 256MB: 672 s -> 1.7 s (395x)
Non-array aggregates (count, sum, string_agg): unchanged
Built-in array_agg: unchanged
Spill behavior (batches, disk usage): unchanged
Regards,
Frank Heikens
> On Apr 2, 2026, at 10:38 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> Scott Carey <scott.carey@algonomy.com> writes:
>> I have discovered the root cause.
>> This database is old. It pre-dates Postgres 8.4 which introduced
>> array_agg. Apparently, in some version prior to 8.4 array_agg was added
>> as a user function, defined as below for bigint:
>
>> create AGGREGATE array_agg(
>> BASETYPE = bigint,
>> SFUNC = array_append,
>> STYPE = bigint[],
>> INITCOND = '{}'
>> );
>
>> So if you create a test database and run the previous test, performance
>> will be fine and the query will be fast. Then run:
>> create AGGREGATE array_agg(BASETYPE = bigint, SFUNC = array_append,STYPE =
>> bigint[], INITCOND = '{}');
>
>> It will be slow and reproduce this behavior.
>
> Thank you for running that to ground! I confirm your results that v13
> and up are far slower for this example than v12 was.
>
>> Why would this run so much more slowly after updating from postgres 12 to
>> 17? It is a user defined aggregate, although maybe not as optimized as
>> the intrinsic one it shouldn't behave this way.
>
> I did some bisecting using the attached simplified test case, and found
> that the query execution time jumps from circa 60ms to circa 7500ms here:
>
> 1f39bce021540fde00990af55b4432c55ef4b3c7 is the first bad commit
> commit 1f39bce021540fde00990af55b4432c55ef4b3c7
> Author: Jeff Davis <jdavis@postgresql.org>
> Date: Wed Mar 18 15:42:02 2020 -0700
>
> Disk-based Hash Aggregation.
>
> While performing hash aggregation, track memory usage when adding new
> groups to a hash table. If the memory usage exceeds work_mem, enter
> "spill mode".
>
> (Times quoted are on a Mac M4 Pro, but in assert-enabled builds so
> maybe not directly comparable to production.)
>
> I'm bemused as to why: the test case has work_mem set high enough that
> we shouldn't be triggering spill mode, so why did this change affect
> it at all?
>
> regards, tom lane
>
> CREATE AGGREGATE array_agg(
> BASETYPE = bigint,
> SFUNC = array_append,
> STYPE = bigint[],
> INITCOND = '{}'
> );
>
> drop table if exists array_agg_test;
>
> create table array_agg_test(product_id bigint not null, region_id bigint
> not null, available boolean not null);
>
> insert into array_agg_test (product_id, region_id, available) SELECT
> generate_series(1, 50000) as product_id,
> (ARRAY[1,2,3,4])[floor(random()*4)+1] as region_id, true as available;
>
> insert into array_agg_test (product_id, region_id, available) SELECT
> generate_series(1, 50000) as product_id,
> (ARRAY[11,12,13,14])[floor(random()*4)+1] as region_id, true as available;
>
> insert into array_agg_test (product_id, region_id, available) SELECT
> generate_series(1, 50000) as product_id,
> (ARRAY[111,112,113,114])[floor(random()*4)+1] as region_id, true as
> available;
>
> insert into array_agg_test (product_id, region_id, available) SELECT
> generate_series(1, 50000) as product_id,
> (ARRAY[1111,1112,1113,1114])[floor(random()*4)+1] as region_id, true as
> available;
>
> vacuum analyze array_agg_test;
>
> \set ECHO all
>
> -- set hash_mem_multiplier = 2;
> set work_mem = "200MB";
>
> explain (analyze, buffers) select product_id, array_agg(region_id) from
> array_agg_test group by product_id;
Attachments:
[application/octet-stream] 0001-Throttle-hash_agg_check_limits-to-avoid-O-N-2-contex.patch (4.1K, ../540A0AD2-7CAA-4535-82F7-FC9055437B20@elevarq.com/3-0001-Throttle-hash_agg_check_limits-to-avoid-O-N-2-contex.patch)
download | inline diff:
From 3c8e3e34dc79109394b948330dfa4e32666b57e0 Mon Sep 17 00:00:00 2001
From: Frank Heikens <fheikens@users.noreply.github.com>
Date: Thu, 2 Apr 2026 21:01:19 -0700
Subject: [PATCH] Throttle hash_agg_check_limits to avoid O(N^2) context
traversal
hash_agg_check_limits() calls MemoryContextMemAllocated() with
recurse=true after every new hash group addition. This traverses
all child memory contexts to sum their mem_allocated, which is O(C)
where C is the number of child contexts.
Some aggregate transition functions create per-group child contexts.
For example, array_append (when used as an aggregate SFUNC) creates
an expanded-array object with a private AllocSet for each group.
With N groups the total traversal cost is O(N * C) = O(N^2), which
becomes the dominant cost once tens of thousands of groups are
present in the hash table.
On a reproducer with 50K groups using a user-defined array_agg
with array_append as SFUNC, the unthrottled check accounts for
roughly 97% of the query time: ~5 seconds versus ~150 ms for the
actual aggregate computation.
Fix by throttling the recursive memory check: once the group count
exceeds 1024, only perform the full check every 1024 new groups.
This bounds the spill-detection latency to at most 1024 groups'
worth of memory while keeping the per-check overhead constant.
Benchmarks on 50K groups: 4.6 s -> 152 ms (30x).
Benchmarks on 100K groups: 35 s -> 2.9 s (12x).
Benchmarks on 500K groups: 672 s -> 1.7 s (395x).
No regressions observed for built-in aggregates, non-array aggregates,
or batched (low work_mem) workloads. Spill behavior (batch count,
disk usage) is unchanged.
---
src/backend/executor/nodeAgg.c | 38 +++++++++++++++++++++++++++-------
1 file changed, 31 insertions(+), 7 deletions(-)
diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.cindex 925caadd2ce..9a23dedeccd 100644--- a/src/backend/executor/nodeAgg.c+++ b/src/backend/executor/nodeAgg.c@@ -1861,20 +1861,44 @@ hash_agg_set_limits(double hashentrysize, double input_groups, int used_bits,
* After adding a new group to the hash table, check whether we need to enter
* spill mode. Allocations may happen without adding new groups (for instance,
* if the transition state size grows), so this check is imperfect.
+ *+ * Note: MemoryContextMemAllocated with recurse=true traverses all child+ * contexts, making it O(C) where C is the child count. Some aggregate+ * transition functions create per-group child contexts (for example,+ * array_append creates expanded-array objects each owning a private+ * AllocSet). Calling this function after every new group would then be+ * O(N*C) ≈ O(N^2) total, which becomes the dominant cost with tens of+ * thousands of groups. We avoid that by throttling: once there are more+ * than 1024 groups, we only run the full check every 1024th group. This+ * caps the overshoot to at most 1024 groups' worth of memory before spill+ * mode is entered.
*/
static void
hash_agg_check_limits(AggState *aggstate)
{
uint64 ngroups = aggstate->hash_ngroups_current;
- Size meta_mem = MemoryContextMemAllocated(aggstate->hash_metacxt,- true);- Size entry_mem = MemoryContextMemAllocated(aggstate->hash_tuplescxt,- true);- Size tval_mem = MemoryContextMemAllocated(aggstate->hashcontext->ecxt_per_tuple_memory,- true);- Size total_mem = meta_mem + entry_mem + tval_mem;+ Size meta_mem;+ Size entry_mem;+ Size tval_mem;+ Size total_mem;
bool do_spill = false;
+ /*+ * Throttle the expensive recursive MemoryContextMemAllocated calls.+ * Below 1024 groups the quadratic cost is negligible; above that we+ * check every 1024 groups to keep the overhead linear.+ */+ if (ngroups > 1024 && (ngroups & 0x3FF) != 0)+ return;++ meta_mem = MemoryContextMemAllocated(aggstate->hash_metacxt,+ true);+ entry_mem = MemoryContextMemAllocated(aggstate->hash_tuplescxt,+ true);+ tval_mem = MemoryContextMemAllocated(aggstate->hashcontext->ecxt_per_tuple_memory,+ true);+ total_mem = meta_mem + entry_mem + tval_mem;+
#ifdef USE_INJECTION_POINTS
if (ngroups >= 1000)
{
--
2.33.0
[text/markdown] BENCHMARK_SUMMARY.md (1.7K, ../540A0AD2-7CAA-4535-82F7-FC9055437B20@elevarq.com/4-BENCHMARK_SUMMARY.md)
download | inline:
# Benchmark summary
PG 19devel, aarch64-darwin, debug build (-O0, cassert).
All runs: max_parallel_workers_per_gather = 0.
## Tom's reproducer (50K groups × 4 elems, 200K rows)
| Test | Unpatched | Patched | Change |
|------|:---------:|:-------:|:------:|
| custom array_agg, 200MB (run 1) | 4,563 ms | 155 ms | 29x faster |
| custom array_agg, 200MB (run 2) | 5,025 ms | 152 ms | 33x faster |
| custom array_agg, 200MB (run 3) | 6,451 ms | 152 ms | 42x faster |
| custom array_agg, 4MB (run 1) | 388 ms | 283 ms | 1.4x faster |
| built-in array_agg, 200MB | 102 ms | 103 ms | unchanged |
Plan structure, batch count, and memory usage: identical.
## Synthetic workloads (5M total elements)
| Workload | work_mem | Unpatched | Patched | Change |
|----------|:--------:|:---------:|:-------:|:------:|
| 100K grp × 50 elem | 256MB | 35.0 s | 2.9 s | 12x |
| 100K grp × 50 elem | 4MB | 6.1 s | 5.9 s | — |
| 10K grp × 500 elem | 256MB | 2.7 s | 2.5 s | — |
| 10K grp × 500 elem | 4MB | 4.5 s | 4.5 s | — |
| 1K grp × 5K elem | 256MB | 2.4 s | 2.5 s | — |
| 500K grp × 2 elem | 256MB | 672 s | 1.7 s | 395x |
| 500K grp × 2 elem | 4MB | 5.4 s | 1.8 s | 3x |
## Non-array aggregates (unchanged)
| Aggregate | Unpatched | Patched |
|-----------|:---------:|:-------:|
| count(*) 100K groups | 1.9 s | 1.9 s |
| sum() 100K groups | 1.9 s | 1.9 s |
| string_agg 10K groups | 0.6 s | 0.6 s |
| built-in array_agg 256MB | 2.9 s | 2.9 s |
## Spill Behavior (work_mem = 4MB, 100K groups)
| Metric | Unpatched | Patched |
|--------|:---------:|:-------:|
| Batches | 61 | 61 |
| Memory Usage | 8,547 kB | 8,753 kB |
| Disk Usage | 143,872 kB | 143,440 kB |
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: frank@elevarq.com, tgl@sss.pgh.pa.us, scott.carey@algonomy.com, pgsql@j-davis.com, dgrowleyml@gmail.com, pgsql-performance@lists.postgresql.org
Subject: Re: Significant performance issues with array_agg() + HashAggregate plans on Postgres 17
In-Reply-To: <540A0AD2-7CAA-4535-82F7-FC9055437B20@elevarq.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox