| From: | Andres Freund <andres(at)anarazel(dot)de> |
|---|---|
| To: | Ants Aasma <ants(dot)aasma(at)cybertec(dot)at>, Jeff Davis <pgsql(at)j-davis(dot)com>, David Rowley <dgrowleyml(at)gmail(dot)com> |
| Cc: | Tomas Vondra <tomas(at)vondra(dot)me>, PostgreSQL Hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org> |
| Subject: | Re: Hash aggregate collisions cause excessive spilling |
| Date: | 2026-11-21 17:42:31 |
| Message-ID: | shfhbnixgeafm2xzhnnxdz3e5ov4evkracctd545rel5uq3u23@vtnjzwyoi2gx |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-hackers |
Hi,
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:
> > > This problem should only affect cases where multiple hash tables worth
> > > of tuples are trying to fit into one.
> >
> > Is that entirely true? If we are feeding one hash table from other hash table,
> > 1:1, and the initial size of the target table is wrong, we probably also won't
> > handle it in the best way.
> >
> > That could happen with a group by over a group by (with perhaps some joins
> > above the first group by). Probably not that common, but ...
> >
> > I guess another case could be a CTAS of a group by query that is then grouped
> > by again.
>
> With 1:1 tables, if the target table is smaller there is going to be a
> ton of collisions which should quite quickly trigger growth via
> SH_GROW_MAX_MOVE (150). But once the target table is the same size as
> source the growth will stop. I think this ends up being slightly more
> efficient in the correlated case because the table will be growing at
> 10% fill factor, having less entries to move around. And the access to
> the target hash table will be more correlated over time for better
> cache efficiency.
>
> However I think it might be possible to have different hash table size
> limits in a single plan. At least setting hash_mem_multiplier on a
> function would do it. But I wasn't able to trigger any bad behavior
> with this for some reason. I will experiment some more.
I was trying to reproduce the non-parallel case. And for a while I failed
badly. One hashtable feeding into another would just not trigger anything bad.
Thinking about it way too long, I think it's maybe kind of fundamentally true?
1) The only reason we get into the "bad" performance situation is that we
limit the growth with SH_GROW_MIN_FILLFACTOR.
Without that the table would just grow very fast initially and then not at
all afterwards.
2) With a single source hashtable, we shouldn't get into the extreme spilling
case, as the source hashtable was also limited in size by spilling.
Of course there could be a join or such in between increasing the number of
input rows, but it shouldn't be able to influence the number of groups
without completely changing the hash values, e.g. due to adding another key
column.
3) The multiple source hashtables have to have mostly *non* overlapping data
Otherwise they'll just get combined into one aggregated value.
4) We iterate over the source hashtable approximately in reverse
hash & size maskorder
5) We need to build the result hashtable by iterating over all the source data
in `hash & mask` order. Outside of the parallel case that seems
exceedingly unlikely.
I think this means it's quite hard to get to a sufficiently inbalanced
hashtable with a single source.
I then also tried the parallel worker repro - and interestingly, it turned out
that I can only reproduce problems with at least 3 source hashtables
(i.e. leader_participation=1 + 2 workers, or leader_participation=0 + 3
workers).
The repro for the single session case is this:
SET work_mem = '1GB'; -- trigger quadradic performance issues
-- SET SET work_mem = '60MB'; -- trigger excessive spilling
EXPLAIN ANALYZE
SELECT i, count(*) FROM (
SELECT * FROM (
SELECT *
FROM
(SELECT 25 as reps, 500000 rows),
-- repeat a hash table with non-equivalent contents but close-by
-- hash & sizemask values n times
LATERAL generate_series(1, reps) inst,
lateral (
SELECT row_number() OVER () AS rn, i
FROM generate_series(inst, rows * reps, reps) WITH ORDINALITY g(i, ord)
GROUP BY i)
)
-- then order all the hashtables in ~ hash & sizemask order
ORDER BY rn
)
GROUP BY i;
You can play with work_mem, the number of rows and reps to get differently
extreme cases.
I think this query only really gets this bad because the distinctness
estimation for generate_series() is terrifyingly bad. But of course there'd be
plenty ways of triggering this without generate_series() too.
I can't really come up with non-crazy query patterns that trigger the
non-parallel case. But I'm not sure that's true.
I'm inclined to think that on balance we should indeed apply an IV every time,
not just in the parallel case? Even though I can't come up with non-crazy
ways of hitting this.
It's worth noting that given the way the IV is computed right now, i.e. based
on the parallel worker number and plan ID, doesn't entirely prevent this
situation: You could have cases where query results are stored in a table, in
`hash & mask` order, re-aggregated and stored again, ... But due the
requirement of really needing to consume several ~evenly sized hashtables in
parallel (one after each other would work perfectly).
The proper fix here would be to use a random IV, but I think the downsides of
loosing all query stability are too severe.
Thoughts?
Andres Freund
| From | Date | Subject | |
|---|---|---|---|
| Next Message | shihao zhong | 2026-11-21 17:44:51 | Re: [PATCH] Add planner support function to two-argument regexp_like() |
| Previous Message | Zhijie Hou | 2026-11-21 17:09:28 | Fix standby logical slot creation during dynamic logical decoding activation |