Making Vars outer-join aware

Tom, two quick questions before attempting to read the patch:

Given that views are represented in a parsed representation, does anything need to happen to the Vars inside a view when that view is outer-joined to?

If an outer join is converted to an inner join, must this information get propagated to all the affected Vars, potentially across query block levels?

"Finnerty, Jim" <jfinnert@amazon.com> writes:

Given that views are represented in a parsed representation, does anything need to happen to the Vars inside a view when that view is outer-joined to?

No. The markings only refer to what is in the same Query tree as the Var
itself.

Subquery flattening during planning does deal with this: if we pull up a
subquery (possibly inserted from a view) that was underneath an outer
join, the nullingrel marks on the upper-level Vars referring to subquery
outputs will get merged into what is pulled up, either by unioning the
varnullingrel bitmaps if what is pulled up is just a Var, or if what is
pulled up isn't a Var, by wrapping it in a PlaceHolderVar that carries
the old outer Var's markings. We had essentially this same behavior
with PlaceHolderVars before, but I think this way makes it a lot more
principled and intelligible (and I suspect there are now cases where we
manage to avoid inserting unnecessary PlaceHolderVars that the old code
couldn't avoid).

If an outer join is converted to an inner join, must this information get propagated to all the affected Vars, potentially across query block levels?

Yes. The code is there in the patch to run around and remove nullingrel
bits from affected Vars.

One thing that doesn't happen (and didn't before, so this is not a
regression) is that if we strength-reduce a FULL JOIN USING to an outer
or plain join, it'd be nice if the "COALESCE" hack we represent the
merged USING column with could be replaced with the same lower-relation
Var that the parser would have used if the join weren't FULL to begin
with. Without that, we're leaving optimization opportunities on the
table. I'm hesitant to try to do that though as long as the COALESCE
structures look exactly like something a user could write. It'd be
safer if we used some bespoke node structure for this purpose ...
but nobody's bothered to invent that.

regards, tom lane

On Sat, Jul 2, 2022 at 12:42 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:

Anyway, even though this is far from done, I'm pretty pleased with
the results so far, so I thought I'd put it out for review by
anyone who cares to take a look. I'll add it to the September CF
in hopes that it might be more or less finished by then, and so
that the cfbot will check it out.

Thanks for the work! I have a question about qual clause placement.

For the query in the example

SELECT * FROM t1 LEFT JOIN t2 ON (t1.x = t2.y) WHERE foo(t2.z)

(foo() is not strict.) We want to avoid pushing foo(t2.z) down to the t2
scan level. Previously we do that with check_outerjoin_delay() by
scanning all the outer joins below and check if the qual references any
nullable rels of the OJ, and if so include the OJ's rels into the qual.
So as a result we'd get that foo(t2.z) is referencing t1 and t2, and
we'd put the qual into the join lists of t1 and t2.

Now there is the 'varnullingrels' marker in the t2.z, which is the LEFT
JOIN below (with RTI 3). So we consider the qual is referencing RTE 2
(which is t2) and RTE 3 (which is the OJ). Do we still need to include
RTE 1, i.e. t1 into the qual's required relids? How should we do that?

Thanks
Richard

Richard Guo <guofenglinux@gmail.com> writes:

For the query in the example

SELECT * FROM t1 LEFT JOIN t2 ON (t1.x = t2.y) WHERE foo(t2.z)

(foo() is not strict.) We want to avoid pushing foo(t2.z) down to the t2
scan level. Previously we do that with check_outerjoin_delay() by
scanning all the outer joins below and check if the qual references any
nullable rels of the OJ, and if so include the OJ's rels into the qual.
So as a result we'd get that foo(t2.z) is referencing t1 and t2, and
we'd put the qual into the join lists of t1 and t2.

Now there is the 'varnullingrels' marker in the t2.z, which is the LEFT
JOIN below (with RTI 3). So we consider the qual is referencing RTE 2
(which is t2) and RTE 3 (which is the OJ). Do we still need to include
RTE 1, i.e. t1 into the qual's required relids? How should we do that?

It seems likely to me that we could leave the qual's required_relids
as just {2,3} and not have to bother ORing any additional bits into
that. However, in the case of a Var-free JOIN/ON clause it'd still
be necessary to artificially add some relids to its initially empty
relids. Since I've not yet tried to rewrite distribute_qual_to_rels
I'm not sure how the details will shake out.

regards, tom lane

Here's v2 of this patch series. It's functionally identical to v1,
but I've rebased it over the recent auto-node-support-generation
changes, and also extracted a few separable bits in hopes of making
the main planner patch smaller. (It's still pretty durn large,
unfortunately.) Unlike the original submission, each step will
compile on its own, though the intermediate states mostly don't
pass all regression tests.

regards, tom lane

On Sun, Jul 10, 2022 at 12:39 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

Here's v2 of this patch series. It's functionally identical to v1,
but I've rebased it over the recent auto-node-support-generation
changes, and also extracted a few separable bits in hopes of making
the main planner patch smaller. (It's still pretty durn large,
unfortunately.) Unlike the original submission, each step will
compile on its own, though the intermediate states mostly don't
pass all regression tests.

regards, tom lane

Hi,

For v2-0004-cope-with-nullability-in-planner.patch.
In remove_unneeded_nulling_relids():

+ if (removable_relids == NULL)

Why is bms_is_empty() not used in the above check ?
Earlier there is `if (bms_is_empty(old_nulling_relids))`

+typedef struct reduce_outer_joins_partial_state

Since there are already reduce_outer_joins_pass1_state
and reduce_outer_joins_pass2_state, a comment
above reduce_outer_joins_partial_state would help other people follow its
purpose.

+       if (j->rtindex)
+       {
+           if (j->jointype == JOIN_INNER)
+           {
+               if (include_inner_joins)
+                   result = bms_add_member(result, j->rtindex);
+           }
+           else
+           {
+               if (include_outer_joins)

Since there are other join types beside JOIN_INNER, should there be an
assertion in the else block ? e.g. jointype wouldn't be JOIN_UNIQUE_INNER.

Cheers

Zhihong Yu <zyu@yugabyte.com> writes:

In remove_unneeded_nulling_relids():

+ if (removable_relids == NULL)

Why is bms_is_empty() not used in the above check ?

We initialized that to NULL just a few lines above, and then did
nothing to it other than perhaps bms_add_member, so it's impossible
for it to be empty-and-yet-not-NULL.

+typedef struct reduce_outer_joins_partial_state

Since there are already reduce_outer_joins_pass1_state
and reduce_outer_joins_pass2_state, a comment
above reduce_outer_joins_partial_state would help other people follow its
purpose.

We generally document these sorts of structs in the using code,
not at the struct declaration.

+       if (j->rtindex)
+       {
+           if (j->jointype == JOIN_INNER)
+           {
+               if (include_inner_joins)
+                   result = bms_add_member(result, j->rtindex);
+           }
+           else
+           {
+               if (include_outer_joins)

Since there are other join types beside JOIN_INNER, should there be an
assertion in the else block?

Like what? We don't particularly care what the join type is here,
as long as it's not INNER. In any case there is plenty of nearby
code checking for unsupported join types.

regards, tom lane

On Mon, Jul 11, 2022 at 3:38 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:

Here's v2 of this patch series. It's functionally identical to v1,
but I've rebased it over the recent auto-node-support-generation
changes, and also extracted a few separable bits in hopes of making
the main planner patch smaller. (It's still pretty durn large,
unfortunately.) Unlike the original submission, each step will
compile on its own, though the intermediate states mostly don't
pass all regression tests.

Noticed a different behavior from previous regarding PlaceHolderVar.
Take the query below as an example:

select a.i, ss.jj from a left join (select b.i, b.j + 1 as jj from b) ss
on a.i = ss.i;

Previously the expression 'b.j + 1' would not be wrapped in a
PlaceHolderVar, since it contains a Var of the subquery and meanwhile it
does not contain any non-strict constructs. And now in the patch, we
would insert a PlaceHolderVar for it, in order to have a place to store
varnullingrels. So the plan for the above query now becomes:

# explain (verbose, costs off) select a.i, ss.jj from a left join
(select b.i, b.j + 1 as jj from b) ss on a.i = ss.i;
QUERY PLAN
----------------------------------
Hash Right Join
Output: a.i, ((b.j + 1))
Hash Cond: (b.i = a.i)
-> Seq Scan on public.b
Output: b.i, (b.j + 1)
-> Hash
Output: a.i
-> Seq Scan on public.a
Output: a.i
(9 rows)

Note that the evaluation of expression 'b.j + 1' now occurs below the
outer join. Is this something we need to be concerned about?

Thanks
Richard

Richard Guo <guofenglinux@gmail.com> writes:

Note that the evaluation of expression 'b.j + 1' now occurs below the
outer join. Is this something we need to be concerned about?

It seems more formally correct to me, but perhaps somebody would
complain about possibly-useless expression evals. We could likely
re-complicate the logic that inserts PHVs during pullup so that it
looks for Vars it can apply the nullingrels to. Maybe there's an
opportunity to share code with flatten_join_alias_vars?

regards, tom lane

On Tue, Jul 12, 2022 at 9:37 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

Richard Guo <guofenglinux@gmail.com> writes:

Note that the evaluation of expression 'b.j + 1' now occurs below the
outer join. Is this something we need to be concerned about?

It seems more formally correct to me, but perhaps somebody would
complain about possibly-useless expression evals. We could likely
re-complicate the logic that inserts PHVs during pullup so that it
looks for Vars it can apply the nullingrels to. Maybe there's an
opportunity to share code with flatten_join_alias_vars?

Yeah, maybe we can extend and leverage the codes in
adjust_standard_join_alias_expression() to do that?

But I'm not sure which is better, to evaluate the expression below or
above the outer join. It seems to me that if the size of base rel is
large and somehow the size of the joinrel is small, evaluation above the
outer join would win. And in the opposite case evaluation below the
outer join would be better.

Thanks
Richard

Richard Guo <guofenglinux@gmail.com> writes:

But I'm not sure which is better, to evaluate the expression below or
above the outer join. It seems to me that if the size of base rel is
large and somehow the size of the joinrel is small, evaluation above the
outer join would win. And in the opposite case evaluation below the
outer join would be better.

Reasonable question. But I think for the purposes of this patch,
it's better to keep the old behavior as much as we can. People
have probably relied on it while tuning queries. (I'm not saying
it has to be *exactly* bug-compatible, but simple cases like your
example probably should work the same.)

regards, tom lane

Here's a rebase up to HEAD, mostly to placate the cfbot.
I accounted for d8e34fa7a (s/all_baserels/all_query_rels/
in those places) and made one tiny bug-fix change.
Nothing substantive as yet.

regards, tom lane

Zhihong Yu <zyu@yugabyte.com> writes:

For v3-0003-label-Var-nullability-in-parser.patch :

+   if (rtindex > 0 && rtindex <= list_length(pstate->p_nullingrels))
+       relids = (Bitmapset *) list_nth(pstate->p_nullingrels, rtindex - 1);
+   else
+       relids = NULL;
+
+   /*
+    * Merge with any already-declared nulling rels.  (Typically there won't
+    * be any, but let's get it right if there are.)
+    */
+   if (relids != NULL)

It seems the last if block can be merged into the previous if block. That
way `relids = NULL` can be omitted.

No, because the list entry we fetch could be NULL.

regards, tom lane

On Mon, Aug 1, 2022 at 12:51 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

Here's a rebase up to HEAD, mostly to placate the cfbot.
I accounted for d8e34fa7a (s/all_baserels/all_query_rels/
in those places) and made one tiny bug-fix change.
Nothing substantive as yet.

regards, tom lane

Hi,

For v3-0003-label-Var-nullability-in-parser.patch :

+   if (rtindex > 0 && rtindex <= list_length(pstate->p_nullingrels))
+       relids = (Bitmapset *) list_nth(pstate->p_nullingrels, rtindex - 1);
+   else
+       relids = NULL;
+
+   /*
+    * Merge with any already-declared nulling rels.  (Typically there won't
+    * be any, but let's get it right if there are.)
+    */
+   if (relids != NULL)

It seems the last if block can be merged into the previous if block. That
way `relids = NULL` can be omitted.

Cheers

On Tue, Aug 2, 2022 at 3:51 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:

Here's a rebase up to HEAD, mostly to placate the cfbot.
I accounted for d8e34fa7a (s/all_baserels/all_query_rels/
in those places) and made one tiny bug-fix change.
Nothing substantive as yet.

When we add required PlaceHolderVars to a join rel's targetlist, if the
PHV can be computed in the nullable-side of the join, we would add the
join's RT index to phnullingrels. This is correct as we know the PHV's
value can be nulled at this join. But I'm wondering if it is necessary
since we have already propagated any varnullingrels into the PHV when we
apply pullup variable replacement in perform_pullup_replace_vars().

On the other hand, the phnullingrels may contain RT indexes of outer
joins above this join level. It seems not good to add such a PHV to the
joinrel's targetlist. Below is an example:

# explain (verbose, costs off) select a.i, ss.jj from a left join (b left
join (select c.i, coalesce(c.j, 1) as jj from c) ss on b.i = ss.i) on true;
QUERY PLAN
---------------------------------------------------------
Nested Loop Left Join
Output: a.i, (COALESCE(c.j, 1))
-> Seq Scan on public.a
Output: a.i, a.j
-> Materialize
Output: (COALESCE(c.j, 1))
-> Hash Left Join
Output: (COALESCE(c.j, 1))
Hash Cond: (b.i = c.i)
-> Seq Scan on public.b
Output: b.i, b.j
-> Hash
Output: c.i, (COALESCE(c.j, 1))
-> Seq Scan on public.c
Output: c.i, COALESCE(c.j, 1)
(15 rows)

In this query, for the joinrel {B, C}, the PHV in its targetlist has a
phnullingrels that contains the join of {A} and {BC}, which is confusing
because we have not reached that join level.

I tried the changes below to illustrate the two issues. The assertion
holds true during regression tests and the error pops up for the query
above.

--- a/src/backend/optimizer/util/placeholder.c
+++ b/src/backend/optimizer/util/placeholder.c
@@ -464,18 +464,20 @@ add_placeholders_to_joinrel(PlannerInfo *root,
RelOptInfo *joinrel,
                       {
                               if (sjinfo->jointype == JOIN_FULL &&
sjinfo->ojrelid != 0)
                               {
-                                      /* PHV's value can be nulled at this
join */
-                                      phv->phnullingrels =
bms_add_member(phv->phnullingrels,
-
                                   sjinfo->ojrelid);
+
 Assert(bms_is_member(sjinfo->ojrelid, phv->phnullingrels));
+
+                                      if
(!bms_is_subset(phv->phnullingrels, joinrel->relids))
+                                              elog(ERROR, "phnullingrels
is not subset of joinrel's relids");
                               }
                       }
                       else if (bms_is_subset(phinfo->ph_eval_at,
inner_rel->relids))
                       {
                               if (sjinfo->jointype != JOIN_INNER &&
sjinfo->ojrelid != 0)
                               {
-                                      /* PHV's value can be nulled at this
join */
-                                      phv->phnullingrels =
bms_add_member(phv->phnullingrels,
-
                                   sjinfo->ojrelid);
+
 Assert(bms_is_member(sjinfo->ojrelid, phv->phnullingrels));
+
+                                      if
(!bms_is_subset(phv->phnullingrels, joinrel->relids))
+                                              elog(ERROR, "phnullingrels
is not subset of joinrel's relids");
                               }
                       }

If the two issues are indeed something we need to fix, maybe we can
change add_placeholders_to_joinrel() to search the PHVs from
outer_rel/inner_rel's targetlist, and add the ojrelid to phnullingrels
if needed, just like what we do in build_joinrel_tlist(). The PHVs there
should have the correct phnullingrels (at least the PHVs in base rels'
targetlists have correctly set phnullingrels to NULL).

Thanks
Richard

Richard Guo <guofenglinux@gmail.com> writes:

When we add required PlaceHolderVars to a join rel's targetlist, if the
PHV can be computed in the nullable-side of the join, we would add the
join's RT index to phnullingrels. This is correct as we know the PHV's
value can be nulled at this join. But I'm wondering if it is necessary
since we have already propagated any varnullingrels into the PHV when we
apply pullup variable replacement in perform_pullup_replace_vars().

I'm not seeing the connection there? Any nullingrels that are set
during perform_pullup_replace_vars would refer to outer joins within the
pulled-up subquery, whereas what you are talking about here is what
happens when the PHV's value propagates up through outer joins of the
parent query. There's no overlap between those relid sets, or if there
is we have some fault in the logic that constrains join order to ensure
that there's a valid place to compute each PHV.

On the other hand, the phnullingrels may contain RT indexes of outer
joins above this join level. It seems not good to add such a PHV to the
joinrel's targetlist.

Hmm, yeah, add_placeholders_to_joinrel is doing this wrong. The
intent was to match what build_joinrel_tlist does with plain Vars,
but in that case we're adding the join's relid to what we find in
varnullingrels in the input tlist. Using the phnullingrels from
the placeholder_list entry is wrong. (I wonder whether a
placeholder_list entry's phnullingrels is meaningful at all?
Maybe it isn't.) I think it might work to take the intersection
of the join's relids with root->outer_join_rels.

If the two issues are indeed something we need to fix, maybe we can
change add_placeholders_to_joinrel() to search the PHVs from
outer_rel/inner_rel's targetlist, and add the ojrelid to phnullingrels
if needed, just like what we do in build_joinrel_tlist(). The PHVs there
should have the correct phnullingrels (at least the PHVs in base rels'
targetlists have correctly set phnullingrels to NULL).

Yeah, maybe we should do something more invasive and make use of the
input targetlists rather than doing this from scratch. Not sure.
I'm worried that doing it that way would increase the risk of getting
different join tlist contents depending on which pair of input rels
we happen to consider first.

regards, tom lane

I wrote:

Richard Guo <guofenglinux@gmail.com> writes:

If the two issues are indeed something we need to fix, maybe we can
change add_placeholders_to_joinrel() to search the PHVs from
outer_rel/inner_rel's targetlist, and add the ojrelid to phnullingrels
if needed, just like what we do in build_joinrel_tlist(). The PHVs there
should have the correct phnullingrels (at least the PHVs in base rels'
targetlists have correctly set phnullingrels to NULL).

Yeah, maybe we should do something more invasive and make use of the
input targetlists rather than doing this from scratch. Not sure.
I'm worried that doing it that way would increase the risk of getting
different join tlist contents depending on which pair of input rels
we happen to consider first.

After chewing on that for awhile, I've concluded that that is the way
to go. 0001 attached is a standalone patch to rearrange the way that
PHVs are added to joinrel targetlists. It results in one cosmetic
change in the regression tests, where the targetlist order for an
intermediate join node changes. I think that's fine; if anything,
the new order is more sensible than the old because it matches the
inputs' targetlist orders better.

I believe the reason I didn't do it like this to start with is that
I was concerned about the cost of searching the placeholder_list
repeatedly. With a lot of PHVs, build_joinrel_tlist becomes O(N^2)
just from the repeated find_placeholder_info lookups. We can fix
that by adding an index array to go straight from phid to the
PlaceHolderInfo. While thinking about where to construct such
an index array, I decided it'd be a good idea to have an explicit
step to "freeze" the set of PlaceHolderInfos, at the start of
deconstruct_jointree. This allows getting rid of the create_new_ph
flags for find_placeholder_info and add_vars_to_targetlist, which
I've always feared were bugs waiting to happen: they require callers
to have a very clear understanding of when they're invoked. There
might be some speed gain over existing code too, but I've not really
tried to measure it. I did drop a couple of hacks that were only
meant to short-circuit find_placeholder_info calls; that function
should now be cheap enough to not matter.

Barring objections, I'd like to push these soon and then rebase
the main outer-join-vars patch set over them.

regards, tom lane

I wrote:

... We can fix
that by adding an index array to go straight from phid to the
PlaceHolderInfo. While thinking about where to construct such
an index array, I decided it'd be a good idea to have an explicit
step to "freeze" the set of PlaceHolderInfos, at the start of
deconstruct_jointree.

On further thought, it seems better to maintain the index array
from the start, allowing complete replacement of the linear list
searches. We can add a separate bool flag to denote frozen-ness.
This does have minor downsides:

* Some fiddly code is needed to enlarge the index array at need.
But it's not different from that for, say, simple_rel_array.

* If we ever have a need to mutate the placeholder_list as a whole,
we'd have to reconstruct the index array to point to the new
objects. We don't do that at present, except in one place in
analyzejoins.c, which is easily fixed. While the same argument
could be raised against the v1 patch, it's not very likely that
we'd be doing such mutation beyond the start of deconstruct_jointree.

Hence, see v2 attached.

regards, tom lane

On Wed, Aug 17, 2022 at 4:57 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:

On further thought, it seems better to maintain the index array
from the start, allowing complete replacement of the linear list
searches. We can add a separate bool flag to denote frozen-ness.

+1 for 0001 patch. Now we process plain Vars and PlaceHolderVars in a
more consistent way when building joinrel's tlist. And this change would
make it easier to build up phnullingrels for PHVs as we climb up the
join tree.

BTW, the comment just above the two calls to build_joinrel_tlist says:

* Create a new tlist containing just the vars that need to be output from

Here by 'vars' it means both plain Vars and PlaceHolderVars, right? If
not we may need to adjust this comment to also include PlaceHolderVars.

0002 patch looks good to me. Glad we can get rid of create_new_ph flag.
A minor comment is that seems we can get rid of phid inside
PlaceHolderInfo, since we do not do linear list searches any more. It's
some duplicate to the phid inside PlaceHolderVar. Currently there are
two places referencing PlaceHolderInfo->phid, remove_rel_from_query and
find_placeholder_info. We can use PlaceHolderVar->phid instead in both
the two places.

Thanks
Richard