BUG #19759: Hashed SetOp / RecursiveUnion pre-allocate up to 64 GB from the row estimate since 8f29467c57f

Hi Alperen,

On Thu, 15 Oct 2026 at 13:44, PG Bug reporting form
<noreply@postgresql.org> wrote:

Since commit 8f29467c57f ("Change "long" numGroups fields to be
Cardinality (i.e., double)", 2025-11-02), BuildTupleHashTable() no
longer limits the initial size of a TupleHashTable to hash_mem.

Confirmed on master aa7b9cf132b and REL_19_STABLE 0fb192f1b02 (19rc1),
meson debug build with cassert, Debian trixie, server under
ulimit -v 6 GB. The recursive UNION asks for 68719476736 bytes and the
EXCEPT with enable_sort = off for 34359738368. The 1M-row recursive
UNION peaks at 1094 MB, against 33 MB for the same query with UNION
ALL. The official 17.11 and 18.6 images run all of them fine.

On macOS 26.6 arm64 (native autoconf debug builds, no ulimit since
macOS ignores it) master grows past 4 GB on the same queries before I
kill the backend. The 10M-row recursive UNION peaks at 8599 MB on
master and 977 MB on REL_18_STABLE.

Two more ways to reach it:

1. Plain EXPLAIN, without ANALYZE, fails the same way, since the table
is built in ExecInitSetOp and ExecInitRecursiveUnion. nodeAgg skips
it under EXEC_FLAG_EXPLAIN_ONLY since 2cccb627f10.

2. A column type that can be hashed but not sorted leaves HashSetOp as
the only plan, so no setting change is needed:

SELECT a.c0::text::xid, b.c0, c.c0, d.c0
FROM t0 a, t0 b, t0 c, t0 d
EXCEPT SELECT '1'::xid, 2, 3, 4;

asks for 34359738368 bytes on master with default settings.

EXCEPT ALL, INTERSECT and INTERSECT ALL behave the same.

EXCEPT ALL does. INTERSECT and INTERSECT ALL with your query do not
fail for me: the right side has one row, so the planner estimates one
group. With the 4-way cross join on both sides, INTERSECT asks for
34359738368 bytes too.

Everything above also reproduces on the macOS builds: on master the
backend grows past 4 GB and I kill it, while REL_18_STABLE runs it all
fine.

The backtrace (backtrace_functions = 'MemoryContextAllocationFailure')
goes tuplehash_create <- BuildTupleHashTable <- ExecInitRecursiveUnion
or ExecInitSetOp, in both SELECT and EXPLAIN.

For the history: the cap came from 299d1716525 (2011, BUG #6035), whose
message says huge numGroups values reach BuildTupleHashTable "in cases
where we have no alternative to building a hashtable". 1ea5bdb00bf says
the same about RecursiveUnion: it has no non-hashed implementation, and
its estimate of the number of entries is "so suspect". So the planner
cannot keep these tables under hash_mem, as 8f29467c57f expects it to.
nodeAgg still bounds its initial size in hash_choose_num_buckets().

The attached script reproduces the Linux numbers with psql only. It
needs a superuser and reads /proc/self/status for the backend's peak
RSS.

Disclosure: I used Claude Opus 5.5 (reasoning medium) for the analysis
and tests. Codex gpt-6.1-sol (reasoning high) checked independently
whether this could be by design. I reviewed the results.

Regards,
Sebastian

Em qui., 15 de out. de 2026 às 10:47, PG Bug reporting form <
noreply@postgresql.org> escreveu:

The following bug has been logged on the website:

Bug reference: 19759
Logged by: Alperen Keles
Email address: alpkeles99@gmail.com
PostgreSQL version: 19beta4
Operating system: Ubuntu 24.04 x86_64 (also macOS 26 arm64)
Description:

Since commit 8f29467c57f ("Change "long" numGroups fields to be Cardinality
(i.e., double)", 2025-11-02), BuildTupleHashTable() no longer limits the
initial size of a TupleHashTable to hash_mem. Its new comment says that
staying within hash_mem is the caller's job. But nodeRecursiveunion.c and
nodeSetOp.c pass the planner's raw group estimate, so the executor now
allocates and zeroes a bucket array of up to 2^32 entries x 16 bytes =
64 GB in ExecInit, before reading a single row, whenever the estimate is
large. PostgreSQL 18 is not affected (it capped nbuckets at
get_hash_memory_limit() / entrysize). The commit is in REL_19_BETA1
through REL_19_RC1.

Two ways to reach it:

1. Recursive UNION, default settings. It can only be hashed, and
generate_recursion_path() estimates its groups as lrows + 10 * rrows,
so an inflated estimate goes straight into the allocation. With an
empty, never-analyzed table:

CREATE TABLE t0(c0 int4);
WITH RECURSIVE r(w, x, y, z) AS (
SELECT a.c0, b.c0, c.c0, d.c0 FROM t0 a, t0 b, t0 c, t0 d
UNION
SELECT w, x, y, z FROM r WHERE false)
SELECT count(*) FROM r;

On master (49103c3cd63, Ubuntu 24.04, x86_64, the server under
ulimit -v 6 GB):

ERROR: 53200: out of memory
DETAIL: Failed on request of size 68719476736 in memory context
"ExecutorState".
LOCATION: MemoryContextAllocationFailure, mcxt.c:1208

Without a memory limit the backend simply allocates it: on macOS its
RSS passed 3 GB within a few milliseconds. On 18.6 the query returns 0
at once.

An accurate estimate is enough to see the difference, without any
tables:

WITH RECURSIVE r(n) AS (
SELECT g FROM generate_series(1, 1000000) g
UNION SELECT n + 1 FROM r WHERE n < 0)
SELECT count(*) FROM r;

Peak backend RSS: 1086 MB on master, 115 MB on 18.6 (same result).
With 10 million rows master allocates 8 GB up front, while 18.6 peaks
at about 1 GB.

2. Hashed set operations whose table the planner itself expects to
exceed hash_mem. create_setop_path() only marks such a path disabled,
so it is chosen when the sorted alternative is disabled even more,
e.g. with enable_sort = off:

BEGIN;
SET LOCAL enable_sort = off;
SELECT a.c0, b.c0, c.c0, d.c0 FROM t0 a, t0 b, t0 c, t0 d
EXCEPT SELECT 1, 2, 3, 4;
ROLLBACK;

EXPLAIN shows "HashSetOp Except ... rows=1600000000 ... Disabled: true".
On master it tries to allocate 32 GB (2^31 buckets) and fails or
exhausts memory; on 18.6 it returns no rows in about 2 ms. EXCEPT ALL,
INTERSECT and INTERSECT ALL behave the same.

Versions tested:
- master 158b6d5109f (macOS 26, arm64, Apple clang 21) and 49103c3cd63
(Ubuntu 24.04, x86_64, gcc 13.3), both --enable-cassert --enable-debug
- REL_18_STABLE a85b5523e67 (18.6, macOS): not affected
Rechecked on 2026-10-15 (Ubuntu 24.04, x86_64, gcc 13.3, --enable-cassert
--enable-debug, server under ulimit -v 6 GB) on 19rc1
(REL_19_STABLE 0fb192f1b02), current master aa7b9cf132b and
REL_18_STABLE 4d62ef92fda (18.6): on 19rc1 and master the three queries
above fail with requests of 34359738368, 68719476736 and 8589934592
bytes, and the 1M-row recursive UNION peaks at 1088 MB; on 18.6 all
three succeed and that query peaks at 103 MB.

Found with a query fuzzer.

--
Sebastian Webber

On Fri, 16 Oct 2026 at 02:47, PG Bug reporting form
<noreply@postgresql.org> wrote:

Since commit 8f29467c57f ("Change "long" numGroups fields to be Cardinality
(i.e., double)", 2025-11-02), BuildTupleHashTable() no longer limits the
initial size of a TupleHashTable to hash_mem. Its new comment says that
staying within hash_mem is the caller's job. But nodeRecursiveunion.c and
nodeSetOp.c pass the planner's raw group estimate, so the executor now
allocates and zeroes a bucket array of up to 2^32 entries x 16 bytes =
64 GB in ExecInit, before reading a single row, whenever the estimate is
large. PostgreSQL 18 is not affected (it capped nbuckets at
get_hash_memory_limit() / entrysize). The commit is in REL_19_BETA1
through REL_19_RC1.

Looking back at the changes made in 8f29467c5 and looking at the
estimation code in generate_recursion_path(), I think we're dreaming
if we think we can avoid capping planner estimates in the executor.
There's an argument for doing that in the planner, but plans can be
cached, and we don't replan when work_mem or the hash_mem_multiplier
changes, so I think keeping some logic in BuildTupleHashTable() is
sensible. Queries being slightly slower due to the hash table having
to grow a few times seems much better than OOM because of the planner
not having enough information to make an informed estimate.

I've tried to do that in the attached and incorporated the capping to
UINT32_MAX that Tom added in 8f29467c5. The calculation still doesn't
account for the tuple width, but if we were to try to include that as
part of the calculation is means making the cap calculation
susceptible to planner estimates. That seems weird since the whole
point of the cap is to protect against crazy planner estimates.

David

On Fri, 16 Oct 2026 at 02:47, PG Bug reporting form
<noreply@postgresql.org> wrote:

Since commit 8f29467c57f ("Change "long" numGroups fields to be Cardinality
(i.e., double)", 2025-11-02), BuildTupleHashTable() no longer limits the
initial size of a TupleHashTable to hash_mem. Its new comment says that
staying within hash_mem is the caller's job. But nodeRecursiveunion.c and
nodeSetOp.c pass the planner's raw group estimate, so the executor now
allocates and zeroes a bucket array of up to 2^32 entries x 16 bytes =
64 GB in ExecInit, before reading a single row, whenever the estimate is
large. PostgreSQL 18 is not affected (it capped nbuckets at
get_hash_memory_limit() / entrysize). The commit is in REL_19_BETA1
through REL_19_RC1.

I've added an open item for this to ensure it's not forgotten.

David

Hi David,

The patch fixes the cases from the report for me. Two small things.

1. simplehash rounds the size up to a power of 2, so the empty table
can still be twice hash_mem. With work_mem = 1GB, a plain EXPLAIN of
the recursive query zeroes 4 GB. Halving the limit fixes it.
hash_choose_num_buckets() does the same.

2. Plain EXPLAIN still builds the table. nodeAgg skips it.

The attached patch on top of yours does both.

Thanks,
Shihao