Should HashSetOp go away

Jeff Janes <jeff.janes@gmail.com> writes:

I noticed some changes in this code v18, so wanted to revisit the issue.
Under commit 27627929528e, it looks like it got 25% more memory efficient,
but it thinks it got 40% more efficient, so the memory use got better but
the estimation actually got worse.

Hmm, so why not fix that estimation?

I was thinking of ways to improve the memory usage (or at least its
estimation) but decided maybe it would be better if HashSetOp went away
entirely. As far as I can tell HashSetOp has nothing to recommend it other
than the fact that it already exists. If we instead used an elaboration on
Hash Anti Join, then it would automatically get spilling to disk, parallel
operations, better estimation, and the benefits of whatever micro
optimizations people lavish on the highly used HashJoin machinery but not
the obscure, little-used HashSetOp.

This seems like a pretty bad solution. It would imply exporting the
complexities of duplicate-counting for EXCEPT ALL and INTERSECT ALL
modes into the hash-join logic. We don't need that extra complexity
there (it's more than enough of a mess already), and we don't need
whatever performance hit ordinary hash joins would take.

Also, I doubt the problem is confined to nodeSetOp. I think this is
fundamentally a complaint about BuildTupleHashTable and friends being
unable to spill to disk. Since we also use that logic for hashed
aggregates, RecursiveUnion, and hashed SubPlans, getting rid of
nodeSetOp isn't going to move the needle very far.

regards, tom lane

I wrote:

Jeff Janes <jeff.janes@gmail.com> writes:

I noticed some changes in this code v18, so wanted to revisit the issue.
Under commit 27627929528e, it looks like it got 25% more memory efficient,
but it thinks it got 40% more efficient, so the memory use got better but
the estimation actually got worse.

Hmm, so why not fix that estimation?

So I poked at this a little bit, and found a few factors affecting it:

* Tuple hash tables are typically given license to use twice work_mem;
see hash_mem_multiplier. Not sure if you were accounting for that
in your test.

* create_setop_path's required-space estimate of entrysize * numGroups
was rather lame before commit 5dfc19814, and it's even more so
afterwards. It's basically only accounting for the tuples themselves,
and not either the hashtable overhead or the SetOpStatePerGroupData
counter space. With wide tuples that might disappear into the noise,
but with only 16-ish data bytes per tuple it's all about the overhead.
On my machine this example uses 80 bytes per tuple in the "SetOp hash
table" context and another 16 or more in the simplehash hashtable.
So about triple what the planner thought.

* We can buy some of this back nearly for free, by switching the
SetOp hash table context to be a BumpContext not an AllocSetContext.
That doesn't move the needle too much in this example with
MEMORY_CONTEXT_CHECKING on, but with it off, the SetOp hash table
consumption drops to 48 bytes/tuple. (Also, for other tuple widths,
AllocSetContext's round-up-to-power-of-2 behavior could hurt a lot
more than it does here.)

* To do better, we probably need to take this computation out of the
planner and have execGrouping.c expose a function to estimate the
TupleHashTable size for N entries and such-and-such average data
width. That in turn will require simplehash.h to expose a function
for estimating the size of its tables, because AFAICS its callers are
not supposed to know such details.

Attached is a quick-hack patch to use a BumpContext for this purpose
in nodeSetOp.c. We should probably look at whether other users of
BuildTupleHashTable can do similarly. I haven't thought hard about
what better-factorized space estimation would look like.

regards, tom lane

On Mon, 27 Oct 2025 at 07:00, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Jeff Janes <jeff.janes@gmail.com> writes:

I was thinking of ways to improve the memory usage (or at least its
estimation) but decided maybe it would be better if HashSetOp went away
entirely. As far as I can tell HashSetOp has nothing to recommend it other
than the fact that it already exists. If we instead used an elaboration on
Hash Anti Join, then it would automatically get spilling to disk, parallel
operations, better estimation, and the benefits of whatever micro
optimizations people lavish on the highly used HashJoin machinery but not
the obscure, little-used HashSetOp.

This seems like a pretty bad solution. It would imply exporting the
complexities of duplicate-counting for EXCEPT ALL and INTERSECT ALL
modes into the hash-join logic. We don't need that extra complexity
there (it's more than enough of a mess already), and we don't need
whatever performance hit ordinary hash joins would take.

If Hash Joins did support IS NOT DISTINCT FROM clauses, then at least
the non-ALL cases could be done with Hash Semi Join and Hash Anti Join
for INTERSECT and EXCEPT, respectively, followed by a HashAgg. I doubt
it would be any faster for the general case, but at least it would
allow those setop queries to run when the inputs don't fit in memory.
It's not ideal though, as when the planner underestimates, Hashed
Setops could still blow up.

David

David Rowley <dgrowleyml@gmail.com> writes:

If Hash Joins did support IS NOT DISTINCT FROM clauses, then at least
the non-ALL cases could be done with Hash Semi Join and Hash Anti Join
for INTERSECT and EXCEPT, respectively, followed by a HashAgg. I doubt
it would be any faster for the general case, but at least it would
allow those setop queries to run when the inputs don't fit in memory.
It's not ideal though, as when the planner underestimates, Hashed
Setops could still blow up.

Yeah. As I hinted before, I think a better answer would be to teach
TupleHashTables to be able to spill to disk at need. No idea how
much work that would be, but it would fix all users of that code
not just one of them.

regards, tom lane

I wrote:

* create_setop_path's required-space estimate of entrysize * numGroups
was rather lame before commit 5dfc19814, and it's even more so
afterwards. It's basically only accounting for the tuples themselves,
and not either the hashtable overhead or the SetOpStatePerGroupData
counter space. With wide tuples that might disappear into the noise,
but with only 16-ish data bytes per tuple it's all about the overhead.
On my machine this example uses 80 bytes per tuple in the "SetOp hash
table" context and another 16 or more in the simplehash hashtable.
So about triple what the planner thought.

* To do better, we probably need to take this computation out of the
planner and have execGrouping.c expose a function to estimate the
TupleHashTable size for N entries and such-and-such average data
width. That in turn will require simplehash.h to expose a function
for estimating the size of its tables, because AFAICS its callers are
not supposed to know such details.

Here's a pair of patches to try to do better. The first one
is concerned with getting more realistic size estimates for
TupleHashTables in the planner. The second is some mop-up
that's been pending for a long time in the same area, namely
getting rid of "long int" field types in Plan nodes.

With 0001, the planner's estimate of the amount of space needed
for your example query seems to be pretty dead-on, at least in
non-debug builds.

regards, tom lane

I wrote:

Here's a pair of patches to try to do better. The first one
is concerned with getting more realistic size estimates for
TupleHashTables in the planner. The second is some mop-up
that's been pending for a long time in the same area, namely
getting rid of "long int" field types in Plan nodes.

Meh ... cfbot found a compiler warning that I'd not seen locally.
v2 attached silences that, and I twiddled a couple of comments.

regards, tom lane

On Sat, 1 Nov 2025 at 08:22, Tom Lane <tgl@sss.pgh.pa.us> wrote:

I wrote:

Here's a pair of patches to try to do better. The first one
is concerned with getting more realistic size estimates for
TupleHashTables in the planner. The second is some mop-up
that's been pending for a long time in the same area, namely
getting rid of "long int" field types in Plan nodes.

I had a look at the v2 patches. Mostly quibbles, but #4 seems like an oversight.

0001:

1) For the following:

+    tuples_space = nentries * (MAXALIGN(SizeofMinimalTupleHeader) +
+                               MAXALIGN(tupleWidth) +
+                               MAXALIGN(additionalsize));

If I'm not mistaken, technically that should be
MAXALIGN(SizeofMinimalTupleHeader + tupleWidth) +
MAXALIGN(additionalsize), but in reality it should come out the same
since SizeofMinimalTupleHeader is 16. If that were to change then I
believe the extra MAXALIGN would start overestimating the memory.

2) Would it be better to reference the function name
"buildSubPlanHash" instead of "above" in:

+ * Adjust the rowcount estimate in the same way as above, except that we

I think "above" is ok when it's the same function, but when it's
talking about another function, it's a recipe for becoming outdated.
It'd be better using the function name so we can grep for that when do
refactor work, else we end up with commits like e3a0304eb...

3) Quite a collection of naming styles here.

+Size
+EstimateTupleHashTableSpace(double nentries,
+                            Size tupleWidth,
+                            Size additionalsize)
+{
+    Size        sh_space;
+    double        tuples_space;

4) I think this is missing a "/ SH_FILLFACTOR"

+ /* should be safe to convert to uint64 */
+ size = (uint64) nentries;

i.e do what SH_CREATE does.

0002:

5) Is it switching "Max(nbuckets, 1);" to "nbuckets" in
hash_choose_num_buckets(). Looks like BuildTupleHashTable() will do
that part for us.

David

David Rowley <dgrowleyml@gmail.com> writes:

I had a look at the v2 patches. Mostly quibbles, but #4 seems like an oversight.

Thanks for reviewing!

1) For the following:
+    tuples_space = nentries * (MAXALIGN(SizeofMinimalTupleHeader) +
+                               MAXALIGN(tupleWidth) +
+                               MAXALIGN(additionalsize));
If I'm not mistaken, technically that should be
MAXALIGN(SizeofMinimalTupleHeader + tupleWidth) +
MAXALIGN(additionalsize),

No, I think it's correct as written: the data payload of a tuple
must always start on a MAXALIGN boundary. As you say, it doesn't
matter as long as SizeofMinimalTupleHeader is 16, but I think this
way is formally correct. (It would matter more if we were trying
to account for tuples' null bitmaps ...)

2) Would it be better to reference the function name
"buildSubPlanHash" instead of "above" in:
+ * Adjust the rowcount estimate in the same way as above, except that we

Done.

3) Quite a collection of naming styles here.

Yeah :-( ... we work in an old and none-too-consistent code base.
Do you have any specific suggestions about which of these functions
might fit its surroundings better with a different caps style?

4) I think this is missing a "/ SH_FILLFACTOR"
+ /* should be safe to convert to uint64 */
+ size = (uint64) nentries;
i.e do what SH_CREATE does.

Oh! I think I got confused because some of that logic is in
SH_CREATE and some in SH_COMPUTE_SIZE :-(. Good catch.

5) Is it switching "Max(nbuckets, 1);" to "nbuckets" in
hash_choose_num_buckets(). Looks like BuildTupleHashTable() will do
that part for us.

Yeah, we could do that. I was trying to not touch more of nodeAgg
than I had to, but it seems sensible to not duplicate something
that BuildTupleHashTable will do.

v3 attached.

regards, tom lane

On Mon, 3 Nov 2025 at 05:26, Tom Lane <tgl@sss.pgh.pa.us> wrote:

v3 attached.

I reviewed the changes. Looks good to me.

David

David Rowley <dgrowleyml@gmail.com> writes:

On Mon, 3 Nov 2025 at 05:26, Tom Lane <tgl@sss.pgh.pa.us> wrote:

v3 attached.

I reviewed the changes. Looks good to me.

Thanks again! I'll get that pushed shortly.

regards, tom lane