Subject: Re: Check lateral references within PHVs for memoize cache keys

From: Richard Guo <[email-masked]>
Date: Tue, 4 Jul 2023 15:33:22 +0800

On Fri, Dec 30, 2022 at 11:00 AM Richard Guo <[email-masked]> wrote:

> On Fri, Dec 9, 2022 at 5:16 PM Richard Guo <[email-masked]> wrote:
>
>> Actually we do have checked PHVs for lateral references, earlier in
>> create_lateral_join_info.  But that time we only marked lateral_relids
>> and direct_lateral_relids, without remembering the lateral expressions.
>> So I'm wondering whether we can fix that by fetching Vars (or PHVs) of
>> lateral references within PlaceHolderVars and remembering them in the
>> baserel's lateral_vars.
>>
>> Attach a draft patch to show my thoughts.
>>
>
> Update the patch to fix test failures.
>

Rebase the patch on HEAD as cfbot reminds.

Thanks
Richard

---

From: Paul A Jungwirth <[email-masked]>
Date: Fri, 7 Jul 2023 22:24:27 -0700

> Rebase the patch on HEAD as cfbot reminds.

All of this seems good to me. I can reproduce the problem, tests pass,
and the change is sensible as far as I can tell.

One adjacent thing I noticed is that when we renamed "Result Cache" to
"Memoize" this bit of the docs in config.sgml got skipped (probably
because of the line break):

        Hash tables are used in hash joins, hash-based aggregation, result
        cache nodes and hash-based processing of <literal>IN</literal>
        subqueries.

I believe that should say "memoize nodes" instead. Is it worth
correcting that as part of this patch? Or perhaps another one?

Regards,

-- 
Paul              ~{:-)
[email-masked]

---

From: Tom Lane <[email-masked]>
Date: Sat, 08 Jul 2023 13:28:43 -0400

> Rebase the patch on HEAD as cfbot reminds.

This fix seems like a mess.  The function that is in charge of filling
RelOptInfo.lateral_vars is extract_lateral_references; or at least
that was how it was done up to now.  Can't we compute these additional
references there?  If not, maybe we ought to just merge
extract_lateral_references into create_lateral_join_info, rather than
having the responsibility split.  I also wonder whether this change
isn't creating hidden dependencies on RTE order (which would likely be
bugs), since create_lateral_join_info itself examines the lateral_vars
lists as it walks the rtable.

More generally, it's not clear to me why we should need to look inside
lateral PHVs in the first place.  Wouldn't the lateral PHV itself
serve fine as a cache key?

			regards, tom lane

---

From: David Rowley <[email-masked]>
Date: Sun, 9 Jul 2023 13:11:41 +1200

> serve fine as a cache key?

For Memoize specifically, I purposefully made it so the expression was
used as a cache key rather than extracting the Vars from it and using
those.  The reason for that was that the expression may result in
fewer distinct values to cache tuples for. For example:

create table t1 (a int primary key);
create table t2 (a int primary key);

create statistics on (a % 10) from t2;
insert into t2 select x from generate_Series(1,1000000)x;
insert into t1 select x from generate_Series(1,1000000)x;

analyze t1,t2;
explain (analyze, costs off) select * from t1 inner join t2 on t1.a=t2.a%10;
                                         QUERY PLAN
--------------------------------------------------------------------------------------------
 Nested Loop (actual time=0.015..212.798 rows=900000 loops=1)
   ->  Seq Scan on t2 (actual time=0.006..33.479 rows=1000000 loops=1)
   ->  Memoize (actual time=0.000..0.000 rows=1 loops=1000000)
         Cache Key: (t2.a % 10)
         Cache Mode: logical
         Hits: 999990  Misses: 10  Evictions: 0  Overflows: 0  Memory Usage: 1kB
         ->  Index Only Scan using t1_pkey on t1 (actual
time=0.001..0.001 rows=1 loops=10)
               Index Cond: (a = (t2.a % 10))
               Heap Fetches: 0
 Planning Time: 0.928 ms
 Execution Time: 229.621 ms
(11 rows)

---

From: David Rowley <[email-masked]>
Date: Sun, 9 Jul 2023 16:17:03 +1200

> correcting that as part of this patch? Or perhaps another one?

I just pushed a fix for this.  Thanks for reporting it.

David

---

From: Richard Guo <[email-masked]>
Date: Thu, 13 Jul 2023 15:12:29 +0800

> lists as it walks the rtable.

Yeah, you're right.  Currently all RelOptInfo.lateral_vars are filled in
extract_lateral_references.  And then in create_lateral_join_info these
lateral_vars, together with all PlaceHolderInfos, are examined to
compute the per-base-relation lateral refs relids.  However, in the
process of extract_lateral_references, it's possible that we create new
PlaceHolderInfos.  So I think it may not be a good idea to extract the
lateral references within PHVs there.  But I agree with you that it's
also not a good idea to compute these additional lateral Vars within
PHVs in create_lateral_join_info as the patch does.  Actually with the
patch I find that with PHVs that are due to be evaluated at a join we
may get a problematic plan.  For instance

explain (costs off)
select * from t t1 left join lateral
(select t1.a as t1a, t2.a as t2a from t t2 join t t3 on true) s on true
where s.t1a = s.t2a;
             QUERY PLAN
------------------------------------
 Nested Loop
   ->  Seq Scan on t t1
   ->  Nested Loop
         Join Filter: (t1.a = t2.a)
         ->  Seq Scan on t t2
         ->  Memoize
               Cache Key: t1.a
               Cache Mode: binary
               ->  Seq Scan on t t3
(9 rows)

There are no lateral refs in the subtree of the Memoize node, so it
should be a Materialize node rather than a Memoize node.  This is caused
by that for a PHV that is due to be evaluated at a join, we fill its
lateral refs in each baserel in the join, which is wrong.

So I'm wondering if it'd be better that we move all this logic of
computing additional lateral references within PHVs to get_memoize_path,
where we can examine only PHVs that are evaluated at innerrel.  And
considering that these lateral refs are only used by Memoize, it seems
more sensible to compute them there.  But I'm a little worried that
doing this would make get_memoize_path too expensive.

Please see v4 patch for this change.

Thanks
Richard

---

From: Richard Guo <[email-masked]>
Date: Thu, 13 Jul 2023 17:21:03 +0800

> serve fine as a cache key?

Do you mean we use the lateral PHV directly as a cache key?  Hmm, it
seems to me that we'd have problem if the PHV references rels that are
inside the PHV's syntactic scope.  For instance

select * from t t1 left join
    lateral (select t1.a+t2.a as t1a, t2.a as t2a from t t2) s on true
where s.t1a = s.t2a;

The PHV references t1.a so it's lateral.  But it also references t2.a,
so if we use the PHV itself as cache key, the plan would look like

               QUERY PLAN
----------------------------------------
 Nested Loop
   ->  Seq Scan on t t1
   ->  Memoize
         Cache Key: (t1.a + t2.a)
         Cache Mode: binary
         ->  Seq Scan on t t2
               Filter: ((t1.a + a) = a)
(7 rows)

which is an invalid plan as the cache key contains t2.a.

Thanks
Richard

---

From: Richard Guo <[email-masked]>
Date: Thu, 13 Jul 2023 17:29:42 +0800

> I just pushed a fix for this.  Thanks for reporting it.

BTW, I noticed a typo in the comment inside paraminfo_get_equal_hashops.

    foreach(lc, innerrel->lateral_vars)
    {
        Node       *expr = (Node *) lfirst(lc);
        TypeCacheEntry *typentry;

        /* Reject if there are any volatile functions in PHVs */
        if (contain_volatile_functions(expr))
        {
            list_free(*operators);
            list_free(*param_exprs);
            return false;
        }

The expressions in RelOptInfo.lateral_vars are not necessarily from
PHVs.  For instance

explain (costs off)
select * from t t1 join
    lateral (select * from t t2 where t1.a = t2.a offset 0) on true;
            QUERY PLAN
----------------------------------
 Nested Loop
   ->  Seq Scan on t t1
   ->  Memoize
         Cache Key: t1.a
         Cache Mode: binary
         ->  Seq Scan on t t2
               Filter: (t1.a = a)
(7 rows)

The lateral Var 't1.a' comes from the lateral subquery, not PHV.

This seems a typo from 63e4f13d.  How about we change it to the below?

-     /* Reject if there are any volatile functions in PHVs */
+     /* Reject if there are any volatile functions in lateral vars */

Thanks
Richard