Subquery pull-up increases jointree search space

Andrei Lepikhov <lepihov@gmail.com> writes:

From time to time, I see user complaints on performance degradation
caused by newly introduced transformation - it is usually related to
correlated subplan transformation as well as trivial initplan → join
transformation.
The original issue (according to my case analysis) is usually that, by
adding such a pull-up optimiser excess join collapse limit. As a result,
the query tree tail, which was previously ordered according to the cost
model, is now determined mechanically, sometimes causing severe
degradation in execution time.

Certainly that's possible, but I doubt it's common enough to justify
putting a lot of work into specialized mechanisms to deal with such
scenarios.

What I'm wondering about is that join_collapse_limit and
from_collapse_limit were invented more than two decades ago, but
we've not touched their default values since then. Machines are a
lot faster since 2004, and we've probably achieved some net speedups
in the planner logic as well. Could we alleviate this concern by
raising those defaults, and if so, what are reasonable values in 2026?

(geqo_threshold should probably be looked at too.)

regards, tom lane

On 9/2/26 21:16, Tom Lane wrote:

Andrei Lepikhov <lepihov@gmail.com> writes:

From time to time, I see user complaints on performance degradation
caused by newly introduced transformation - it is usually related to
correlated subplan transformation as well as trivial initplan → join
transformation.
The original issue (according to my case analysis) is usually that, by
adding such a pull-up optimiser excess join collapse limit. As a result,
the query tree tail, which was previously ordered according to the cost
model, is now determined mechanically, sometimes causing severe
degradation in execution time.

Certainly that's possible, but I doubt it's common enough to justify
putting a lot of work into specialized mechanisms to deal with such
scenarios.

I feel the same. But what is also true is that people complain about
that when migrating from other DBMSes. And it is a common question: why
does the alternative one perform better? What technology lies under the
hood?

That's why I think about some tiny changes to let extension developers
discover the problem and find a workaround. Or we can put pulled-up
relations at the end of the join list to minimise impact on the query
plan during an upgrade.

What's more, where more flaws exist (a typical example is the
limitations of the partition pruning state machine), they may also be
fixed by replanning with alternative settings or other extension tricks,
if the problem can be detected and memorised.

What I'm wondering about is that join_collapse_limit and
from_collapse_limit were invented more than two decades ago, but
we've not touched their default values since then. Machines are a
lot faster since 2004, and we've probably achieved some net speedups
in the planner logic as well. Could we alleviate this concern by
raising those defaults, and if so, what are reasonable values in 2026?

As I see, people never use the default settings now. The case that
triggered this topic could work well with a join collapse limit around
40 joins (GEQO started at 14). But a specific setting always depends on
how much time people want to spend on planning. So, I don't think a
change of default settings is needed.

--
regards, Andrei Lepikhov,
pgEdge

On Mon, Feb 9, 2026 at 3:17 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

What I'm wondering about is that join_collapse_limit and
from_collapse_limit were invented more than two decades ago, but
we've not touched their default values since then. Machines are a
lot faster since 2004, and we've probably achieved some net speedups
in the planner logic as well. Could we alleviate this concern by
raising those defaults, and if so, what are reasonable values in 2026?

The problem as I see it is that the planning time growth is
exponential, and so faster hardware doesn't necessarily buy you very
much, especially given that we've added new planner techniques that
add to the number of paths considered. But I also think that the
degenerate cases are much worse than the typical cases. For example, I
seem to remember things like A LEFT JOIN (B1 INNER JOIN B2 INNER JOIN
B3...) LEFT JOIN (C1 INNER JOIN C2 INNER JOIN C3...) [repeat with D,
E, etc.] being a problem, maybe for GEQO, because a
randomly-determined join order isn't likely to be valid. I think there
are similar issues with join_collapse_limit etc, for example because
we prefer joins that have joinclauses over those that don't, so the
actual planner work can be wildly different with the same number of
joins in the query. I suspect the thing that we need in order to be
able to safely raise these thresholds is for somebody to spend some
time figuring out what the pathologically bad cases are and designing
some sort of mitigations specifically for those. Or, alternatively, we
could decide that we've been too pessimistic and set slightly riskier
values by default, expecting that they'll work out most of the time
and that users can lower the setting if there's an issue.

--
Robert Haas
EDB: http://www.enterprisedb.com

On 09/02/2026 23:34, Andrei Lepikhov wrote:

On 9/2/26 21:16, Tom Lane wrote:

What I'm wondering about is that join_collapse_limit and
from_collapse_limit were invented more than two decades ago, but
we've not touched their default values since then.  Machines are a
lot faster since 2004, and we've probably achieved some net speedups
in the planner logic as well.  Could we alleviate this concern by
raising those defaults, and if so, what are reasonable values in 2026?

As I see, people never use the default settings now. The case that triggered
this topic could work well with a join collapse limit around 40 joins (GEQO
started at 14). But a specific setting always depends on how much time people
want to spend on planning. So, I don't think a change of default settings is
needed.

After looking into more cases, I realized the main issue is actually something else.

If a SubLink in the WHERE clause is not turned into a JOIN, it acts as a filter
at the lowest possible level. When we do transform it, we move it to the top of
the join tree. If the collapse limit is lower than the number of joins, we end
up moving its filtering effect outside the ‘join problem’, and the optimiser
cannot take advantage of this often helpful way to execute the query. You can
see a dumb demo in the attachment.

To solve the problem, we should identify the relids that the SubLink refers to
or depends on, ensure they are not on the nullable side of a join, and add them
to the jointree as a JoinExpr with as few relids as possible.

Looking at pull_up_sublinks_qual_recurse, I see that we have information to skip
extra work if the join_collapse_limit is high enough.

--
regards, Andrei Lepikhov,
pgEdge

On 09/05/2026 12:51, Andrei Lepikhov wrote:

On 09/02/2026 23:34, Andrei Lepikhov wrote:

On 9/2/26 21:16, Tom Lane wrote:

What I'm wondering about is that join_collapse_limit and
from_collapse_limit were invented more than two decades ago, but
we've not touched their default values since then.  Machines are a
lot faster since 2004, and we've probably achieved some net speedups
in the planner logic as well.  Could we alleviate this concern by
raising those defaults, and if so, what are reasonable values in 2026?

As I see, people never use the default settings now. The case that triggered
this topic could work well with a join collapse limit around 40 joins (GEQO
started at 14). But a specific setting always depends on how much time people
want to spend on planning. So, I don't think a change of default settings is
needed.

After looking into more cases, I realized the main issue is actually something else.
Looking at pull_up_sublinks_qual_recurse, I see that we have information to skip
extra work if the join_collapse_limit is high enough.

And here is the patch.
The main idea is that after a transformation (EXISTS or ANY), we should not just
initialise the larg of the JoinExpr with the incoming join tree. Instead, we
need to look for minimal subtree. Since we already have relids referenced in the
subselect, we can traverse this subtree to find the smallest safe join tree that
contains these relids. Then, we initialise the larg of our SEMI JOIN JoinExpr
with this subtree and update the larg of the upper JoinExpr to point to our
SemiJoin.

Such behaviour is quite close to the not-pulled-up variant when a subselect is
used as a filter and pushed down to the minimum level needed to evaluate this
SubLink. So, delay the influence of join_collapse_limit as much as possible.

The patch provided contains implementation of the idea - the key function is
insert_pulled_up_sublink_join. It is a little polished with Claude AI - it added
tests to detect any issues during rebase onto master and documentation.

I'll CC Richard, since he often challenges the transformation machinery and may
be interested in helping to stabilise the user experience after the upgrade.

--
regards, Andrei Lepikhov,
pgEdge

On 2/10/26 17:29, Robert Haas wrote:

On Mon, Feb 9, 2026 at 3:17 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

What I'm wondering about is that join_collapse_limit and
from_collapse_limit were invented more than two decades ago, but
we've not touched their default values since then. Machines are a
lot faster since 2004, and we've probably achieved some net speedups
in the planner logic as well. Could we alleviate this concern by
raising those defaults, and if so, what are reasonable values in 2026?

The problem as I see it is that the planning time growth is
exponential, and so faster hardware doesn't necessarily buy you very
much, especially given that we've added new planner techniques that
add to the number of paths considered. But I also think that the
degenerate cases are much worse than the typical cases. For example, I
seem to remember things like A LEFT JOIN (B1 INNER JOIN B2 INNER JOIN
B3...) LEFT JOIN (C1 INNER JOIN C2 INNER JOIN C3...) [repeat with D,
E, etc.] being a problem, maybe for GEQO, because a
randomly-determined join order isn't likely to be valid. I think there
are similar issues with join_collapse_limit etc, for example because
we prefer joins that have joinclauses over those that don't, so the
actual planner work can be wildly different with the same number of
joins in the query. I suspect the thing that we need in order to be
able to safely raise these thresholds is for somebody to spend some
time figuring out what the pathologically bad cases are and designing
some sort of mitigations specifically for those. Or, alternatively, we
could decide that we've been too pessimistic and set slightly riskier
values by default, expecting that they'll work out most of the time
and that users can lower the setting if there's an issue.

Sorry to revive this thread from February, but I've been wondering about
the same thing (possibility to increase join_collapse_limit) in the
context of the starjoin planning thread.

I've decided to do a simple stress-test experiment - generate random
joins of 2-N tables, and measure how long the planning takes. See the
attached python script - it's not super elaborate, the joins are normal
joins (no lateral, no subqueries, ...).

Attached is also a PDF with results. Each dot is one random join, the
charts on the right have log-scale y-axis. I think the conclusion is
increasing join_collapse_limit would require more work. Not just because
of the plan time, but (more importantly?) the memory needed.

There are significant variations, easily 2-3 orders of magnitude, and
it's getting worse with the number of tables. A join of 10 tables can
take 5-1000 ms.

The thing that surprised me a bit is how much memory the larger joins
may need for planning (measured by getrusage and log_planner_stats).
With 8 tables, the backend generally fits into 50MB. But then it
explodes (well, it's exponential, but here it starts to grow a lot), and
with 10 tables we may need 500MB, with 12 it's 5GB, ...

At 13 tables some of the joins start crashing because the machine only
has 64GB of RAM. That's why the chart "levels off" at ~50GB, because the
crashed queries are not included.

FWIW I don't think the joins are particularly nasty. I suspect these are
not the actual "worst" cases, we could probably construct worse ones.

I'm not sure about the plan time - maybe it got much better than it
used to be, either because we optimized some stuff and/or because CPUs
got better (not sure that's sufficient on it's own). But ISTM the memory
usage could be a worse of the two, because it does not make the query
just go slower, it can crash the instance.

So to allow increasing join_collapse_limit, we'd need to address this,
somehow. I have not investigated what exactly uses the memory. Some of
it may be easy to free, but I recall we have difficulties with freeing
some of the stuff because we don't know if it's still referenced.

FWIW I suspect the memory usage may be a significant contributing factor
for the plan time, because I'm seeing asm_exc_page_fault in the profiles
(which reminds me of [1]https://vondra.me/posts/tuning-the-glibc-allocator-for-postgres/). But here mallopt/MALLOC_TOP_PAD_ can't help
with these amounts of memory. So lowering the memory usage might also
help with the plan time quite a bit.

regards

[1]: https://vondra.me/posts/tuning-the-glibc-allocator-for-postgres/

--
Tomas Vondra

On 6/5/26 12:43, Tomas Vondra wrote:

...

So to allow increasing join_collapse_limit, we'd need to address this,
somehow. I have not investigated what exactly uses the memory. Some of
it may be easy to free, but I recall we have difficulties with freeing
some of the stuff because we don't know if it's still referenced.

I was wondering about which places allocate most memory during planning.
I selected a query that allocates a manageable amount (~2.5GB) to plan,
and added some instrumentation to trace alloc/free calls for the
PortalContext (which is the context used by the planner).

Attached are two SQL scripts with the schema and a join query with 12
tables (it increases the join_collapse_limit and disables geqo).

There's also .patch adding the alloc/free trace messages, and a .py
script to aggregate the log messages, and an example summary of the
allocations after the 2.5GB query. For each allocation we know the
backtrace, and so can aggregate allocations per "backtrace".

After classifying the allocations a bit, I see this:

allocation | size
--------------------------------------+----------------
find_mergeclauses_for_outer_pathkeys | 671 MB
generate_join_implied_equalities | 660 MB
add_paths_to_joinrel | 242 MB
make_inner_pathkeys_for_merge | 195 MB
estimate_num_groups | 92 MB
get_joinrel_parampathinfo | 90 MB
create_memoize_path | 48 MB
| 15 MB
calc_nestloop_required_outer | 5226 kB
(9 rows)

This sums to ~2.1GB. It does not include chunk headers etc. so the
actuam memory usage is somewhat higher - accounting for that, it roughly
aligns with the memory context stats and total memory usage reported by
log_planner_stats.

It surprised me ~1/3 of the memory comes from find_mergeclauses, and
another ~1/3 from generating implied equalities. I'm not very familiar
with that code, but I guess it's generating entries over and over,
without freeing them even if unused. I wonder if we can free them? Or is
it unclear if an item is used? Maybe we could a least deduplicate them
in some way? Surely there's not 600MB worth of unique equalities?

regards

--
Tomas Vondra

Tomas Vondra <tomas@vondra.me> writes:

I was wondering about which places allocate most memory during planning.
I selected a query that allocates a manageable amount (~2.5GB) to plan,
and added some instrumentation to trace alloc/free calls for the
PortalContext (which is the context used by the planner).

Thanks for doing this work, very interesting.

After classifying the allocations a bit, I see this:

allocation | size
--------------------------------------+----------------
find_mergeclauses_for_outer_pathkeys | 671 MB
generate_join_implied_equalities | 660 MB
add_paths_to_joinrel | 242 MB
make_inner_pathkeys_for_merge | 195 MB
estimate_num_groups | 92 MB

...

I experimented with the attached trivial patch, which just avoids
leaking sublists within find_mergeclauses_for_outer_pathkeys and
generate_join_implied_equalities. I did not bother with adding
any measurement infrastructure, just watched the process's virtual
size with top(1). What I see is that HEAD consumes about 2.6GB
and this patch gets it down to 1.8GB. So we could move the needle
noticeably just by not wasting memory we don't have to.

regards, tom lane

On 05/06/2026 12:43, Tomas Vondra wrote:

On 2/10/26 17:29, Robert Haas wrote:

On Mon, Feb 9, 2026 at 3:17 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

What I'm wondering about is that join_collapse_limit and
from_collapse_limit were invented more than two decades ago, but
we've not touched their default values since then. Machines are a
lot faster since 2004, and we've probably achieved some net speedups
in the planner logic as well. Could we alleviate this concern by
raising those defaults, and if so, what are reasonable values in 2026?

The problem as I see it is that the planning time growth is
exponential, and so faster hardware doesn't necessarily buy you very
much, especially given that we've added new planner techniques that
add to the number of paths considered. But I also think that the
degenerate cases are much worse than the typical cases. For example, I
seem to remember things like A LEFT JOIN (B1 INNER JOIN B2 INNER JOIN
B3...) LEFT JOIN (C1 INNER JOIN C2 INNER JOIN C3...) [repeat with D,
E, etc.] being a problem, maybe for GEQO, because a
randomly-determined join order isn't likely to be valid. I think there
are similar issues with join_collapse_limit etc, for example because
we prefer joins that have joinclauses over those that don't, so the
actual planner work can be wildly different with the same number of
joins in the query. I suspect the thing that we need in order to be
able to safely raise these thresholds is for somebody to spend some
time figuring out what the pathologically bad cases are and designing
some sort of mitigations specifically for those. Or, alternatively, we
could decide that we've been too pessimistic and set slightly riskier
values by default, expecting that they'll work out most of the time
and that users can lower the setting if there's an issue.

Sorry to revive this thread from February, but I've been wondering about
the same thing (possibility to increase join_collapse_limit) in the
context of the starjoin planning thread.

I've decided to do a simple stress-test experiment - generate random
joins of 2-N tables, and measure how long the planning takes. See the
attached python script - it's not super elaborate, the joins are normal
joins (no lateral, no subqueries, ...).

Thanks.
This thread induced by the pain of the ORM world, where companies have a
stringent query response time. In such cases, query planning time is highly
important, and the number of joins varies widely (I'd say, unpredictably).

In my view, the purpose of a collapse limit in these cases is to keep planning
time reasonable and execution time steady. That’s why companies adjust these
GUCs carefully. Here’s a common example, typical for current widely used hardware:

from_collapse_limit = 20
join_collapse_limit = 20
geqo_threshold = 12

In this thread, I didn’t try to fix the issue by raising the collapse limit
because that doesn’t solve the problem. Instead, to make planning decisions more
stable, I suggest rearranging the jointree so the pulled-up jointree is closer
to the referenced outer subtree.

I’m not saying this approach should be added to the core, but it would be
helpful to have a way for extensions to influence rewriting decisions.

--
regards, Andrei Lepikhov,
pgEdge

On 6/7/26 20:57, Tom Lane wrote:

Tomas Vondra <tomas@vondra.me> writes:

I was wondering about which places allocate most memory during planning.
I selected a query that allocates a manageable amount (~2.5GB) to plan,
and added some instrumentation to trace alloc/free calls for the
PortalContext (which is the context used by the planner).

Thanks for doing this work, very interesting.

After classifying the allocations a bit, I see this:

allocation | size
--------------------------------------+----------------
find_mergeclauses_for_outer_pathkeys | 671 MB
generate_join_implied_equalities | 660 MB
add_paths_to_joinrel | 242 MB
make_inner_pathkeys_for_merge | 195 MB
estimate_num_groups | 92 MB

...

I experimented with the attached trivial patch, which just avoids
leaking sublists within find_mergeclauses_for_outer_pathkeys and
generate_join_implied_equalities. I did not bother with adding
any measurement infrastructure, just watched the process's virtual
size with top(1). What I see is that HEAD consumes about 2.6GB
and this patch gets it down to 1.8GB. So we could move the needle
noticeably just by not wasting memory we don't have to.

Thanks. I've tried the fix on the original query, and I confirm the
memory usage reported by log_planner_stats drops from ~2.7GB to ~1.8GB,
so quite a bit. I assume your numbers were from the same query, so this
aligns with your numbers from 'top'.

I also tried with a larger 13-table join, using ~17GB of memory. The fix
gets it to ~13GB, so it saves ~30% in both cases (the trace log has nice
1.2TB in this case ...).

I haven't measured how this affect plan time, but I can't imagine it'd
make it worse. If anything, it'll reduce the number of page faults -
which can be quite expensive.

So +1 to do this.

Of course, if we want to consider increasing join_collapse_limit, we'd
need to reduce memory usage further. Also, I wonder which other join
features (LATERAL, partition-wise joins, ...) might use significant
amounts of memory. The queries generated by the script are rather basic.
I suppose we might have to impose somewhat stricter rules about freeing
memory during planning, etc.

regards

--
Tomas Vondra

On 07/06/2026 20:10, Tomas Vondra wrote:

On 6/5/26 12:43, Tomas Vondra wrote:
After classifying the allocations a bit, I see this:

allocation | size
--------------------------------------+----------------
find_mergeclauses_for_outer_pathkeys | 671 MB
generate_join_implied_equalities | 660 MB
add_paths_to_joinrel | 242 MB
make_inner_pathkeys_for_merge | 195 MB
estimate_num_groups | 92 MB
get_joinrel_parampathinfo | 90 MB
create_memoize_path | 48 MB
| 15 MB
calc_nestloop_required_outer | 5226 kB
(9 rows)

It is fun to use the benchmark script from the previous research on this topic
[1]: /messages/by-id/603c8f070907062230v169541b0ka5a939de1132fd5c@mail.gmail.com
now shows the following numbers:

join_collapse_limit = 12: Memory: used=0.8GB, Time: 2.5s
join_collapse_limit = 14: Memory: used=1.1GB, Time: 5.5s
join_collapse_limit = 18: Memory: used=9.3GB, Time: 50.6s

It's interesting to compare these results with your memory consumption profile.
I tried using the memtrace patch and the Python script directly, but they gave
unusual output on my machine, so I couldn't rely on them without more detailed
instructions. Instead, I used the heaptrack tool, which gave me the following
profiles:

bytes pct function
collapse limit = 14:
354.48 MB 29.3% get_relation_foreign_keys
109.07 MB 9.0% generate_join_implied_equalities_normal
75.51 MB 6.2% get_eclass_indexes_for_relids
67.12 MB 5.5% find_mergeclauses_for_outer_pathkeys
67.12 MB 5.5% create_nestloop_path
58.73 MB 4.9% make_inner_pathkeys_for_merge
38.27 MB 3.2% expression_tree_mutator_impl
33.56 MB 2.8% hash_inner_and_outer
collapse limit = 18:
1.23 GB 12.8% generate_join_implied_equalities_normal
1.11 GB 11.5% get_joinrel_parampathinfo
989.90 MB 10.3% get_eclass_indexes_for_relids
755.04 MB 7.9% find_mergeclauses_for_outer_pathkeys
721.44 MB 7.5% calc_nestloop_required_outer
721.43 MB 7.5% get_param_path_clause_serials
629.15 MB 6.5% bms_intersect
578.81 MB 6.0% have_unsafe_outer_join_ref
411.08 MB 4.3% make_inner_pathkeys_for_merge
354.48 MB 3.7% get_relation_foreign_keys
335.58 MB 3.5% create_nestloop_path
301.99 MB 3.1% generate_join_implied_equalities

Overall, the results for generate_join_implied_equalities and
find_mergeclauses_for_outer_pathkeys are consistent. This test also highlights
other sources of memory allocations, such as parameterised paths. The memory
profile changes as the number of joins in the 'join problem' increases.

[1]: /messages/by-id/603c8f070907062230v169541b0ka5a939de1132fd5c@mail.gmail.com
/messages/by-id/603c8f070907062230v169541b0ka5a939de1132fd5c@mail.gmail.com
[2]: Test /messages/by-id/200907091700.43411.andres@anarazel.de
/messages/by-id/200907091700.43411.andres@anarazel.de

--
regards, Andrei Lepikhov,
pgEdge

On 6/8/26 15:32, Andrei Lepikhov wrote:

On 07/06/2026 20:10, Tomas Vondra wrote:

On 6/5/26 12:43, Tomas Vondra wrote:
After classifying the allocations a bit, I see this:

allocation | size
--------------------------------------+----------------
find_mergeclauses_for_outer_pathkeys | 671 MB
generate_join_implied_equalities | 660 MB
add_paths_to_joinrel | 242 MB
make_inner_pathkeys_for_merge | 195 MB
estimate_num_groups | 92 MB
get_joinrel_parampathinfo | 90 MB
create_memoize_path | 48 MB
| 15 MB
calc_nestloop_required_outer | 5226 kB
(9 rows)

It is fun to use the benchmark script from the previous research on this topic
[1], conducted in 2009. Query, consuming a lot of memory and planning time [2],
now shows the following numbers:

join_collapse_limit = 12: Memory: used=0.8GB, Time: 2.5s
join_collapse_limit = 14: Memory: used=1.1GB, Time: 5.5s
join_collapse_limit = 18: Memory: used=9.3GB, Time: 50.6s

It's interesting to compare these results with your memory consumption profile.
I tried using the memtrace patch and the Python script directly, but they gave
unusual output on my machine, so I couldn't rely on them without more detailed
instructions.

Yeah, the memtrace patch is very hacky, and I haven't given enough
instructions how to use it. The .patch adds elog(LOG) with the MEMTRACE
information (context, action, chunk, size), and the memtrace.py
aggregates it like this:

grep MEMTRACE pg.log | ./memtrace.py > memtrace.log

But the heaptrack seems more convenient, of course.

Instead, I used the heaptrack tool, which gave me the following

profiles:

bytes pct function
collapse limit = 14:
354.48 MB 29.3% get_relation_foreign_keys
109.07 MB 9.0% generate_join_implied_equalities_normal
75.51 MB 6.2% get_eclass_indexes_for_relids
67.12 MB 5.5% find_mergeclauses_for_outer_pathkeys
67.12 MB 5.5% create_nestloop_path
58.73 MB 4.9% make_inner_pathkeys_for_merge
38.27 MB 3.2% expression_tree_mutator_impl
33.56 MB 2.8% hash_inner_and_outer
collapse limit = 18:
1.23 GB 12.8% generate_join_implied_equalities_normal
1.11 GB 11.5% get_joinrel_parampathinfo
989.90 MB 10.3% get_eclass_indexes_for_relids
755.04 MB 7.9% find_mergeclauses_for_outer_pathkeys
721.44 MB 7.5% calc_nestloop_required_outer
721.43 MB 7.5% get_param_path_clause_serials
629.15 MB 6.5% bms_intersect
578.81 MB 6.0% have_unsafe_outer_join_ref
411.08 MB 4.3% make_inner_pathkeys_for_merge
354.48 MB 3.7% get_relation_foreign_keys
335.58 MB 3.5% create_nestloop_path
301.99 MB 3.1% generate_join_implied_equalities

Hmm, how does heaptrack deal with out memory pools? I was worried
existing memory profilers (like heaptrack) would get confused by our
memory contexts, attributing the whole block to the palloc that just
happens to allocate a new block. But that's not really right.

I see the heaptrack README claims it can work with memory pools after
annotating the code in some way. But there's not much details about
that. Also, it suggests valgrind/massif can already do that.

Overall, the results for generate_join_implied_equalities and
find_mergeclauses_for_outer_pathkeys are consistent. This test also highlights
other sources of memory allocations, such as parameterised paths. The memory
profile changes as the number of joins in the 'join problem' increases.

Yes. I did actually mention get_joinrel_parampathinfo.

regards

--
Tomas Vondra

On 08/06/2026 17:27, Tomas Vondra wrote:

On 6/8/26 15:32, Andrei Lepikhov wrote:

Instead, I used the heaptrack tool, which gave me the following

Hmm, how does heaptrack deal with out memory pools? I was worried
existing memory profilers (like heaptrack) would get confused by our
memory contexts, attributing the whole block to the palloc that just
happens to allocate a new block. But that's not really right.

In theory, heaptrack does not catch pallocs inside a memory context and only
tracks malloc and free calls. However, in my experience, it still helps identify
the issue. This might be because the planner uses local memory contexts, and
with [1]/messages/by-id/1f797d0e-4829-48b5-817e-2278466ed4ef@gmail.com added, it could be even more localised. Usually, the problem is a cycle
that grows too long, with many allocations within it that go unreleased, causing
overconsumption and memory context growth. In this case, heaptrack may not point
to the exact spot, but it still provides useful hints.

Compared to other profilers (gperftools, jemalloc, valgrind massif), I like it
more for its flexibility, flamegraphs, and an interface that the support team
frequently uses (even on Windows somehow) - it is beneficial for the
inter-department communication. Profilers don’t understand malloc/palloc
postgres separation anyway, and to use them we need to annotate postgres calls.

I see the heaptrack README claims it can work with memory pools after
annotating the code in some way. But there's not much details about
that. Also, it suggests valgrind/massif can already do that.

Looking into the interface [2,3], it looks quite clear to me - it even includes
a Valgrind macros set that makes it more natively integrated. Thinking about
implementation, my first wish was to create an extension and see how it actually
works in practice, but we can’t inject a wrapper into the static
MemoryContextMethods, which limits the ability of such an extension. Maybe with
an umbrella planning memory context …

Core-based annotation looks more interesting. There are questions about proper
palloc/malloc counting that exist - I think it can be generally solved by
employing heaptrack_pause / heaptrack_resume calls, if this topic sparks an
interest. Or we can discuss some API flexibility on the HeapTrack side.

[1]: /messages/by-id/1f797d0e-4829-48b5-817e-2278466ed4ef@gmail.com
/messages/by-id/1f797d0e-4829-48b5-817e-2278466ed4ef@gmail.com
[2]: https://github.com/KDE/heaptrack/blob/master/src/track/libheaptrack.h
[3]: https://github.com/KDE/heaptrack/blob/master/src/track/heaptrack_api.h

--
regards, Andrei Lepikhov,
pgEdge

On 6/9/26 09:08, Andrei Lepikhov wrote:

On 08/06/2026 17:27, Tomas Vondra wrote:

On 6/8/26 15:32, Andrei Lepikhov wrote:

Instead, I used the heaptrack tool, which gave me the following

Hmm, how does heaptrack deal with out memory pools? I was worried
existing memory profilers (like heaptrack) would get confused by our
memory contexts, attributing the whole block to the palloc that just
happens to allocate a new block. But that's not really right.

In theory, heaptrack does not catch pallocs inside a memory context and only
tracks malloc and free calls. However, in my experience, it still helps identify
the issue. This might be because the planner uses local memory contexts, and
with [1] added, it could be even more localised. Usually, the problem is a cycle
that grows too long, with many allocations within it that go unreleased, causing
overconsumption and memory context growth. In this case, heaptrack may not point
to the exact spot, but it still provides useful hints.

I don't know what you mean by "planner uses local memory contexts". All
the memory allocations I discussed are in PortalContext. Maybe there are
some short-lived memory contexts, but those are by definition not an
issue, because the memory is released. It's about the long-lived
allocations that are left in PortalContext that ...

Maybe heaptrack can still do a sufficient job, because given enough
allocations the distribution of palloc and malloc will be about the
same. But if there's a problem to make it work well with pools ...

Compared to other profilers (gperftools, jemalloc, valgrind massif), I like it
more for its flexibility, flamegraphs, and an interface that the support team
frequently uses (even on Windows somehow) - it is beneficial for the
inter-department communication. Profilers don’t understand malloc/palloc
postgres separation anyway, and to use them we need to annotate postgres calls.

OK

The one advantage of massif might be that we already have dependency and
instrumentation for valgrind (I'm assuming it might extend that, not
having to introduce a completely new dependency).

I see the heaptrack README claims it can work with memory pools after
annotating the code in some way. But there's not much details about
that. Also, it suggests valgrind/massif can already do that.

Looking into the interface [2,3], it looks quite clear to me - it even includes
a Valgrind macros set that makes it more natively integrated. Thinking about
implementation, my first wish was to create an extension and see how it actually
works in practice, but we can’t inject a wrapper into the static
MemoryContextMethods, which limits the ability of such an extension. Maybe with
an umbrella planning memory context …

Core-based annotation looks more interesting. There are questions about proper
palloc/malloc counting that exist - I think it can be generally solved by
employing heaptrack_pause / heaptrack_resume calls, if this topic sparks an
interest. Or we can discuss some API flexibility on the HeapTrack side.

I don't see a point of doing this from an extension. It's a developer
feature, similar to valgrind instrumentation.

regards

--
Tomas Vondra

Hi,

I kept poking at the patch releasing some transient sublists, trying to
make it release even more memory. Attached is a couple hacky patches
releasing memory in a couple more places:

0001 - Tom's patch releasing a couple transient lists

0002 - releases a couple more transient lists in nearby functions

0003 - release yet more transient lists in equivclass.c

0004 - release transient lists in estimate_num_groups

0005 - free lists used by mergejoin paths

0006 - free lists used by hahsjoin paths

I think 0002-0004 are a relatively straightforward extensions of the
0001 patch, releasing lists that are not used outside a function.

0005+0006 are a bit more invasive, but also save much more memory.

The places constructing mergejoin/hashjoin paths build lists for
inner/outer keys, merge/hash clauses etc. But then those are leaked,
because (a) it's not clear if a join using those lists was actually
created (or if add_path threw it away), and (b) add_path may keep it and
discard it sometime later. But that releases just the path, not the lists.

So 0005+0006 change the contract a bit:

(a) create_hashjoin_path/create_mergejoin_path always copy these list

(b) add_path frees these list when discarding a mergejoin/hashjoin path

(c) the places creating join paths free the lists too

This is a bit ugly, because sometimes the lists may be the same etc. But
it does work well enough for a hacky PoC (passes make check).

With these patches, the memory usage (per log_planner_stats) drops to
~500MB. That's a nice improvement, from the original 2.6GB. The larger
query that used ~17GB now needs ~3GB of memory.

I was wondering how this impacts planning time, so I ran the original
test with 2-11 tables, with 1000 joins for each join size. Attached are
two charts showing the average plan time and memory usage. The patched
build seems consistently faster - for smaller joins (up to ~8 tables)
the differences are small, not really visible in these charts. As the
joins grow it's getting much more visible, and the differences increase.

I redid the memory tracing for the "smaller" query (which now needs
~500MB), and it looks like this

allocation_group | pg_size_pretty
--------------------------------------+----------------
create_memoize_path | 92 MB
get_joinrel_parampathinfo | 65 MB
estimate_num_groups | 47 MB
add_paths_to_joinrel | 38 MB
generate_join_implied_equalities | 24 MB
| 15 MB
create_material_path | 15 MB
calc_nestloop_required_outer | 5224 kB
find_mergeclauses_for_outer_pathkeys | 0 bytes
make_inner_pathkeys_for_merge | 0 bytes
(10 rows)

It shouldn't be hard to get rid of estimate_num_groups entirely, by
freeing the GroupVarInfo entries (and not just the lists).

But after that, it's going to be harder. I'm not sure what to do about
the memoize/material paths - we're leaking these paths because various
places in joinpath.c try to "inject" these paths below a join. But this
way the logic in add_path may not free the path - we may not even get to
add_path, and even if we do, it operates on the join, not this new made
up memoize/material path. The callers have no idea if the path happens
to be used or not, so can't free it either.

I'm not sure what to do about this. I suppose it'd be good to have a
better idea if the path got used, in some way.

regards

--
Tomas Vondra

On 09/06/2026 12:43, Tomas Vondra wrote:

I'm not sure what to do about this. I suppose it'd be good to have a
better idea if the path got used, in some way.

Looking ahead, I believe Tom's idea of using a selectivity-estimation memory
context can help lower memory spikes when working with massive clauses.

A combination of Ashutosh's 'smart references' [2]/messages/by-id/CAExHW5tUcVsBkq9qT=L5vYz4e-cwQNw=KAGJrtSyzOp3F=XacA@mail.gmail.com and a per-RelOptInfo memory
context might reduce memory usage even further. Right now, partitionwise-enabled
planning with parameterised join paths can lead to high peak memory usage due to
reparameterisation copy.

[1]: /messages/by-id/1367418.1708816059@sss.pgh.pa.us
[2]: /messages/by-id/CAExHW5tUcVsBkq9qT=L5vYz4e-cwQNw=KAGJrtSyzOp3F=XacA@mail.gmail.com
/messages/by-id/CAExHW5tUcVsBkq9qT=L5vYz4e-cwQNw=KAGJrtSyzOp3F=XacA@mail.gmail.com

--
regards, Andrei Lepikhov,
pgEdge

On 09/06/2026 12:43, Tomas Vondra wrote:

I kept poking at the patch releasing some transient sublists, trying to
make it release even more memory. Attached is a couple hacky patches
releasing memory in a couple more places:

0001 - Tom's patch releasing a couple transient lists

I used to think that list_concat() simply added a reference from sublist1 to
sublist2, forgetting that it's actually an array underneath. I’m curious how
many parts of the code are written with the same assumption.

Let's check some of them:

1. result = list_concat(result, generate_join_implied_equalities(root, ...
2. pclauses = list_concat(pclauses, eqclauses);
3. qpquals = list_concat(extract_nonindex_conditions(path->indexinfo- ...

in relnode.c, costsize.c looks like a good candidates too

out_list = list_concat(out_list, ...

in pull_ors / pull_ands also might be freed earlier.

0002 - releases a couple more transient lists in nearby functions

Also, quite a typical template. Maybe an automatic AI search might crawl the
code and detect similar places? Maybe it makes sense to analyse and free also
bitmapsets outer_and_req, inner_and_req, and real_outer_and_req? In case of
partitioned tables, they might be quite massive.

0003 - release yet more transient lists in equivclass.c

Yes, EC memebers might be quite long lists

0004 - release transient lists in estimate_num_groups

I'm not sure this is necessary. The grouping list is usually short, and cleaning
varinfos seems like over-managing.

0005 - free lists used by mergejoin paths

Here, as well, I don't see the reason - pathkeys lists are quite short and
truncate_useless_pathkeys reduces their nomenclature quite effectively

0006 - free lists used by hahsjoin paths

The same as above

With these patches, the results of the benchmark [1]/messages/by-id/200907091700.43411.andres@anarazel.de change consumption and
planning time a little (don't forget 'geqo = off'):

collapse limit | Memory consumed | Planning time
8 | 0.4 GB -> 0.4 GB | 0.7s -> 0.7s
12 | 0.8 GB -> 0.6 GB | 2.5s -> 2.3s
14 | 1.1 GB -> 0.8 GB | 5.5s -> 5.5s
18 | 9.3 GB -> 6.1 GB | 52s -> 48s

[1]: /messages/by-id/200907091700.43411.andres@anarazel.de

--
regards, Andrei Lepikhov,
pgEdge

On 6/13/26 12:07, Andrei Lepikhov wrote:

On 09/06/2026 12:43, Tomas Vondra wrote:

I kept poking at the patch releasing some transient sublists, trying to
make it release even more memory. Attached is a couple hacky patches
releasing memory in a couple more places:

0001 - Tom's patch releasing a couple transient lists

I used to think that list_concat() simply added a reference from sublist1 to
sublist2, forgetting that it's actually an array underneath. I’m curious how
many parts of the code are written with the same assumption.

Let's check some of them:

1. result = list_concat(result, generate_join_implied_equalities(root, ...
2. pclauses = list_concat(pclauses, eqclauses);
3. qpquals = list_concat(extract_nonindex_conditions(path->indexinfo- ...

in relnode.c, costsize.c looks like a good candidates too

out_list = list_concat(out_list, ...

in pull_ors / pull_ands also might be freed earlier.

Perhaps. But I don't think we need to worry about places invoked only
once (or very limited number of times) per query/plan. Which I think is
the case of pull_ors, pull_ands, qpquals, etc. Those do not matter.

It's the calls that happen for every path we consider/create, because if
there are many paths (and for large joins there can be very many) that
ends up using a lot of memory.

0002 - releases a couple more transient lists in nearby functions

Also, quite a typical template. Maybe an automatic AI search might crawl the
code and detect similar places? Maybe it makes sense to analyse and free also
bitmapsets outer_and_req, inner_and_req, and real_outer_and_req? In case of
partitioned tables, they might be quite massive.

Could be. It's certainly possible other queries or queries on
partitioned tables will consume a lot of memory in other places.

0003 - release yet more transient lists in equivclass.c

Yes, EC memebers might be quite long lists

0004 - release transient lists in estimate_num_groups

I'm not sure this is necessary. The grouping list is usually short, and cleaning
varinfos seems like over-managing.

It's not just the question of how long the lists are. It's how often we
build them. In the example query we ended up with ~100MB used by these
things, and ~1/2 of that was the varinfo items.

0005 - free lists used by mergejoin paths

Here, as well, I don't see the reason - pathkeys lists are quite short and
truncate_useless_pathkeys reduces their nomenclature quite effectively

0006 - free lists used by hahsjoin paths

The same as above

I don't follow. I posted this table a couple messages back:

allocation | size
--------------------------------------+----------------
find_mergeclauses_for_outer_pathkeys | 671 MB
generate_join_implied_equalities | 660 MB
...

Which shows the lists in merge joins consuming ~671MB of memory. That's
not exactly negligible, it's ~30% of the memory usage at that point.
Maybe it wasn't just because of pathkey lists, I don't recall if I
folded some more stuff into it. But it's certainly part of it.

Again, it does not matter if the individual lists are short if we build
an exponential number of them.

With these patches, the results of the benchmark [1] change consumption and
planning time a little (don't forget 'geqo = off'):

collapse limit | Memory consumed | Planning time
8 | 0.4 GB -> 0.4 GB | 0.7s -> 0.7s
12 | 0.8 GB -> 0.6 GB | 2.5s -> 2.3s
14 | 1.1 GB -> 0.8 GB | 5.5s -> 5.5s
18 | 9.3 GB -> 6.1 GB | 52s -> 48s

[1] /messages/by-id/200907091700.43411.andres@anarazel.de

It's not surprising a different query uses different amounts of memory,
allocated in different places.

regards

--
Tomas Vondra

On 6/8/26 17:27, Tomas Vondra wrote:

...

Hmm, how does heaptrack deal with out memory pools? I was worried
existing memory profilers (like heaptrack) would get confused by our
memory contexts, attributing the whole block to the palloc that just
happens to allocate a new block. But that's not really right.

I see the heaptrack README claims it can work with memory pools after
annotating the code in some way. But there's not much details about
that. Also, it suggests valgrind/massif can already do that.

I took a look at massif - mostly because it comes with valgrind, which
we already use and have the infrastructure in place for (while heaptrack
would be a new dependency, would require new instrumentation etc.).

I think it works pretty well. I'm still not quite sure it does the right
thing with memory contexts (i.e. tracking chunks and not malloc blocks).
We do have the macros (VALGRIND_MEMPOOL_ALLOC, ...) in the right places,
but I saw some malloc() calls in the traces too, which seems wrong.

Anyway, it seems very convenient to use, and gives me data roughly in
line with the manual tracing. It produces much nicer / more complete
reports, and it's way faster (a minute vs. an hour).

Here's how I use it (after building with -DUSE_VALGRIND)

valgrind --trace-children=yes --tool=massif \
--alloc-fn=MemoryContextAlloc \
--alloc-fn=MemoryContextAllocExtended \
--alloc-fn=AllocSetAlloc \
--alloc-fn=AllocSetAllocFromNewBlock \
--alloc-fn=palloc --alloc-fn=palloc0 \
--max-snapshots=1000 --detailed-freq=1 --threshold=0.0 \
postgres ...

Which may be an overkill (e.g. too many detailed snapshots, threshold
too low, ...). But it works. It produces one file per process, I think
you need to exit the process for the file to be written / complete.

Then, to process the massif.out.PID file into a text report:

TMPDIR=./tmp ms_print massif.out.PID > massif.txt

Attached is an example of one of the reports.

It's also possible to use a massif-visualizer, which shows a nice graph
and allows drilling down to the various places allocating memory.

regards

--
Tomas Vondra