Thread: Check lateral references within PHVs for memoize cache keys

On Fri, 30 Dec 2022 at 16:00, Richard Guo <guofenglinux@gmail.com> wrote:
>
> On Fri, Dec 9, 2022 at 5:16 PM Richard Guo <guofenglinux@gmail.com> 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.

I'm surprised to see that it's only Memoize that ever makes use of
lateral_vars. I'd need a bit more time to process your patch, but one
additional thought I had was that I wonder if the following code is
still needed in nodeMemoize.c

if (bms_nonempty_difference(outerPlan->chgParam, node->keyparamids))
    cache_purge_all(node);

Ideally, that would be an Assert failure, but possibly we should
probably still call cache_purge_all(node) after Assert(false) so that
at least we'd not start returning wrong results if we've happened to
miss other cache keys. I thought maybe something like:

if (bms_nonempty_difference(outerPlan->chgParam, node->keyparamids))
{
    /*
     * Really the planner should have added all the possible parameters to
     * the cache keys, so let's Assert fail here so we get the memo to fix
     * that can fix that.  On production builds, we'd better purge the
     * cache to account for the changed parameter value.
     */
    Assert(false);

    cache_purge_all(node);
}

I've not run the tests to ensure we don't get an Assert failure with
that, however.

All that cache_purge_all code added in 411137a42 likely was an
incorrect fix for what you've raised here, but it's maybe a good
failsafe to keep around even if we think we've now found all possible
parameters that can invalidate the memorized results.

David

On Tue, Jul 4, 2023 at 12:33 AM Richard Guo <guofenglinux@gmail.com> wrote:
>
> 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              ~{:-)
pj@illuminatedcomputing.com

Richard Guo <guofenglinux@gmail.com> writes:
> 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

On Sun, 9 Jul 2023 at 05:28, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> 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?

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)

On Sat, 8 Jul 2023 at 17:24, Paul A Jungwirth
<pj@illuminatedcomputing.com> wrote:
> 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?

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

David

On Mon, Mar 18, 2024 at 4:36 PM Richard Guo <guofenglinux@gmail.com> wrote:
> Here is another rebase over master so it applies again.  I also added a
> 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

On 6/18/24 08:47, Richard Guo wrote:
> On Mon, Mar 18, 2024 at 4:36 PM Richard Guo <guofenglinux@gmail.com> wrote:
>> Here is another rebase over master so it applies again.  I also added a
>> 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?).
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

On Fri, Jun 28, 2024 at 10:14 PM Andrei Lepikhov <lepihov@gmail.com> wrote:
> I have reviewed v7 of the patch. This improvement is good enough to be
> applied, thought.

Thank you for reviewing this patch!

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

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.

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

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.

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

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.

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

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

On 7/11/24 16:18, Richard Guo wrote:
> On Fri, Jun 28, 2024 at 10:14 PM Andrei Lepikhov <lepihov@gmail.com> wrote:
>> 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?
> 
> 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.
Ok

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

On Fri, Jul 12, 2024 at 11:18 AM Andrei Lepikhov <lepihov@gmail.com> wrote:
> 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?

I don't think this is a problem.  AFAIK we use AVG() a lot in the
existing test cases.

Thanks
Richard

On Thu, Jul 11, 2024 at 5:18 PM Richard Guo <guofenglinux@gmail.com> wrote:
> Attached is an updated version of this patch.

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

Thanks
Richard