Re: Check lateral references within PHVs for memoize cache keys

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