Обсуждение: Useless LEFT JOIN breaks MIN/MAX optimization

Hi hackers!

My colleague gave me an interesting case related to min max 
optimization. Adding a useless left join to the select min from t query 
breaks the min/max read optimization from the index.
What is meant is shown in the example below:

drop table if exists t1;
drop table if exists t2;

create table t1 (id int not null, mod text);
insert into t1 select id, (id % 10)::text from generate_series(1,100000) id;
create unique index on t1(id);
create index on t1(mod);

This is the best plan for this query, since we only need one minimum 
value for this index. And it works perfectly:
explain select min(mod) from t1;
explain select min(mod) from t1;
QUERY PLAN
------------------------------------------------------------------------------------------------
  Result (cost=0.33..0.34 rows=1 width=32)
  InitPlan 1 (returns $0)
  -> Limit (cost=0.29..0.33 rows=1 width=32)
  -> Index Only Scan using t1_mod_idx on t1 (cost=0.29..3861.54 
rows=99500 width=32)
  Index Cond: (mod IS NOT NULL)
(5 rows)

create table t2 (id int not null);
insert into t2 select id from generate_series(1,100000) id;
create unique index on t2(id);

But if we add a join, we fall into a sec scan without options:
explain select min(t1.mod) from t1 left join t2 on t1.id = t2.id;
postgres=# explain select min(t1.mod) from t1 left join t2 on t1.id = t2.id;
QUERY PLAN
-----------------------------------------------------------------
Aggregate (cost=1693.00..1693.01 rows=1 width=32)
-> Seq Scan on t1 (cost=0.00..1443.00 rows=100000 width=32)

I have implemented a patch that solves this problem - allowing to 
consider and join expressions for trial optimization. I am glad for 
feedback and review!

-- 
Regards,
Alena Rybakina
Postgres Professional

Hi Alena,

If I understand correctly, the problem here is that join removal and
minmax aggregates don't work well together: after join removal runs,
we end up with a state that doesn't permit the minmax-aggregate code
to work.

I agree that would be good to fix but the patch doesn't seem right to me.

I'm looking at this line from the patch, in particular:

+ if (IsA(jtnode, JoinExpr) && jtnode->fromlist == NIL &&
IsA(jtnode->quals, RangeTblRef))

jtnode is declared to be of type FromExpr. But here you check that it
is a JoinExpr, and if it is, then you dereference it as if it were a
FromExpr. So, if I'm understanding correctly, the reference to
jtnode->fromlist is actually looking at some completely unrelated
field that is part of a JoinExpr, like maybe larg, and jtnode->quals
is looking at some other field, maybe jtnode->rarg. That's pretty
crazy coding -- the right thing to do would be to cast the jtnode to
the proper type and then access it using the proper field names.

Backing up a step, it seems to me that it might be a good idea to
rewrite the preceding loop, which can descend through any number of
levels of FromExpr expressions, to be able to descend through either
FromExpr or JoinExpr expressions, stopping when it can't descend
further using either method. The way you've coded it supposes that it
only ever needs to descend through one JoinExpr expression and that
the JoinExpr will always be beneath all the FromExprs, which might not
be a correct assumption. It would probably be a good idea to write
some more complex test cases where multiple joins get removed at
various levels, and where there are also subquery levels that produce
FromExprs, in various configurations, and test that the patch works in
all of those cases.

But that's also assuming that you're correct here about how to descend
through a JoinExpr, which I'm not quite sure whether is true. It's
also assuming that we should solve the problem here rather than in
some other part of the code e.g. the join removal code, and I'm not
sure about that either.

I'm just studying this for the first time so apologies if this review
is not quite up to standard.

Thanks,

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

Hi, Robert!

On 09.05.2025 20:12, Robert Haas wrote:
> If I understand correctly, the problem here is that join removal and
> minmax aggregates don't work well together: after join removal runs,
> we end up with a state that doesn't permit the minmax-aggregate code
> to work.
Yes, it is correct.
> I agree that would be good to fix but the patch doesn't seem right to me.
>
> I'm looking at this line from the patch, in particular:
>
> + if (IsA(jtnode, JoinExpr) && jtnode->fromlist == NIL &&
> IsA(jtnode->quals, RangeTblRef))
>
> jtnode is declared to be of type FromExpr. But here you check that it
> is a JoinExpr, and if it is, then you dereference it as if it were a
> FromExpr. So, if I'm understanding correctly, the reference to
> jtnode->fromlist is actually looking at some completely unrelated
> field that is part of a JoinExpr, like maybe larg, and jtnode->quals
> is looking at some other field, maybe jtnode->rarg. That's pretty
> crazy coding -- the right thing to do would be to cast the jtnode to
> the proper type and then access it using the proper field names.
Yes, you are right, my mistake. I'll correct it. Thank you)
> Backing up a step, it seems to me that it might be a good idea to
> rewrite the preceding loop, which can descend through any number of
> levels of FromExpr expressions, to be able to descend through either
> FromExpr or JoinExpr expressions, stopping when it can't descend
> further using either method. The way you've coded it supposes that it
> only ever needs to descend through one JoinExpr expression and that
> the JoinExpr will always be beneath all the FromExprs, which might not
> be a correct assumption. It would probably be a good idea to write
> some more complex test cases where multiple joins get removed at
> various levels, and where there are also subquery levels that produce
> FromExprs, in various configurations, and test that the patch works in
> all of those cases.

You are right, there are not enough tests here and we need to add 
queries with more complex semantics and you are right about the approach.

I'll implement it. Thanks for pointing this out, I missed it.

> But that's also assuming that you're correct here about how to descend
> through a JoinExpr, which I'm not quite sure whether is true. It's
> also assuming that we should solve the problem here rather than in
> some other part of the code e.g. the join removal code, and I'm not
> sure about that either.

I don’t think it’s necessary to move this code into the join removal 
optimization phase. There’s no guarantee that there will not appear 
future optimizations that will make impossible to apply min/max 
optimization afterward. Keeping the min/max optimization in a single, 
consistent location also improves clarity and maintainability of the code.

The simplest solution, in my opinion, is to extend the current logic to 
include type checking for the JoinExpr types as I did in my patch. 
Specifically, we can verify that it now involves only a single relation 
or partitioned relations without formation join algorithms.

> I'm just studying this for the first time so apologies if this review
> is not quite up to standard.
No need to apologize - you raised important points during both the patch 
and issue reviews. Thanks for your valuable and helpful feedback!

-- 
Regards,
Alena Rybakina
Postgres Professional

Robert Haas <robertmhaas@gmail.com> writes:
> But that's also assuming that you're correct here about how to descend
> through a JoinExpr, which I'm not quite sure whether is true. It's
> also assuming that we should solve the problem here rather than in
> some other part of the code e.g. the join removal code, and I'm not
> sure about that either.

The actual problem here is that remove_useless_joins hasn't run yet.
It's called inside query_planner which happens only after we do
preprocess_minmax_aggregates.

So I think this patch is a dead end.  It's not possible for it to
correctly predict whether remove_useless_joins will remove the join,
short of repeating all that work which we surely don't want.
(I'm a bit surprised that it hasn't visibly broken existing test cases.)

It might be possible to move preprocess_minmax_aggregates to happen
after join removal, but I fear it'd require some pretty fundamental
rethinking of how it generates indexscan paths --- recursively
calling query_planner seems dubious.  (But maybe that'd work?
The modified query should no longer contain aggs, so we wouldn't
recurse again.)

preprocess_minmax_aggregates is pretty much of a hack anyway.
If you read the comments, it's just full of weird stuff that it
has to duplicate from other places, or things that magically work
because the relevant stuff isn't possible in this query, etc.
Maybe it's time to think about nuking it from orbit and doing a
fresh implementation in some other place that's a better fit.
I have no immediate ideas about what that should look like, other
than it'd be better if it happened after join removal.

            regards, tom lane

Robert Haas <robertmhaas@gmail.com> writes:

But that's also assuming that you're correct here about how to descend
through a JoinExpr, which I'm not quite sure whether is true. It's
also assuming that we should solve the problem here rather than in
some other part of the code e.g. the join removal code, and I'm not
sure about that either.

The actual problem here is that remove_useless_joins hasn't run yet.
It's called inside query_planner which happens only after we do
preprocess_minmax_aggregates.

So I think this patch is a dead end.  It's not possible for it to
correctly predict whether remove_useless_joins will remove the join,
short of repeating all that work which we surely don't want.
(I'm a bit surprised that it hasn't visibly broken existing test cases.)

To be honest, I was not completely sure about my decision at first and had no idea how to do it differently, so I submitted a request for "Advanced session feedback" to consider this patch.

It might be possible to move preprocess_minmax_aggregates to happen
after join removal, but I fear it'd require some pretty fundamental
rethinking of how it generates indexscan paths --- recursively
calling query_planner seems dubious.  (But maybe that'd work?
The modified query should no longer contain aggs, so we wouldn't
recurse again.)

It was a long time ago to be frankly, but the problem there was that the planner stored this information at a higher level. I can try to finish this.

I attached a diff just in case.

preprocess_minmax_aggregates is pretty much of a hack anyway.
If you read the comments, it's just full of weird stuff that it
has to duplicate from other places, or things that magically work
because the relevant stuff isn't possible in this query, etc.
Maybe it's time to think about nuking it from orbit and doing a
fresh implementation in some other place that's a better fit.
I have no immediate ideas about what that should look like, other
than it'd be better if it happened after join removal.

I didn't consider this and I'll think about it. 

Thanks for the feedback!

Regards,
Alena Rybakina
Postgres Professional