Thread: Reference to - BUG #18349: ERROR: invalid DSA memory alloc request size 1811939328, CONTEXT: parallel worker

Craig Milhiser <craig@milhiser.com> writes:
> Has the referenced bug in this discussion[1] been released?

I don't see any indication, either in that thread or in the commit
log, that anything has been done in this area since about 16.2.
It's not an easy problem in general.

Having said that, Aurora is not Postgres, and I don't know
how closely they track us.  Can you reproduce this problem
on a stock build of community Postgres?

            regards, tom lane

On Mon, Sep 23, 2024 at 12:52 PM Craig Milhiser <craig@milhiser.com> wrote:
> On Sun, Sep 22, 2024 at 11:02 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Craig Milhiser <craig@milhiser.com> writes:
>> > Has the referenced bug in this discussion[1] been released?
>>
>> I don't see any indication, either in that thread or in the commit
>> log, that anything has been done in this area since about 16.2.
>> It's not an easy problem in general.
>>
>> Having said that, Aurora is not Postgres, and I don't know
>> how closely they track us.  Can you reproduce this problem
>> on a stock build of community Postgres?
>>
>>                         regards, tom lane
>
>
> Thanks.  I will work on setting that up.  Also getting the aws team involved.
>
> The one query I investigated I rewrote. It took 15 seconds without parallel to avoid this issue. I rewrote it and now
thequery completes in 0.2 seconds. For this query I can avoid the issue, at least temporarily, by making a better
query. But we need to solve the real problem. And I have not looked at the other queries affecting me.  I may not get
solucky again. 
>
> I will post when I get the stock Postgres setup and running.

Hi,

FYI this is on my radar and it would be good to try to make a small
back-patchable improvement.  I would need to swap the problem back
into memory to be sure but from memory the problem is that parallel
hash join partitions take 432 bytes of book keeping memory each (there
is also the problem that they each have output buffers, but those are
not allocated in one big array, and for non-parallel hash join there
is also a per-partition overhead, but it's smaller due to less
bookkeeping state so we don't hear about it).  Hash joins use
partition files (AKA batches) to try to keep each hash table under
work_mem * hash_mem_multiplier, and if you have 2^22 (~4 million)
partitions we therefore try to allocate 1811939328 bytes of memory
(the number in $SUBJECT), exceeding our arbitrary 1GB allocation
limit.  It's possible to turn that arbitrary allocation limit off, but
that'd be treating a symptom and certainly not really produce good
performance.  If you increased (probably at least by double) work_mem
or hash_mem_multiplier, you might have better luck: at some cross-over
point, doubling the size of the array of partitions uses more memory
than you can save by (potentially) halving the size of the hash table!
 Even aside from that arithmetic problem, anything more than around
2^10 partitions (~1 thousand) will start to perform worse unless you
also increase max_files_per_process to match, because every flush of a
page of spill file will likely have to close and open a file (on stock
PostgreSQL at least, but Aurora may have a completely different scheme
for temporary spill data for all I know).  So we could simply cap the
number of partitions, and start ignoring the work_mem *
hash_mem_multiplier limit beyond that cap, but we haven't done it yet
because it's hard to pick a number and reports are rare (ie very large
queries run with low work_mem, if that is indeed the problem here).
2^21 would be the highest plausible candidate (2^21 * 432 = ~900MB),
but it's still very high.  There is a related problem of extreme skew
(squillions of tuples in one bucket), which is much harder to treat,
but ideas were mentioned in that and other threads...  For the
non-skewed version of the problem, which may be more common, at one
level at least the problem is the defaults being set for small memory
machines, people running increasingly huge joins on huge memory
machines, and the machinery to make it work being a bit naive and
excessively expensive.  We could and should invent better strategies
for coping.

On Mon, Sep 23, 2024 at 1:46 PM Thomas Munro <thomas.munro@gmail.com> wrote:
> 432 bytes

Oh, as Tomas pointed out in the referenced thread, the actual number
depends on the number of workers because there is some per-worker
state for partitions, but that number does seem consistent with your
reported case.  Perhaps the correct answer is simply to give up
partitioning when the partition state size would exceed the potential
hash table savings by further partitioning.  Another question is
whether it's arriving at the problematic number by underestimating and
then repeatedly expanding, which is very inefficient, or planning the
high number from the outset, but either way that'd be two different
code paths that would need to respect a new cap.  If it's the former,
there may also be ways to improve initial estimates with statistics.

On Mon, Sep 30, 2024 at 12:03 PM Craig Milhiser <craig@milhiser.com> wrote:
> I reproduced the issue on v17. I downloaded the source tarball, built it, passed tests, put my production database,
analyzedand ran the query. As you expected, the same issue occurred. I have opened the incident with the AWS team as
well.

Since you're building from source, you could try applying the patch
posted by Andrei Lephikov:

https://www.postgresql.org/message-id/7d763a6d-fad7-49b6-beb0-86f99ce4a6eb%40postgrespro.ru

I suspect we may want to limit it to a smaller number than that, as
mentioned already, and I think we should also apply the same cap to
the initial estimate (Andrei's patch only caps it when it decides to
increase it, not for the initial nbatch number).  I can write a patch
like that in a few days when I return from travelling, and we can aim
to get it into the November release, but I suspect Andrei's patch
might already avoid the error for your case.

On 2/10/2024 02:12, Craig Milhiser wrote:
>  > Since you're building from source, you could try applying the patch
>  >posted by Andrei Lephikov:
>  > 
> https://www.postgresql.org/message-id/7d763a6d-fad7-49b6-beb0-86f99ce4a6eb%40postgrespro.ru
<https://www.postgresql.org/message-id/7d763a6d-fad7-49b6-beb0-86f99ce4a6eb%40postgrespro.ru>
> 
> This did not work for me. I am running out of memory.
Can you provide an explain of this query? Also, can you remove 
unnecessary details from the query text like temporary view or CASE .. 
WHEN construction, if the OOM still reproduces.

-- 
regards, Andrei Lepikhov

On 10/7/24 18:42, Craig Milhiser wrote:
> 
>     On Oct 1, 2024 Andrei Lepikhov wrote
> 
>  > Can you provide an explain of this query?
> 
> Apologies for the delay. I have been travelling since Wednesday night. 
> Thanks for your help and time with this issue.
> 
> Below is the query, with specific values redacted. An explain with 
> max_parallel_workers_per_gather = 2 and explain analyze 
> max_parallel_workers_per_gather = 0.
I'm a bit confused: the thread subject named ' invalid DSA memory alloc 
request size ...', but you write about issue with OOM killer. It is two 
different issues, which one do you have exactly?

OOM killer can be explained easily, because I see huge string_agg 
aggregate - workers can utilise memory more intensively. For now, 
explain of an Aggregate node don't show information about factual sort 
operation of each aggregate and memory consumption.

-- 
regards, Andrei Lepikhov

On Thu, Oct 10, 2024 at 5:28 AM Craig Milhiser <craig@milhiser.com> wrote:
> Then the machine ran out of disk space: ERROR:  could not write to file
"base/pgsql_tmp/pgsql_tmp4942.1.fileset/o1859485of2097152.p0.0":No space left on device 

For that, I have a patch in the queue to unlink temporary files incrementally:

https://www.postgresql.org/message-id/flat/CA+hUKG+RGdvhAdVu5_LH3Ksee+kW-XkTP_nMxBL+Rmgp3Tjb_w@mail.gmail.com

That's just treating a symptom, though.  Things have already gone
quite wrong if we're repeatedly repartitioning our way up to 2 million
batches and only giving up there because of Andrei's patch.

I wonder if there something could be wrong with Parallel Hash Right
Join, which we see in your plan.  That's new-ish, and I vaguely recall
another case where that seemed to be on the scene in a plan with a
high number of batches... hmm.  Definitely keen to see a reproducer
with synthetic data if you can come up with one...

On 10/9/24 23:28, Craig Milhiser wrote:
> On Oct 8 Andrei Lepikhov wrote
>  > I'm a bit confused: the thread subject named ' invalid DSA memory alloc
>  > request size ...', but you write about issue with OOM killer. It is two
>  > different issues, which one do you have exactly?
> 
> 
> I started with the Invalid DSA memory allocation error. I was asked to 
> try an experimental patch above. Then I got OOM with the patch only 
> running parallel. You will see below, there was an OOM but I do not 
> believe it is the query.
So, I think the patch works, but you found out one more issue at the 
same query. Awesome!

> I ran a new test on an instance with 512 GiB of memory.  After I applied 
> the patch, the Invalid DSA memory allocation message was not 
> replicated.  Running max_parallel_workers_per_gather = 0, the query took 
> ~9.5 seconds and used <1 GiB of memory.  With 
> max_parallel_workers_per_gather = 2 the query used  ~170 GiB of memory, 
> ~70 GB of temp files were written and the query ran for more than 1 hour 
> until I ran out of disk space.
It's fascinating. I have one user report like that, but they also didn't 
provide any synthetic test. I think it is almost impossible to create 
such reproduction without a minimal understanding of what's happening. I 
can imagine only a data skew or a logical bug in this part of the code. 
But without direct perf and gdb touch, it is hard to resolve the issue 
by just gazing into the code.
Additional actions can provide some food for thought:
1. If you remove aggregates (STRING_AGG, count) from the selection list, 
will the problem remain? What about OFFSET 0?
2. Can you build extended statistics on account_id,disabled,user_type_id 
and provide an explain (and explain analyse)?
3. Can you use pg_query_state (unfortunately, it needs a patch and 
re-compilation) and show us intermediate execution state snapshots?
4. I see a duplicate clause in the query: SGM.OBJECT_ID = U.OBJECT_ID. 
For what reason you have it here? can you remove it from the query?
5. One more wild guess: can you analyse how much NULLS contains column 
u.users_id at the moment when HashJoin evaluates clause (u.users_id = 
cf.user_id)?

[1] https://github.com/postgrespro/pg_query_state

-- 
regards, Andrei Lepikhov

On Mon, Oct 14, 2024 at 12:23 AM Craig Milhiser <craig@milhiser.com> wrote:
> I have reproduced the problem with synthetic data. The script is below. Thank you for your patience with me.

Thanks, repro'd here.  At first glance, it looks like it's trying to
load this distribution into a hash table and failing to handle the
skew as well as non-parallel hash:

postgres=# select user_image_id, count(*) from test_users where
account_id = -1 group by 1 order by 2 desc limit 5;
 user_image_id | count
---------------+--------
               | 878823  <-- choking on this?
       -924960 |      1
       -924934 |      1
       -924917 |      1
       -924971 |      1
(5 rows)

                           ->  Parallel Hash Right Join
(cost=1027177.72..1368758.97 rows=363544 width=82)
                                 Hash Cond: (ui.user_image_id = u.user_image_id)
                                 ->  Parallel Seq Scan on
test_user_image ui  (cost=0.00..215192.79 rows=10436379 width=8)
                                 ->  Parallel Hash
(cost=1017662.42..1017662.42 rows=363544 width=82)
                                       ->  Parallel Seq Scan on
test_users u  (cost=0.00..1017662.42 rows=363544 width=82)
                                             Filter: (account_id =
'-1'::integer)


Getting coffee and looking more closely...

On 10/14/24 04:08, Thomas Munro wrote:
> On Mon, Oct 14, 2024 at 12:23 AM Craig Milhiser <craig@milhiser.com> wrote:
>> I have reproduced the problem with synthetic data. The script is below. Thank you for your patience with me.
> 
> Thanks, repro'd here.  At first glance, it looks like it's trying to
> load this distribution into a hash table and failing to handle the
> skew as well as non-parallel hash:
> Getting coffee and looking more closely...
Hmm, with reproduction, it is too easy to solve ;)
My explanation (correct if I'm wrong):
OUTER JOINs allow NULLs to be in a hash table. At the same time, a hash 
value for NULL is 0, and it goes to the batch==0.
If batch number 0 gets overfilled, the 
ExecParallelHashIncreaseNumBatches routine attempts to increase the 
number of batches - but nothing happens. The initial batch is still too 
big, and the number of batches doubles up to the limit.
At the limit, parallel HashJoin stops this grow and (I didn't trace this 
part, just guess) allocates memory for 2097152 batches that causes OOM.
To support this chain of thought, you can see the simple example below, 
which triggers the issue:

DROP TABLE IF EXISTS test;
CREATE TABLE test (n int);
INSERT INTO test (n) SELECT NULL FROM generate_series(1,1E6);
INSERT INTO test (n) VALUES (1, 'a');
ANALYZE test;

SET enable_nestloop = 'off';
SET enable_mergejoin = 'off';

SET max_parallel_workers_per_gather = 2;
SET min_parallel_table_scan_size = 0;
SET min_parallel_index_scan_size = 0;
SET parallel_setup_cost = 0.001;
SET parallel_tuple_cost = 0.0001;

EXPLAIN (ANALYZE, VERBOSE, COSTS OFF)
SELECT t1.n FROM test t1 LEFT JOIN test t2 USING (n);

I think, now it is much easier to find a proper solution.

-- 
regards, Andrei Lepikhov

Andrei Lepikhov <lepihov@gmail.com> writes:
> My explanation (correct if I'm wrong):
> OUTER JOINs allow NULLs to be in a hash table. At the same time, a hash 
> value for NULL is 0, and it goes to the batch==0.
> If batch number 0 gets overfilled, the 
> ExecParallelHashIncreaseNumBatches routine attempts to increase the 
> number of batches - but nothing happens. The initial batch is still too 
> big, and the number of batches doubles up to the limit.

Interesting point.  If memory serves (I'm too tired to actually look)
the planner considers the statistical most-common-value when
estimating whether an unsplittable hash bucket is likely to be too
big.  It does *not* think about null values ... but it ought to.

However, this does not explain why PHJ would be more subject to
the problem than non-parallel HJ.

            regards, tom lane

On 10/16/24 16:19, Thomas Munro wrote:
> On Mon, Oct 14, 2024 at 10:16 PM Andrei Lepikhov <lepihov@gmail.com> wrote:
>> See the attachment for a sketch of the solution.
> 
> Thanks Andrei, I mostly agree with your analysis, but I came up with a
> slightly different patch.  I think we should check for extreme skew if
> old_batch->space_exhausted (the parent partition).  Your sketch always
> does it for batch 0, which works for these examples but I don't think
> it's strictly correct: if batch 0 didn't run out of memory, it might
> falsely report extreme skew just because it had (say) 0 or 1 tuples.
Yeah, I misunderstood the meaning of the estimated_size variable. Your 
solution is more universal. Also, I confirm, it passes my synthetic  test.
Also, it raises the immediate question: What if we have too many 
duplicates? Sometimes, in user complaints, I see examples where they, 
analysing the database's logical consistency, pass through millions of 
duplicates to find an unexpected value. Do we need a top memory 
consumption limit here? I recall a thread in the mailing list with a 
general approach to limiting backend memory consumption, but it is 
finished with no result.
The patch looks good as well as commentary.

-- 
regards, Andrei Lepikhov

On Thu, Oct 17, 2024 at 9:12 PM Andrei Lepikhov <lepihov@gmail.com> wrote:
> Yeah, I misunderstood the meaning of the estimated_size variable. Your
> solution is more universal. Also, I confirm, it passes my synthetic  test.
> Also, it raises the immediate question: What if we have too many
> duplicates? Sometimes, in user complaints, I see examples where they,
> analysing the database's logical consistency, pass through millions of
> duplicates to find an unexpected value. Do we need a top memory
> consumption limit here? I recall a thread in the mailing list with a
> general approach to limiting backend memory consumption, but it is
> finished with no result.

It is a hard problem alright[1].

> The patch looks good as well as commentary.

Thanks, I will go ahead and push this now.

[1] https://www.postgresql.org/message-id/flat/CAAKRu_aLMRHX6_y%3DK5i5wBMTMQvoPMO8DT3eyCziTHjsY11cVA%40mail.gmail.com

On 10/17/24 15:57, Thomas Munro wrote:
> On Thu, Oct 17, 2024 at 9:12 PM Andrei Lepikhov <lepihov@gmail.com> wrote:
>> Yeah, I misunderstood the meaning of the estimated_size variable. Your
>> solution is more universal. Also, I confirm, it passes my synthetic  test.
>> Also, it raises the immediate question: What if we have too many
>> duplicates? Sometimes, in user complaints, I see examples where they,
>> analysing the database's logical consistency, pass through millions of
>> duplicates to find an unexpected value. Do we need a top memory
>> consumption limit here? I recall a thread in the mailing list with a
>> general approach to limiting backend memory consumption, but it is
>> finished with no result.
> 
> It is a hard problem alright[1].
> 
>> The patch looks good as well as commentary.
> 
> Thanks, I will go ahead and push this now.
> 
> [1]
https://www.postgresql.org/message-id/flat/CAAKRu_aLMRHX6_y%3DK5i5wBMTMQvoPMO8DT3eyCziTHjsY11cVA%40mail.gmail.com
Thanks for the link.
BTW, why not to use current case and fix the problem with the 'invalid 
DSA memory alloc request size 1811939328' itself ?

-- 
regards, Andrei Lepikhov

On Thu, Oct 17, 2024 at 10:48 PM Andrei Lepikhov <lepihov@gmail.com> wrote:
> BTW, why not to use current case and fix the problem with the 'invalid
> DSA memory alloc request size 1811939328' itself ?

I think your patch is good but if you don't mind I'd like to think
about how to generalise it a bit first, so that it applies to all
places where we choose nbatch, not just repartitioning.  Unfortunately
that's a bit circular so I'm still thinking about the tidiest way to
do it... might take a few days due to travel, and if I don't have
something soon I guess your patch is better than nothing (it might be
the most common way we finish up in that sort of trouble).

I'll also push that other patch that cleans up temporary files
aggressively soon (master only), and try to think about some simple
ways to avoid large nbatch values that contradict the goal of reducing
memory for non-skew cases at planning and execution time (probably
master only)...

On 18/10/2024 06:34, Thomas Munro wrote:
> On Thu, Oct 17, 2024 at 10:48 PM Andrei Lepikhov <lepihov@gmail.com> wrote:
>> BTW, why not to use current case and fix the problem with the 'invalid
>> DSA memory alloc request size 1811939328' itself ?
> 
> I think your patch is good but if you don't mind I'd like to think
> about how to generalise it a bit first, so that it applies to all
> places where we choose nbatch, not just repartitioning.  Unfortunately
> that's a bit circular so I'm still thinking about the tidiest way to
> do it... might take a few days due to travel, and if I don't have
> something soon I guess your patch is better than nothing (it might be
> the most common way we finish up in that sort of trouble).
Thanks. I thought about generalisation, but who knows how the caller 
wants to react in the case of unsuccessful allocation? Should we force 
the user to compare the size requested and allocated? Maybe. I'll wait 
for your solution.
> 
> I'll also push that other patch that cleans up temporary files
> aggressively soon (master only),
Have been waiting for this!
> and try to think about some simple
> ways to avoid large nbatch values that contradict the goal of reducing
> memory for non-skew cases at planning and execution time (probably
> master only)...
Hmm, cost-based maximum number of batches defined at the optimisation stage?

-- 
regards, Andrei Lepikhov