Thread: An inefficient query caused by unnecessary PlaceHolderVar

On Fri, May 12, 2023 at 2:35 AM Richard Guo <guofenglinux@gmail.com> wrote:
>
> I happened to notice that the query below can be inefficient.
>
> # explain (costs off)
> select * from
>   int8_tbl a left join
>   (int8_tbl b inner join
>    lateral (select *, b.q2 as x from int8_tbl c) ss on b.q2 = ss.q1)
>   on a.q1 = b.q1;
>              QUERY PLAN
> ------------------------------------
>  Hash Right Join
>    Hash Cond: (b.q1 = a.q1)
>    ->  Nested Loop
>          ->  Seq Scan on int8_tbl b
>          ->  Seq Scan on int8_tbl c
>                Filter: (b.q2 = q1)
>    ->  Hash
>          ->  Seq Scan on int8_tbl a
> (8 rows)
>
> For B/C join, currently we only have one option, i.e., nestloop with
> parameterized inner path.  This could be extremely inefficient in some
> cases, such as when C does not have any indexes, or when B is very
> large.  I believe the B/C join can actually be performed with hashjoin
> or mergejoin here, as it is an inner join.
>
> This happens because when we pull up the lateral subquery, we notice
> that Var 'x' is a lateral reference to 'b.q2' which is outside the
> subquery.  So we wrap it in a PlaceHolderVar.  This is necessary for
> correctness if it is a lateral reference from nullable side to
> non-nullable item.  But here in this case, the referenced item is also
> nullable, so actually we can omit the PlaceHolderVar with no harm.  The
> comment in pullup_replace_vars_callback() also explains this point.
>
>    * (Even then, we could omit the PlaceHolderVar if
>    * the referenced rel is under the same lowest outer join, but
>    * it doesn't seem worth the trouble to check that.)

It's nice that someone already thought about this and left us this comment :)

> All such PHVs would imply lateral dependencies which would make us have
> no choice but nestloop.  I think we should avoid such PHVs as much as
> possible.  So IMO it may 'worth the trouble to check that'.
>
> Attached is a patch to check that for simple Vars.  Maybe we can extend
> it to avoid PHVs for more complex expressions, but that requires some
> codes because for now we always wrap non-var expressions to PHVs in
> order to have a place to insert nulling bitmap.  As a first step, let's
> do it for simple Vars only.
>
> Any thoughts?

This looks good to me.

A few small tweaks suggested to comment wording:

+-- lateral reference for simple Var can escape PlaceHolderVar if the
+-- referenced rel is under the same lowest nulling outer join
+explain (verbose, costs off)

I think this is clearer: "lateral references to simple Vars do not
need a PlaceHolderVar when the referenced rel is part of the same
lowest nulling outer join"?

                  * lateral references to something outside the subquery being
-                 * pulled up.  (Even then, we could omit the PlaceHolderVar if
-                 * the referenced rel is under the same lowest outer join, but
-                 * it doesn't seem worth the trouble to check that.)
+                 * pulled up.  Even then, we could omit the PlaceHolderVar if
+                 * the referenced rel is under the same lowest nulling outer
+                 * join.

I think this is clearer: "references something outside the subquery
being pulled up and is not under the same lowest outer join."

One other thing: it would be helpful to have the test query output be
stable between HEAD and this patch; perhaps add:

order by 1, 2, 3, 4, 5, 6, 7

to ensure stability?

Thanks,
James Coleman

On Wed, May 31, 2023 at 10:30 PM Richard Guo <guofenglinux@gmail.com> wrote:
>
>
> On Wed, May 31, 2023 at 1:27 AM James Coleman <jtc331@gmail.com> wrote:
>>
>> This looks good to me.
>
>
> Thanks for the review!

Sure thing!

>>
>> A few small tweaks suggested to comment wording:
>>
>> +-- lateral reference for simple Var can escape PlaceHolderVar if the
>> +-- referenced rel is under the same lowest nulling outer join
>> +explain (verbose, costs off)
>>
>> I think this is clearer: "lateral references to simple Vars do not
>> need a PlaceHolderVar when the referenced rel is part of the same
>> lowest nulling outer join"?
>
>
> Thanks for the suggestion!  How about we go with "lateral references to
> simple Vars do not need a PlaceHolderVar when the referenced rel is
> under the same lowest nulling outer join"?  This seems a little more
> consistent with the comment in prepjointree.c.

That sounds good to me.

>>
>>                   * lateral references to something outside the subquery being
>> -                 * pulled up.  (Even then, we could omit the PlaceHolderVar if
>> -                 * the referenced rel is under the same lowest outer join, but
>> -                 * it doesn't seem worth the trouble to check that.)
>> +                 * pulled up.  Even then, we could omit the PlaceHolderVar if
>> +                 * the referenced rel is under the same lowest nulling outer
>> +                 * join.
>>
>> I think this is clearer: "references something outside the subquery
>> being pulled up and is not under the same lowest outer join."
>
>
> Agreed.  Will use this one.
>
>>
>> One other thing: it would be helpful to have the test query output be
>> stable between HEAD and this patch; perhaps add:
>>
>> order by 1, 2, 3, 4, 5, 6, 7
>>
>> to ensure stability?
>
>
> Thanks for the suggestion!  I wondered about that too but I'm a bit
> confused about whether we should add ORDER BY in test case.  I checked
> 'sql/join.sql' and found that some queries are using ORDER BY but some
> are not.  Not sure what the criteria are.

I think it's just "is this helpful in this test". Obviously we don't
need it for correctness of this particular check, but as long as the
plan change still occurs as desired (i.e., the ORDER BY doesn't change
the plan from what you're testing) I think it's fine to consider it
author's choice.

James

On Mon, Jan 15, 2024 at 1:50 PM Richard Guo <guofenglinux@gmail.com> wrote:
> Updated this patch over 29f114b6ff, which indicates that we should apply
> the same rules for PHVs.

Here is a new rebase of this patch, with some tweaks to comments.  I've
also updated the commit message to better explain the context.

To recap, this patch tries to avoid wrapping Vars and PHVs from subquery
output that are lateral references to something outside the subquery.
Typically this kind of wrapping is necessary when the Var/PHV references
the non-nullable side of the outer join from the nullable side, because
we need to ensure that it is evaluated at the right place and hence is
forced to null when the outer join should do so.  But if the referenced
rel is under the same lowest nulling outer join, we can actually omit
the wrapping.  The PHVs generated from such kind of wrapping imply
lateral dependencies and force us to resort to nestloop joins, so we'd
better get rid of them.

This patch performs this check by remembering the relids of the nullable
side of the lowest outer join the subquery is within.  So I think it
improves the overall plan in the related cases with very little extra
cost.

Thanks
Richard