Re: Hash aggregate collisions cause excessive spilling

From: Andres Freund <andres(at)anarazel(dot)de>
To: Ants Aasma <ants(dot)aasma(at)cybertec(dot)at>, David Rowley <dgrowleyml(at)gmail(dot)com>, Tomas Vondra <tomas(at)vondra(dot)me>, Richard Guo <guofenglinux(at)gmail(dot)com>, Jeff Davis <pgsql(at)j-davis(dot)com>
Cc: PostgreSQL Hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>
Subject: Re: Hash aggregate collisions cause excessive spilling
Date: 2026-11-19 17:43:58
Message-ID: enylcoyk5nlqd3rk5j5rtd6yh47rdigaurweput27agwxxigi5@6q6hgxofb5bk
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Hi,

I unfortunately forgot about this thread. Until I rediscovered the issue from
scratch yesterday.

I loaded TPCH scale 10 in parallel, ran the queries. And Q04 got stuck. Like
well over an hour without any progress.

There's a bunch of interrelated things that lead to the problem:

1) n_distinct for lineitem.l_orderkey is awful, this has been known for a long
time:
https://postgr.es/m/5581B3EE.1070907%402ndquadrant.com

Due to this a TPCH scale 10 lineitem.l_orderkey is estimated to be ~400k,
instead of 15M.

[1] is a simple repro.

2) Because of the parallel loading, l_orderkey's correlation stat is lower
than with a sequential load (where it's typically ~1).

With high correlation the plan chosen is a nested loop semi join.

3) In 19, via 24225ad9aaf I think, we choose a parallel plan that does a
HashAgg below a Gather and than aggregates again in the leader:

-> HashAggregate (cost=1589539.14..1593466.49 rows=392735 width=8)
Group Key: lineitem.l_orderkey
-> Gather (cost=1488998.98..1587182.73 rows=942564 width=8)
Workers Planned: 2
-> HashAggregate (cost=1487998.98..1491926.33 rows=392735 width=8)
Group Key: lineitem.l_orderkey
-> Parallel Seq Scan on lineitem (cost=0.00..1467174.42 rows=8329825 width=8)
Filter: (l_commitdate < l_receiptdate)

If not loaded in parallel, 2) will prevent this plan from being chosen by
default. But SET enable_nestloop = 0 forces that plan too.

4) Due to the issue in this thread, the re-aggregation in the leader takes
approximately forever.

This requires work_mem to be set to something like 64MB. With a larger work
mem a parallel hash join is chosen.

Here's a tuplehash_stat(tb) after a a while:
size: 8388608, members: 655755, filled: 0.078172, total chain: 3716619732, max chain: 63924, avg chain: 5667.695606, total_collisions: 259020, max_collisions: 8, avg_collisions: 0.394995

While the super-underfilled hashtable is bad, the worst part is that this
triggers hashagg spilling once the hashtable is big enough to trigger
that. At that point all hope is lost, it's so slow that there's no chance
of completing.

If I disable spilling, it's still slow, but does complete (~120s, using
~240MB). If I reduce SH_GROW_MIN_FILLFACTOR performance recovers.

I think the 19 changes make it more urgent to fix this, but it's bad enough
before, so I think we ought to backpatch this all the way.

On 2026-03-01 19:19:38 +0200, Ants Aasma wrote:
> On Sat, 28 Feb 2026 at 22:03, Andres Freund <andres(at)anarazel(dot)de> wrote:
> > > I think right now that limits it to hash aggregates with parallel
> > > query. ExecBuildHash32FromAttrs comment says that we should be using
> > > non-zero init_value only when needed for a marginal performance gain. So I
> > > limited the plan node id inclusion to use_variable_hash_iv, but made it
> > > unconditional for aggregates.
> >
> > That's an argument... I guess we could mostly avoid that though, by just
> > always combining in EEOP_HASHDATUM_FIRST.
>
> I think that makes it exactly the same as EEOP_HASHDATUM_NEXT32,
> making the special op code pointless. I assume David observed some
> speedup there to go through the effort to include it.

> > > diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
> > > index 7d487a165fa..5c947fd151f 100644
> > > --- a/src/backend/executor/nodeAgg.c
> > > +++ b/src/backend/executor/nodeAgg.c
> > > @@ -1535,7 +1535,7 @@ build_hash_table(AggState *aggstate, int setno, double nbuckets)
> > > metacxt,
> > > tuplescxt,
> > > tmpcxt,
> > > - DO_AGGSPLIT_SKIPFINAL(aggstate->aggsplit));
> > > + true);
> > > }
> >
> > Hm, won't that mean we'll now always use the slower path? I think there are
> > non-partial cases that could be problematic, but if we do this we probaly
> > should do the optimization of the hash expression stuff I mentioned above.
>
> If you mean EEOP_HASHDATUM_FIRST, then I think that would just be
> removing an optimization. I think getting rid of the quicker growth
> and correlated table filling in the 1:1 case might be more significant
> than the slightly slower hash calculation. However the downside of the
> bad case is pretty nasty. Do you think it's worth the effort of trying
> to figure out if we are in a dangerous looking structure?

David, any opinion?

> Decorrelating the hash tables still doesn't fix the terrible edge case
> of hash aggregate exceeding memory limit with hash table alone. Just
> makes it exceedingly improbable to hit with non-antagonistic
> workloads. Would it be a good idea to fix that too? A simple answer
> would be to always allow hash aggregate to use some fraction like 25%
> of allowed memory for tuples, even if the hash table is too big.

There is already the logic to have at least one group, I wonder if that ought
to be changed to some fillfactor based logic. Resetting the table's size ends
up performing very poorly, so I don't think that's a great option either...

Jeff?

> diff --git a/src/test/regress/expected/union.out b/src/test/regress/expected/union.out
> index 709c85f2294..fad22c0ed2d 100644
> --- a/src/test/regress/expected/union.out
> +++ b/src/test/regress/expected/union.out
> @@ -551,8 +551,8 @@ select x from (values (array[1, 2]), (array[1, 3])) _(x) union select x from (va
> x
> -------
> {1,4}
> - {1,2}
> {1,3}
> + {1,2}
> (3 rows)
>
> explain (costs off)

Think we ought to give this query an ORDER BY...

Greetings,

Andres Freund

[1]

Basically the problem is frequent duplicates within one block, with very
infrequent duplicates across blocks.

To reproduce:

CREATE TABLE t_1m_5r_w2_ff50 WITH (fillfactor = 50) AS SELECT a, repeats, repeat(random()::text, 5) r1, repeat(random()::text, 5) r2 FROM (SELECT generate_series(1, 1000000) a), (SELECT generate_series(1, 5) repeats);
ANALYZE t_1m_5r_w2_ff50;

SELECT tablename, attname, reltuples::numeric, n_distinct::numeric, (case when n_distinct < 0 then reltuples * -n_distinct ELSE n_distinct END)::int8 AS n_distinct_abs, ((relpages::numeric * 8192) / reltuples)::numeric(10,2) tuple_width, correlation FROM pg_stats JOIN pg_class pc ON (tableid=pc.oid) WHERE (tablename LIKE 't_%' AND attname IN ('a')) ORDER BY tablename, attname;

┌─────────────────┬─────────┬───────────┬────────────┬────────────────┬─────────────┬──────────────┐
│ tablename │ attname │ reltuples │ n_distinct │ n_distinct_abs │ tuple_width │ correlation │
├─────────────────┼─────────┼───────────┼────────────┼────────────────┼─────────────┼──────────────┤
│ t_1m_5r_w2_ff20 │ a │ 4999910 │ 69349 │ 69349 │ 1170.44 │ 1 │
│ t_1m_5r_w2_ff50 │ a │ 5000000 │ 142053 │ 142053 │ 455.50 │ 1 │
│ t_1m_5r_w2_ff99 │ a │ 4999420 │ 261368 │ 261368 │ 229.14 │ 1 │
│ t_1m_5r_w2_r │ a │ 5000000 │ -0.193563 │ 967814 │ 225.44 │ 0.0009527237 │
└─────────────────┴─────────┴───────────┴────────────┴────────────────┴─────────────┴──────────────┘

Obviously 142053 is not a good approximation of 1M. And _r (which I added
ORDER BY random() for), shows that different distributions won't have the
same problem.

In response to

Browse pgsql-hackers by date

  From Date Subject
Next Message Fujii Masao 2026-11-19 17:46:48 Re: [BUG] Take a long time to reach consistent after pg_rewind
Previous Message David Geier 2026-11-19 17:33:48 Re: Use local buffer for packed numerics