MIME-Version: 1.0
References: 
 <CANwKhkPOZupu3PYQVdkMmYjquYVqG2v8XmCAuuVM9Eu13-Zw3g@mail.gmail.com>
 <a5f46e2e-3b11-44bd-9a24-fa7d5b3948cd@vondra.me>
 <CANwKhkM853zqt4xkpG6UvS0CTJ1_nqL-PDju+QmF_-Dv5TjFtw@mail.gmail.com>
 <vhafwgkrzqlc5cm7vuz6df5ohmf4rjfgrfnd6stqag5i7edi46@wcdtbcib4nnd>
 <CANwKhkNQjUwSR_2KPE0my1cYiMyFij_50Bmfdy0eWsy-5_p5WQ@mail.gmail.com>
 <vx4azu62rgrnkt4oauviepbydxj5q7wbtzycwmqnmby2sfpvwc@xfvp3pcjnv2w>
 <CANwKhkMoXaTEe8yCd0hJSXxTH6S9awF8g=ES-xYt8E0FoVpfzQ@mail.gmail.com>
 <CANwKhkOZuf8ychD3b=8-+-hxyu+OjOCU56AesbHiDqpRmARc0w@mail.gmail.com>
 <5pbulw5plv5owcg5iothxfg5xf6vj6ayfltppsg573kllpnx24@vd2iaqxnkasy>
 <CANwKhkOMbFeFwmzB0zoFDXKYMV-xM8===0LD3c4DHJ1wht3=6w@mail.gmail.com>
 <ywqrfyzq77hxfvzj7kbm22dtcny3wqfm6gzwghorp2eq4kzzuf@af7v5atqoqk6>
In-Reply-To: <ywqrfyzq77hxfvzj7kbm22dtcny3wqfm6gzwghorp2eq4kzzuf@af7v5atqoqk6>
From: Ants Aasma <ants.aasma@cybertec.at>
Date: Sun, 1 Mar 2026 19:19:38 +0200
Message-ID: 
 <CANwKhkM5ZWH4WMegLZ7s_RBzkTtN7CUouNiu291Xn-76JZwd_w@mail.gmail.com>
Subject: Re: Hash aggregate collisions cause excessive spilling
To: Andres Freund <andres@anarazel.de>
Cc: Tomas Vondra <tomas@vondra.me>,
	PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Content-Type: multipart/mixed; boundary="0000000000008abd19064bf9add8"
Archived-At: 
 <https://www.postgresql.org/message-id/CANwKhkM5ZWH4WMegLZ7s_RBzkTtN7CUouNiu291Xn-76JZwd_w%40mail.gmail.com>
Precedence: bulk

--0000000000008abd19064bf9add8
Content-Type: text/plain; charset="UTF-8"

On Sat, 28 Feb 2026 at 22:03, Andres Freund <andres@anarazel.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 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.

>> > I used hash_combine to smear together the bits of the two. I think
> > that should be good enough. Alternatively a xor of murmurhash32 of the
> > two should be better.
>
> Probably it's good enough, but i'd probably still go for
>   hash_combine(murmurhash32(ParallelWorkerNumber),
>                murmurhash32(parent->plan->plan_node_id))
> or such.

Used this approach.

> > There is also a call to ExecBuildHash32FromAttrs from ExecInitSubPlan
> > that specifies a hash_iv for a hashed sub plan execution.
>
> When you're saying it specifies a hash IV you mean the 0 it passes, not some
> more complicated value, right?

Right.

>
> > This must match the value BuildTupleHashTable decides on. Worth adding a
> > comment?
>
> Yes, I think so.

Done.

> >        */
> >       if (use_variable_hash_iv)
> > -             hash_iv = murmurhash32(ParallelWorkerNumber);
> > +             hash_iv = hash_combine(ParallelWorkerNumber, parent->plan->plan_node_id);
> >
> >       hashtable->hashtab = tuplehash_create(metacxt, nbuckets, hashtable);
>
> I think some of the reasoning from your commit messages needs to be in a
> comment somewhere too, otherwise the next person tackling this code will have
> a hell of a time.

I gave it a shot.

> > 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?

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.

Regards,
Ants Aasma

--0000000000008abd19064bf9add8
Content-Type: text/x-patch; charset="US-ASCII";
	name="v2-0001-Decorrelate-nested-hash-tables.patch"
Content-Disposition: attachment;
	filename="v2-0001-Decorrelate-nested-hash-tables.patch"
Content-Transfer-Encoding: base64
Content-ID: <f_mm80lkej0>
X-Attachment-Id: f_mm80lkej0

RnJvbSA3YTJhYzlkZjQ3MTdlOTU0NzVlMTBlNjYwMjY0ZGJhNTUwZDViZWU2IE1vbiBTZXAgMTcg
MDA6MDA6MDAgMjAwMQpGcm9tOiBBbnRzIEFhc21hIDxhbnRzQGN5YmVydGVjLmF0PgpEYXRlOiBT
YXQsIDI4IEZlYiAyMDI2IDE1OjA4OjUwICswMjAwClN1YmplY3Q6IFtQQVRDSCB2Ml0gRGVjb3Jy
ZWxhdGUgbmVzdGVkIGhhc2ggdGFibGVzCgpCZWNhdXNlIGhhc2ggdGFibGVzIGFyZSBpdGVyYXRl
ZCBpbiBoYXNoIG9yZGVyLCB1c2luZyB0aGUgc2FtZSBoYXNoCmZ1bmN0aW9uIGluIG5lc3RlZCBo
YXNoIHRhYmxlcyBjYW4gbGVhZCB0byBleGNlc3NpdmUgY29sbGlzaW9ucy4gSWYgdGhlCnBhcmVu
dCBoYXNoIHRhYmxlIGNhbiBiZSB0aGUgc2FtZSBzaXplIGFzIHRoZSBjaGlsZCBoYXNoIHRhYmxl
cyBpdCBpcwpub3QgYSBwcm9ibGVtIGFzIHRoZSBwYXJlbnQgd2lsbCBxdWlja2x5IGdyb3cgdG8g
dGhlIHNhbWUgc2l6ZSBhcyB0aGUKY2hpbGQsIGVsaW1pbmF0aW5nIGZ1cnRoZXIgY29sbGlzaW9u
cy4gQnV0IGlmIHRoZXJlIGFyZSBtb3JlIHRoYW4gb25lCmNoaWxkIHRoZSBjb2xsaXNpb25zIGNh
biBjYXVzZSB0aGUgdGFibGUgdG8gcXVpY2tseSBncm93IHVudGlsIGl0IGlzCmJlbG93IDEwJSBm
aWxsZmFjdG9yLgoKVGhlIHByb2JsZW0gaXMgbWFkZSB3b3JzZSBieSBub2RlQWdnIGRldm9sdmlu
ZyBpbnRvIGJ1aWxkaW5nIHNpbmdsZQplbnRyeSBiYXRjaGVzIG9uY2UgaGFzaCB0YWJsZSBzaXpl
IGV4Y2VlZHMgd29ya2luZyBtZW1vcnkuCgpUbyBoaXQgdGhlIHByb2JsZW0gYW4gYWdncmVnYXRl
IG5vZGUgd2l0aG91dCBhIGZpbmFsIGZ1bmN0aW9uIGFib3ZlCm11bHRpcGxlIG90aGVyIGFnZ3Jl
Z2F0ZSBub2RlcyBpcyBuZWVkZWQuIEJlY2F1c2UgaGFzaCBpdiBpcyBhbHJlYWR5CmluaXRpYWxp
emVkIHVzaW5nIHBhcmFsbGVsIHdvcmtlciBudW1iZXIgd2hlbiB0aGVyZSBpcyBubyBmaW5hbCBm
bgp0aGUgdHlwaWNhbCBjYXNlcyBkbyBub3QgaGl0IHRoaXMgcHJvYmxlbS4gQSBoYXNoIGFnZ3Jl
Z2F0ZSBpbXBsZW1lbnRpbmcKRElTVElOQ1QgYWJvdmUgbXVsdGlwbGUgcGFyYWxsZWwgd29ya2Vy
cyB3aXRoIG1vcmUgZ3JvdXBzIHRoYW4gZml0IGludG8KbWVtb3J5IGlzIG5lZWRlZC4KCkluaXRp
YWxpemluZyB0aGUgaGFzaCBmdW5jdGlvbiBiYXNlZCBvbiBwbGFuIG5vZGUgaWQgZGVjb3JyZWxh
dGVzIGhhc2gKdGFibGVzIHdpdGhpbiBhIHBsYW4gd2hpbGUgc3RpbGwga2VlcGluZyBiZWhhdmlv
ciBkZXRlcm1pbmlzdGljLgoKQXV0aG9yOiBBbnRzIEFhc21hIDxhbnRzLmFhc21hQGN5YmVydGVj
LmF0PgpEaXNjdXNzaW9uOiBodHRwczovL3Bvc3Rnci5lcy9tL0NBTndLaGtQT1p1cHUzUFlRVmRr
TW1ZanF1WVZxRzJ2OFhtQ0F1dVZNOUV1MTMtWnczZyU0MG1haWwuZ21haWwuY29tCi0tLQogc3Jj
L2JhY2tlbmQvZXhlY3V0b3IvZXhlY0dyb3VwaW5nLmMgfCAxNiArKysrKysrKysrKy0tLS0tCiBz
cmMvYmFja2VuZC9leGVjdXRvci9ub2RlQWdnLmMgICAgICB8ICAyICstCiBzcmMvdGVzdC9yZWdy
ZXNzL2V4cGVjdGVkL3VuaW9uLm91dCB8ICAyICstCiAzIGZpbGVzIGNoYW5nZWQsIDEzIGluc2Vy
dGlvbnMoKyksIDcgZGVsZXRpb25zKC0pCgpkaWZmIC0tZ2l0IGEvc3JjL2JhY2tlbmQvZXhlY3V0
b3IvZXhlY0dyb3VwaW5nLmMgYi9zcmMvYmFja2VuZC9leGVjdXRvci9leGVjR3JvdXBpbmcuYwpp
bmRleCBjMTA3NTE0YTg1ZC4uYmZkY2FjYTRlN2QgMTAwNjQ0Ci0tLSBhL3NyYy9iYWNrZW5kL2V4
ZWN1dG9yL2V4ZWNHcm91cGluZy5jCisrKyBiL3NyYy9iYWNrZW5kL2V4ZWN1dG9yL2V4ZWNHcm91
cGluZy5jCkBAIC0xOTksNiArMTk5LDEwIEBAIEJ1aWxkVHVwbGVIYXNoVGFibGUoUGxhblN0YXRl
ICpwYXJlbnQsCiAJVHVwbGVIYXNoVGFibGUgaGFzaHRhYmxlOwogCXVpbnQzMgkJbmJ1Y2tldHM7
CiAJTWVtb3J5Q29udGV4dCBvbGRjb250ZXh0OworCS8qCisJICogVGhlIHZhbHVlIGhlcmUgbXVz
dCBtYXRjaCB3aGF0IEV4ZWNJbml0U3ViUGxhbiBwYXNzZXMgdG8KKwkgKiBFeGVjQnVpbGRIYXNo
MzJGcm9tQXR0cnMuCisJICovCiAJdWludDMyCQloYXNoX2l2ID0gMDsKIAogCS8qCkBAIC0yNDAs
MTMgKzI0NCwxNSBAQCBCdWlsZFR1cGxlSGFzaFRhYmxlKFBsYW5TdGF0ZSAqcGFyZW50LAogCS8q
CiAJICogSWYgcGFyYWxsZWxpc20gaXMgaW4gdXNlLCBldmVuIGlmIHRoZSBsZWFkZXIgYmFja2Vu
ZCBpcyBwZXJmb3JtaW5nIHRoZQogCSAqIHNjYW4gaXRzZWxmLCB3ZSBkb24ndCB3YW50IHRvIGNy
ZWF0ZSB0aGUgaGFzaHRhYmxlIGV4YWN0bHkgdGhlIHNhbWUgd2F5Ci0JICogaW4gYWxsIHdvcmtl
cnMuIEFzIGhhc2h0YWJsZXMgYXJlIGl0ZXJhdGVkIG92ZXIgaW4ga2V5c3BhY2Utb3JkZXIsCi0J
ICogZG9pbmcgc28gaW4gYWxsIHByb2Nlc3NlcyBpbiB0aGUgc2FtZSB3YXkgaXMgbGlrZWx5IHRv
IGxlYWQgdG8KLQkgKiAidW5iYWxhbmNlZCIgaGFzaHRhYmxlcyB3aGVuIHRoZSB0YWJsZSBzaXpl
IGluaXRpYWxseSBpcwotCSAqIHVuZGVyZXN0aW1hdGVkLgorCSAqIGluIGFsbCB3b3JrZXJzLiBB
cyBoYXNodGFibGVzIGFyZSBpdGVyYXRlZCBvdmVyIGluIGhhc2ggdmFsdWUgb3JkZXIsCisJICog
aW5zZXJ0aW5nIGludG8gYSBzbWFsbGVyIHRhYmxlIG9yIGZyb20gbXVsdGlwbGUgdGFibGVzIGlz
IGdvaW5nIHRvCisJICogY2F1c2UgY29sbGlzaW9ucyB3aGljaCB0cmlnZ2VycyBoYXNoIHRhYmxl
IGdyb3d0aC4gSW4gaGFzaCBhZ2dyZWdhdGVzCisJICogYSB0b28gbGFyZ2UgaGFzaCB0YWJsZSBj
YXVzZXMgZXhjZXNzaXZlIHNwaWxsaW5nIGFzIHRoZXJlIGlzIG5vIG1lbW9yeQorCSAqIGxlZnQg
b3ZlciBmb3IgdHVwbGVzLgogCSAqLwogCWlmICh1c2VfdmFyaWFibGVfaGFzaF9pdikKLQkJaGFz
aF9pdiA9IG11cm11cmhhc2gzMihQYXJhbGxlbFdvcmtlck51bWJlcik7CisJCWhhc2hfaXYgPSBo
YXNoX2NvbWJpbmUobXVybXVyaGFzaDMyKFBhcmFsbGVsV29ya2VyTnVtYmVyKSwKKwkJCQkJCQkg
ICBtdXJtdXJoYXNoMzIocGFyZW50LT5wbGFuLT5wbGFuX25vZGVfaWQpKTsKIAogCWhhc2h0YWJs
ZS0+aGFzaHRhYiA9IHR1cGxlaGFzaF9jcmVhdGUobWV0YWN4dCwgbmJ1Y2tldHMsIGhhc2h0YWJs
ZSk7CiAKZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL2V4ZWN1dG9yL25vZGVBZ2cuYyBiL3NyYy9i
YWNrZW5kL2V4ZWN1dG9yL25vZGVBZ2cuYwppbmRleCA3ZDQ4N2ExNjVmYS4uNWM5NDdmZDE1MWYg
MTAwNjQ0Ci0tLSBhL3NyYy9iYWNrZW5kL2V4ZWN1dG9yL25vZGVBZ2cuYworKysgYi9zcmMvYmFj
a2VuZC9leGVjdXRvci9ub2RlQWdnLmMKQEAgLTE1MzUsNyArMTUzNSw3IEBAIGJ1aWxkX2hhc2hf
dGFibGUoQWdnU3RhdGUgKmFnZ3N0YXRlLCBpbnQgc2V0bm8sIGRvdWJsZSBuYnVja2V0cykKIAkJ
CQkJCQkJCQkJIG1ldGFjeHQsCiAJCQkJCQkJCQkJCSB0dXBsZXNjeHQsCiAJCQkJCQkJCQkJCSB0
bXBjeHQsCi0JCQkJCQkJCQkJCSBET19BR0dTUExJVF9TS0lQRklOQUwoYWdnc3RhdGUtPmFnZ3Nw
bGl0KSk7CisJCQkJCQkJCQkJCSB0cnVlKTsKIH0KIAogLyoKZGlmZiAtLWdpdCBhL3NyYy90ZXN0
L3JlZ3Jlc3MvZXhwZWN0ZWQvdW5pb24ub3V0IGIvc3JjL3Rlc3QvcmVncmVzcy9leHBlY3RlZC91
bmlvbi5vdXQKaW5kZXggNzA5Yzg1ZjIyOTQuLmZhZDIyYzBlZDJkIDEwMDY0NAotLS0gYS9zcmMv
dGVzdC9yZWdyZXNzL2V4cGVjdGVkL3VuaW9uLm91dAorKysgYi9zcmMvdGVzdC9yZWdyZXNzL2V4
cGVjdGVkL3VuaW9uLm91dApAQCAtNTUxLDggKzU1MSw4IEBAIHNlbGVjdCB4IGZyb20gKHZhbHVl
cyAoYXJyYXlbMSwgMl0pLCAoYXJyYXlbMSwgM10pKSBfKHgpIHVuaW9uIHNlbGVjdCB4IGZyb20g
KHZhCiAgICB4ICAgCiAtLS0tLS0tCiAgezEsNH0KLSB7MSwyfQogIHsxLDN9CisgezEsMn0KICgz
IHJvd3MpCiAKIGV4cGxhaW4gKGNvc3RzIG9mZikKLS0gCjIuNTEuMAoK
--0000000000008abd19064bf9add8--