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

Поиск
Список
Период
Сортировка
Искать

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

От:
PG Bug reporting form <noreply@postgresql.org>
Дата:
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.




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

От:
Sebastian Webber <sebastian@swebber.me>
Дата:
Вложения:
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

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

От:
David Rowley <dgrowleyml@gmail.com>
Дата:
Вложения:
On Fri, 16 Oct 2026 at 02:47, PG Bug reporting form
 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

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

От:
David Rowley <dgrowleyml@gmail.com>
Дата:
On Fri, 16 Oct 2026 at 02:47, PG Bug reporting form
 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


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

От:
shihao zhong <zhong950419@gmail.com>
Дата:
Вложения:
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

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

От:
David Rowley <dgrowleyml@gmail.com>
Дата:
Thanks for the review.

On Sat, 24 Oct 2026 at 17:48, shihao zhong  wrote:
> 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.

While it is true that simplehash will make the bucket count the next
power of 2 value, I didn't do this as I wanted to restore what we did
prior to 8f29467c5 in terms of the hard limit.

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

Seems unrelated and I don't recall anyone complaining. Not something I
think we should adjust last minute before v19 goes out the door.

Now pushed.

David


FAQ