Hi hackers,
I found a case where Memoize rescans its inner plan even though the
complete result for the requested key is already cached.
When the cache exceeds its memory limit, Memoize removes older entries.
Removing an entry from the hash table can move other entries to
different buckets, including the entry currently being filled.
The code that stores a tuple accounts for this movement and updates
node->entry. However, its caller then marks the entry as complete using
the old local pointer:
```
entry->complete = node->singlerow;
```
This writes to the old bucket and leaves the actual entry marked
incomplete. When the same key is requested again, Memoize discards the
cached tuples and rescans the inner plan.
Example
```
-- Force a nested loop join with Memoize and keep the cache small
enough to trigger evictions
SET enable_hashjoin = off;
SET enable_mergejoin = off;
SET work_mem = '64kB';
SET hash_mem_multiplier = 1;
CREATE TEMP TABLE a AS SELECT i / 2 AS k FROM generate_series(0, 1999) i;
ALTER TABLE a ALTER k SET (n_distinct = 10);
ANALYZE a;
CREATE TEMP TABLE b (k int PRIMARY KEY, v text);
-- Underestimate the number of distinct keys to make the planner choose
Memoize despite the small cache.
INSERT INTO b SELECT i, repeat('x', 1200) FROM generate_series(0, 999) i;
ANALYZE b;
EXPLAIN ANALYZE
SELECT sum(length(v)) FROM a JOIN b USING (k);
--- master
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=102.96..102.97 rows=1 width=8) (actual
time=6.359..6.360 rows=1.00 loops=1)
Buffers: local hit=2554 dirtied=2 written=5
-> Nested Loop (cost=0.29..92.96 rows=2000 width=1204) (actual
time=0.246..2.549 rows=2000.00 loops=1)
Buffers: local hit=2554 dirtied=2 written=5
-> Seq Scan on a (cost=0.00..36.00 rows=2000 width=4)
(actual time=0.172..0.258 rows=2000.00 loops=1)
Buffers: local hit=23 dirtied=1 written=4
-> Memoize (cost=0.29..0.65 rows=1 width=1208) (actual
time=0.001..0.001 rows=1.00 loops=2000)
Cache Key: a.k
Cache Mode: logical
Estimates: capacity=10 distinct keys=10 lookups=2000 hit
percent=99.50%
*Hits: 901 Misses: 1099* Evictions: 950 Overflows: 0 Memory Usage: 65kB
Buffers: local hit=2531 dirtied=1 written=1
-> Index Scan using b_pkey on b (cost=0.28..0.64 rows=1
width=1208) (actual time=0.001..0.001 rows=1.00 loops=1099)
Index Cond: (k = a.k)
Index Searches: 1099
Buffers: local hit=2531 dirtied=1 written=1
Planning:
Buffers: shared hit=37 read=1, local hit=1
Planning Time: 0.211 ms
Execution Time: 6.412 ms
(20 rows)
--- v1 patch
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=102.96..102.97 rows=1 width=8) (actual
time=6.138..6.139 rows=1.00 loops=1)
Buffers: local hit=2356 dirtied=2 written=5
-> Nested Loop (cost=0.29..92.96 rows=2000 width=1204) (actual
time=0.277..2.442 rows=2000.00 loops=1)
Buffers: local hit=2356 dirtied=2 written=5
-> Seq Scan on a (cost=0.00..36.00 rows=2000 width=4)
(actual time=0.192..0.276 rows=2000.00 loops=1)
Buffers: local hit=23 dirtied=1 written=4
-> Memoize (cost=0.29..0.65 rows=1 width=1208) (actual
time=0.001..0.001 rows=1.00 loops=2000)
Cache Key: a.k
Cache Mode: logical
Estimates: capacity=10 distinct keys=10 lookups=2000 hit
percent=99.50%
*Hits: 1000 Misses: 1000* Evictions: 950 Overflows: 0 Memory Usage: 65kB
Buffers: local hit=2333 dirtied=1 written=1
-> Index Scan using b_pkey on b (cost=0.28..0.64 rows=1
width=1208) (actual time=0.001..0.001 rows=1.00 loops=1000)
Index Cond: (k = a.k)
Index Searches: 1000
Buffers: local hit=2333 dirtied=1 written=1
Planning:
Buffers: shared hit=32 read=5, local hit=1
Planning Time: 0.272 ms
Execution Time: 6.222 ms
(20 rows)
```
Hits Misses
Before the fix 901 1099
After the fix 1000 1000
Using the updated pointer fixes this:
- entry->complete = node->singlerow;
+ node->entry->complete = node->singlerow;
Thoughts?
--
Best regards,
Ilia Evdokimov,
Tantor Labs LLC,
https://tantorlabs.com/
From 2031d56bd5fcc5f5217ca8361192982887b620ab Mon Sep 17 00:00:00 2001
From: Evdokimov Ilia <[email protected]>
Date: Wed, 11 Nov 2026 15:12:24 +0300
Subject: [PATCH v1] Fix stale entry pointer in Memoize after cache eviction
Storing a tuple can trigger cache eviction, which may move the current
hash table entry to another bucket. cache_store_tuple() updates
node->entry when this happens, but ExecMemoize() still uses its local
entry pointer to set the complete flag.
Use node->entry instead, so that singlerow entries are correctly marked
complete. Otherwise, subsequent lookups can unnecessarily discard the
cached tuples and rescan the inner plan.
---
src/backend/executor/nodeMemoize.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/src/backend/executor/nodeMemoize.c b/src/backend/executor/nodeMemoize.c
index 74f79260fc3..42287c19514 100644
--- a/src/backend/executor/nodeMemoize.c
+++ b/src/backend/executor/nodeMemoize.c
@@ -868,7 +868,7 @@ ExecMemoize(PlanState *pstate)
* cache lookups to work even when the scan has not been
* executed to completion.
*/
- entry->complete = node->singlerow;
+ node->entry->complete = node->singlerow;
node->mstatus = MEMO_FILLING_CACHE;
}
--
2.53.0
