PostgreSQL中Memoize节点功能解读

最近在看PostgreSQL16新特性时，注意优化器新特性中新增一条对于memoize相关功能。在深入了解后，其实Memoize是在PG14版本就已经引入了，主要是为了缓存在嵌套循环连接子计划的中间结果，这样在后续扫描中，如果与之前具有相同参数的扫描，就可以使用之前缓存的参数值，因此我们就可以跳过内部扫描。

在这里还有一个比较有趣的事情，Memoize这个节点名称其实在开发之初使用的名称为“Result Cache”，直译就是对结果的缓存，社区开发人员也认为这并不是是一个好名称，但是没有人想到一个大家都喜欢名称，因此当时暂时在代码中使用的就是Result Cache。直到David Johnston提出“Node Memoization”，也就是节点记忆，然后由Tom Lane将其修改为“Memoize”，。因此如果你在 一些文章中看到Memoization，其实就是指的Memoize，我相信你也能明白其中的原因了。下面我们来详细的对Memoize节点功能，进行详细的介绍。

如何缓存

在这里缓存使用的是hash表来实现的，也是一个LRU的双向链表。Memoize节点一般位于执行计划树中参数化节点的上方，以便缓存它们的结果。当我们需要添加新元组，但没有足够的空间存储时， 不会将元组溢出到磁盘，而是通过释放从LRU链表顶部开始的旧的条目，也就是最近最少使用的条目。当我们有新的条目和获得缓存命中的条目时，将该条目移动LRU链表的末尾，以便该条目将是最后一个被释放的；在这里内存消耗受到work_mem大小的限制。

何时缓存

对于嵌套循环连接的缓存，何时缓存完全取决于cost值。cost计算模型根据查看预期的调用次数、不同的cost估计值和work_mem大小，然后确定可以缓存多少项以及估计预期的缓存命中率和删除率，最后为缓存和缓存查找增加一些额外的cost。

版本迭代

目前Memoize功能的版本迭代有下面的两个

PostgreSQL14支持对嵌套循环连接内部的结果进行缓存

PostgreSQL16对UNION ALL的结果memoize

准备测试用例

在这里创建两个测试表t1和t2表。

create table t1 as 
select i,i % 5 as j
FROM generate_series(1, 1000) as t(i);
create table t2 AS
select i,i % 200 as j
FROM generate_series(1, 1000) as t(i);
--创建索引
CREATE INDEX idx_t1_j ON t1(j);
CREATE INDEX idx_t2_j ON t2(j);
ANALYZE t1;
ANALYZE t2;

下面的测试都是在PostgreSQL16.3版本上执行的。

Memoize执行计划对比

我们先来看看不使用Memoize的执行计划，由于Memoize默认是启用的，因此在PostgreSQL16.3版本中，我们需要先禁用enable_memoize参数。

set enable_memoize=0;

执行SQL语句观察下面的执行计划

testdb=# explain analyze select * from t1 join t2 on t1.j=t2.j;
                                                  QUERY PLAN
---------------------------------------------------------------------------------------------------------------
 Hash Join  (cost=27.50..101.25 rows=5000 width=16) (actual time=0.148..0.645 rows=5000 loops=1)
   Hash Cond: (t1.j = t2.j)
   ->  Seq Scan on t1  (cost=0.00..15.00 rows=1000 width=8) (actual time=0.006..0.057 rows=1000 loops=1)
   ->  Hash  (cost=15.00..15.00 rows=1000 width=8) (actual time=0.136..0.136 rows=1000 loops=1)
         Buckets: 1024  Batches: 1  Memory Usage: 48kB
         ->  Seq Scan on t2  (cost=0.00..15.00 rows=1000 width=8) (actual time=0.003..0.048 rows=1000 loops=1)
 Planning Time: 0.174 ms
 Execution Time: 0.785 ms
(8 rows)

启用enable_memoize参数

set enable_memoize=1;

再执行SQL语句观察下面的执行计划

testdb=# explain analyze select * from t1 join t2 on t1.j=t2.j;
                                                       QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.29..92.37 rows=5000 width=16) (actual time=0.029..1.607 rows=5000 loops=1)
   ->  Seq Scan on t1  (cost=0.00..15.00 rows=1000 width=8) (actual time=0.007..0.103 rows=1000 loops=1)
   ->  Memoize  (cost=0.29..0.41 rows=5 width=8) (actual time=0.000..0.001 rows=5 loops=1000)
         Cache Key: t1.j
         Cache Mode: logical
         Hits: 995  Misses: 5  Evictions: 0  Overflows: 0  Memory Usage: 2kB
         ->  Index Scan using idx_t2_j on t2  (cost=0.28..0.40 rows=5 width=8) (actual time=0.002..0.005 rows=5 loops=5)
               Index Cond: (j = t1.j)
 Planning Time: 0.398 ms
 Execution Time: 1.887 ms
(10 rows)

通过观察上述的执行计划，对于enable_memoize参数关闭和打开前后的执行计划对比，当关闭enable_memoize参数，执行计划使用的是Hash Join，其实这里也可能用到Merge Join，这个在下面的例子中就会遇到；当打开enable_memoize参数，执行计划使用的是Nested Loop，并且在执行计划多了一个Memoize节点。当执行计划的Memoize节点对t1表的j列缓存时，只需要进行5次查找，这是因为t1表的j列只有5个不同的值，同时在缓存中对应5个结果。另外我们也观察到当关闭enable_memoize参数时，执行计划的预估的cost值为101.25；当打开enable_memoize参数时，执行计划的预估的cost值为92.37，相比原来cost也降低不少。

下面通过设置参数，强制执行计划走NL连接

set enable_memoize=0;
set enable_hashjoin =off;
set enable_mergejoin =off;

执行SQL语句观察下面的执行计划

testdb=# explain analyze select * from t1 join t2 on t1.j=t2.j;
                                                      QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.28..463.50 rows=5000 width=16) (actual time=0.021..2.047 rows=5000 loops=1)
   ->  Seq Scan on t1  (cost=0.00..15.00 rows=1000 width=8) (actual time=0.007..0.057 rows=1000 loops=1)
   ->  Index Scan using idx_t2_j on t2  (cost=0.28..0.40 rows=5 width=8) (actual time=0.001..0.002 rows=5 loops=1000)
         Index Cond: (j = t1.j)
 Planning Time: 0.081 ms
 Execution Time: 2.176 ms
(6 rows)

Time: 2.552 ms

可以到看到，在强制走NL表连接且关闭enable_memoize时，cost值为463.50，比上述的两种执行计划都高了很多，但是如果在该执行计划的基础上把enable_memoize打开，该执行计划反而是最优的的执行计划，你有没有感觉到翻转的很快。通过这个测试也可以感觉到，成本计算模型是由各个原因决定，可能包括连接方式、是否使用索引、新特性等等。

对UNION ALL的结果memoize

同样在这里，我们也先禁用enable_memoize参数，看一下在未使用memoize时的执行计划

set enable_memoize=0;

执行SQL语句观察下面的执行计划

explain analyze select * from t1
join (select * from t2 union all select * from t2 ) t on t1.j=t.j;
                                                               QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------
 Merge Join  (cost=0.71..316.78 rows=10000 width=16) (actual time=0.074..1.881 rows=10000 loops=1)
   Merge Cond: (t1.j = t2.j)
   ->  Index Scan using idx_t1_j on t1  (cost=0.15..42.67 rows=1000 width=8) (actual time=0.051..0.184 rows=1000 loops=1)
   ->  Materialize  (cost=0.56..126.61 rows=2000 width=8) (actual time=0.019..0.446 rows=10001 loops=1)
         ->  Merge Append  (cost=0.56..121.61 rows=2000 width=8) (actual time=0.018..0.043 rows=51 loops=1)
               Sort Key: t2.j
               ->  Index Scan using idx_t2_j on t2  (cost=0.28..50.80 rows=1000 width=8) (actual time=0.011..0.023 rows=26 loops=1)
               ->  Index Scan using idx_t2_j on t2 t2_1  (cost=0.28..50.80 rows=1000 width=8) (actual time=0.006..0.014 rows=26 loops=1)
 Planning Time: 0.114 ms
 Execution Time: 2.222 ms
(10 rows)

Time: 2.656 ms

可以通过上面的执行计划，对于UNION ALL后的结果是采用物化（Materialize），最后使用Merge Join对两个表进行关联。

启用enable_memoize参数后

set enable_memoize=1;

再执行SQL语句观察下面的执行计划

testdb=#  explain analyze select * from t1
testdb-#  join (select * from t2 union all select * from t2 ) t on t1.j=t.j;
                                                             QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.29..157.55 rows=10000 width=16) (actual time=0.024..1.719 rows=10000 loops=1)
   ->  Seq Scan on t1  (cost=0.00..15.00 rows=1000 width=8) (actual time=0.008..0.076 rows=1000 loops=1)
   ->  Memoize  (cost=0.29..0.86 rows=10 width=8) (actual time=0.000..0.001 rows=10 loops=1000)
         Cache Key: t1.j
         Cache Mode: logical
         Hits: 995  Misses: 5  Evictions: 0  Overflows: 0  Memory Usage: 3kB
         ->  Append  (cost=0.28..0.85 rows=10 width=8) (actual time=0.003..0.007 rows=10 loops=5)
               ->  Index Scan using idx_t2_j on t2  (cost=0.28..0.40 rows=5 width=8) (actual time=0.002..0.004 rows=5 loops=5)
                     Index Cond: (j = t1.j)
               ->  Index Scan using idx_t2_j on t2 t2_1  (cost=0.28..0.40 rows=5 width=8) (actual time=0.001..0.002 rows=5 loops=5)
                     Index Cond: (j = t1.j)
 Planning Time: 0.136 ms
 Execution Time: 2.056 ms
(13 rows)

Time: 2.531 ms

在PostgreSQL16.3版本上，对于嵌套循环连接中，子查询使用UNION ALL的场景进行了优化，允许对UNION ALL的结果进行缓存。可以从上面的执行计划看到Append节点的上方，新增了Memoize节点，并对t1表的j列进行了缓存，只需要对Append后的结果集进行5次查找。另外从cost值，也从之前的316.78，优化到157.55，提升幅度还是比较明显。从测试时间上看，可能是由于数据的问题，目前看提升并不是很明显。

可能存在的问题

如果对内部节点的一次扫描耗尽了缓存内存，就会发生缓存溢出的情况。当出现缓存溢出时，为了给当前扫描的元组调配空间，因此会清除所有的其他条目，但是如果我们看到溢出的时候，那么单次扫描结果的大小一定超过了work_mem的配置大小。也许你可能会想到需要对work_mem做一些调整，但是对于单个过大的扫描会刷新整个缓存，目前是无法解决该问题，另外也无法实现限制刷新某个百分比的work_mem。

总结

Memoize节点，目前唯一的用途是用在参数化嵌套循环和内部节点之间进行切换，就可以缓存之前查询的结果，这样就可以跳过内部扫描，查询已经缓存的参数值。实际上，在这里Memoize所做的是加速数据的加载，节省了大量的时间和内存，从而提升了SQL的查询效率。

参考

https://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=9bfd2822b

https://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=9eacee2e6

https://blog.jooq.org/postgresql-14s-enable_memoize-for-improved-performance-of-nested-loop-joins/

https://pganalyze.com/blog/5mins-postgres-memoize-speed-up-joins

https://www.modb.pro/db/165147

https://www.modb.pro/db/448413