Re: A problem about join ordering

On Fri, Nov 11, 2022 at 11:24 PM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Richard Guo <guofenglinux(at)gmail(dot)com> writes:
> > I'm wondering whether we need to insist on being strict for the lower
> > OJ's min_righthand. What if we instead check strictness for its whole
> > syn_righthand?
>
> Surely not. What if the only point of strictness is for a rel that
> isn't part of the min_righthand? Then we could end up re-ordering
> based on a condition that isn't actually strict for what we've
> chosen as the join's RHS.
>
> It might be possible to change the other part of the equation and
> consider the A/B join's min_righthand instead of syn_righthand
> while checking if Pcd uses A/B's RHS; but I'm not real sure about
> that either.

The problem described upthread occurs in the case where the lower OJ is
in our LHS. For the other case where the lower OJ is in our RHS, it
seems we also have join ordering problem. As an example, consider

A leftjoin (B leftjoin (C leftjoin D on (Pcd)) on (Pbc)) on (Pac)

A leftjoin ((B leftjoin C on (Pbc)) leftjoin D on (Pcd)) on (Pac)

The two forms are equal if we assume Pcd is strict for C, according to
outer join identity 3.

In the two forms we both decide that we cannot interchange the ordering
of A/C join and B/C join, because Pac uses B/C join's RHS. So we add
B/C join's full syntactic relset to A/C join's min_righthand to preserve
the ordering. However, in the first form B/C's full syntactic relset
includes {B, C, D}, while in the second form it only includes {B, C}.
As a result, the A/(BC) join is illegal in the first form and legal in
the second form, and this will determine whether we can get the third
form as below

(A leftjoin (B leftjoin C on (Pbc)) on (Pac)) leftjoin D on (Pcd)

This makes me rethink whether we should use lower OJ's full syntactic
relset or just its min_lefthand + min_righthand to be added to
min_righthand to preserve ordering for this case. But I'm not sure
about this.

Any thoughts?

Thanks
Richard