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

From: Richard Guo <[email-masked]>
Date: Mon, 25 Dec 2023 15:01:51 +0800

On Thu, Jul 13, 2023 at 3:12 PM Richard Guo <[email-masked]> wrote:

> 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.
>

I'd like to add that not checking PHVs for lateral references can lead
to performance regressions with Memoize node.  For instance,

-- by default, enable_memoize is on
regression=# explain (analyze, costs off) select * from tenk1 t1 left join
lateral (select *, t1.four as x from tenk1 t2) s on t1.two = s.two;
                                     QUERY PLAN
-------------------------------------------------------------------------------------
 Nested Loop Left Join (actual time=0.028..105245.547 rows=50000000 loops=1)
   ->  Seq Scan on tenk1 t1 (actual time=0.011..3.760 rows=10000 loops=1)
   ->  Memoize (actual time=0.010..8.051 rows=5000 loops=10000)
         Cache Key: t1.two
         Cache Mode: logical
         Hits: 0  Misses: 10000  Evictions: 9999  Overflows: 0  Memory
Usage: 1368kB
         ->  Seq Scan on tenk1 t2 (actual time=0.004..3.594 rows=5000
loops=10000)
               Filter: (t1.two = two)
               Rows Removed by Filter: 5000
 Planning Time: 1.943 ms
 Execution Time: 106806.043 ms
(11 rows)

-- turn enable_memoize off
regression=# set enable_memoize to off;
SET
regression=# explain (analyze, costs off) select * from tenk1 t1 left join
lateral (select *, t1.four as x from tenk1 t2) s on t1.two = s.two;
                                 QUERY PLAN
-----------------------------------------------------------------------------
 Nested Loop Left Join (actual time=0.048..44831.707 rows=50000000 loops=1)
   ->  Seq Scan on tenk1 t1 (actual time=0.026..2.340 rows=10000 loops=1)
   ->  Seq Scan on tenk1 t2 (actual time=0.002..3.282 rows=5000 loops=10000)
         Filter: (t1.two = two)
         Rows Removed by Filter: 5000
 Planning Time: 0.641 ms
 Execution Time: 46472.609 ms
(7 rows)

As we can see, when Memoize enabled (which is the default setting), the
execution time increases by around 129.83%, indicating a significant
performance regression.

This is caused by that we fail to realize that 't1.four', which is from
the PHV, should be included in the cache keys.  And that makes us have
to purge the entire cache every time we get a new outer tuple.  This is
also implied by the abnormal Memoize runtime stats:

    Hits: 0  Misses: 10000  Evictions: 9999  Overflows: 0

This regression can be fixed by the patch here.  After applying the v4
patch, 't1.four' is added into the cache keys, and the same query runs
much faster.

regression=# explain (analyze, costs off) select * from tenk1 t1 left join
lateral (select *, t1.four as x from tenk1 t2) s on t1.two = s.two;
                                   QUERY PLAN
---------------------------------------------------------------------------------
 Nested Loop Left Join (actual time=0.060..20446.004 rows=50000000 loops=1)
   ->  Seq Scan on tenk1 t1 (actual time=0.027..5.845 rows=10000 loops=1)
   ->  Memoize (actual time=0.001..0.209 rows=5000 loops=10000)
         Cache Key: t1.two, t1.four
         Cache Mode: binary
         Hits: 9996  Misses: 4  Evictions: 0  Overflows: 0  Memory Usage:
5470kB
         ->  Seq Scan on tenk1 t2 (actual time=0.005..3.659 rows=5000
loops=4)
               Filter: (t1.two = two)
               Rows Removed by Filter: 5000
 Planning Time: 0.579 ms
 Execution Time: 21756.598 ms
(11 rows)

Comparing the first plan and the third plan, this query runs ~5 times
faster.

Thanks
Richard

---

From: Richard Guo <[email-masked]>
Date: Fri, 2 Feb 2024 17:18:59 +0800

On Mon, Dec 25, 2023 at 3:01 PM Richard Guo <[email-masked]> wrote:

> to performance regressions with Memoize node.
>

The v4 patch does not apply any more.  I've rebased it on master.
Nothing else has changed.

Thanks
Richard

---

From: Richard Guo <[email-masked]>
Date: Mon, 18 Mar 2024 16:36:01 +0800

> Nothing else has changed.

Here is another rebase over master so it applies again.  I also added a
commit message to help review.  Nothing else has changed.

Thanks
Richard

---

From: Richard Guo <[email-masked]>
Date: Tue, 18 Jun 2024 09:47:27 +0800

> commit message to help review.  Nothing else has changed.

AFAIU currently we do not add Memoize nodes on top of join relation
paths.  This is because the ParamPathInfos for join relation paths do
not maintain ppi_clauses, as the set of relevant clauses varies
depending on how the join is formed.  In addition, joinrels do not
maintain lateral_vars.  So we do not have a way to extract cache keys
from joinrels.

(Besides, there are places where the code doesn't cope with Memoize path
on top of a joinrel path, such as in get_param_path_clause_serials.)

Therefore, when extracting lateral references within PlaceHolderVars,
there is no need to consider those that are due to be evaluated at
joinrels.

Hence, here is v7 patch for that.  In passing, this patch also includes
a comment explaining that Memoize nodes are currently not added on top
of join relation paths (maybe we should have a separate patch for this?).

Thanks
Richard

---

From: Andrei Lepikhov <[email-masked]>
Date: Fri, 28 Jun 2024 21:14:53 +0700

> of join relation paths (maybe we should have a separate patch for this?).
Hi,
I have reviewed v7 of the patch. This improvement is good enough to be 
applied, thought. Here is some notes:

Comment may be rewritten for clarity:
"Determine if the clauses in param_info and innerrel's lateral_vars" -
I'd replace lateral_vars with 'lateral references' to combine in one 
phrase PHV from rel and root->placeholder_list sources.

I wonder if we can add whole PHV expression instead of the Var (as 
discussed above) just under some condition:
if (!bms_intersect(pull_varnos(root, (Node *) phinfo->ph_var->phexpr), 
innerrelids))
{
   // Add whole PHV
}
else
{
   // Add only pulled vars
}

I got the point about Memoize over join, but as a join still calls 
replace_nestloop_params to replace parameters in its clauses, why not to 
invent something similar to find Memoize keys inside specific JoinPath 
node? It is not the issue of this patch, though - but is it doable?

IMO, the code:
if (bms_nonempty_difference(outerPlan->chgParam, node->keyparamids))
   cache_purge_all(node);

is a good place to check an assertion: is it really the parent query 
parameters that make a difference between memoize keys and node list of 
parameters?

Generally, this patch looks good for me to be committed.

-- 
regards, Andrei Lepikhov

---

From: Richard Guo <[email-masked]>
Date: Thu, 11 Jul 2024 17:18:39 +0800

On Fri, Jun 28, 2024 at 10:14 PM Andrei Lepikhov <[email-masked]> wrote:
> applied, thought.

Thank you for reviewing this patch!

> phrase PHV from rel and root->placeholder_list sources.

Makes sense.  I ended up using 'innerrel's lateral vars' to include
both the lateral Vars/PHVs found in innerrel->lateral_vars and those
extracted from within PlaceHolderVars that are due to be evaluated at
innerrel.

> if (!bms_intersect(pull_varnos(root, (Node *) phinfo->ph_var->phexpr),

Good point.  After considering it further, I think we should do this.
As David explained, this can be beneficial in cases where the whole
expression results in fewer distinct values to cache tuples for.

> node? It is not the issue of this patch, though - but is it doable?

I don't think it's impossible to do, but I'm skeptical that there's an
easy way to identify all the cache keys for joinrels, without having
available ppi_clauses and lateral_vars.

> parameters that make a difference between memoize keys and node list of

I don't think we have enough info available here to identify which
params within outerPlan->chgParam are from outer levels.  Maybe we can
store root->outer_params in the MemoizeState node to help with this
assertion, but I'm not sure if it's worth the trouble.

Attached is an updated version of this patch.

Thanks
Richard

---

From: Andrei Lepikhov <[email-masked]>
Date: Fri, 12 Jul 2024 10:18:10 +0700

> available ppi_clauses and lateral_vars.
Ok

> assertion, but I'm not sure if it's worth the trouble.
Got it
> Attached is an updated version of this patch.
I'm not sure about stability of output format of AVG aggregate across 
different platforms. Maybe better to return the result of comparison 
between the AVG() and expected value?

-- 
regards, Andrei Lepikhov

---

From: Richard Guo <[email-masked]>
Date: Mon, 15 Jul 2024 09:36:37 +0800

> Attached is an updated version of this patch.

I've pushed this patch.  Thanks for all the reviews.

Thanks
Richard