The Memoize Node in Parameterized Nested Loops #

A nested loop in your plan has a node you do not recognise between it and the inner index scan: Memoize, with Hits: 1204118 Misses: 812. The inner scan ran 812 times instead of 1.2 million. In another plan the same node shows Hits: 9120 Misses: 2400100 Evictions: 2381204 — and the query got slower after upgrading to PostgreSQL 14. Both are the same feature, one working and one not.

Memoize changes the arithmetic of a nested loop, so it belongs alongside the algorithm comparison in merge join vs nested loop.

The Algorithmic Condition #

In a parameterized nested loop, each outer row supplies a value (the parameter) to the inner side — typically an index scan with Index Cond: (x = outer.y). Without a cache, the inner scan runs once per outer row even when outer rows repeat the same value.

Memoize (PostgreSQL 14+) caches inner results keyed on the parameter values. For each outer row:

The planner considers Memoize when the inner side of a nested loop is parameterized, the join operators are hashable, and it estimates that the outer side repeats keys. Its cost model uses the estimated number of distinct outer key values to predict the hit ratio. That estimate comes from n_distinct of the outer join column, which is why Memoize plans are sensitive to the same statistics errors as grouping — see overriding n_distinct on large tables.

The cache budget is work_mem × hash_mem_multiplier. It is also used for lateral subqueries and correlated lookups, which is why Memoize appears under LATERAL join plan shapes.

Memoize between outer rows and the inner scan Outer rows carrying key values flow into a Memoize cache. A key found in the cache is a hit and returns cached rows immediately. A key not found is a miss, which runs the inner index scan once and stores the result. When the cache is full, the least recently used key is evicted. outer rows keys 7, 7, 9, 7, 3 … Memoize cache key → cached inner rows LRU eviction when full budget: hash memory hit return cached rows miss inner index scan, store the benefit is the fraction of outer rows whose key was already seen and still cached

Annotated EXPLAIN Evidence #

A working cache — many order lines, few products:

Nested Loop  (actual time=0.05..612.8 rows=1204930 loops=1)
  ->  Seq Scan on order_lines ol  (actual rows=1204930 loops=1)
  ->  Memoize  (cost=0.43..0.51 rows=1 width=32) (actual time=0.00..0.00 rows=1 loops=1204930)
        Cache Key: ol.product_id
        Cache Mode: logical
        Hits: 1204118  Misses: 812  Evictions: 0  Overflows: 0  Memory Usage: 118kB
        --  Hits/(Hits+Misses) = 99.93%  → 812 inner scans instead of 1.2M
        --  Evictions 0, Memory 118kB    → every distinct key fits
        ->  Index Scan using products_pkey on products p  (actual rows=1 loops=812)
              Index Cond: (id = ol.product_id)

A failing cache — nearly every key distinct:

Nested Loop  (actual time=0.09..21840.2 rows=2409220 loops=1)
  ->  Seq Scan on sessions s  (actual rows=2409220 loops=1)
  ->  Memoize  (cost=0.44..2.10 rows=1 width=48) (actual time=0.01..0.01 rows=1 loops=2409220)
        Cache Key: s.user_id
        Cache Mode: logical
        Hits: 9120  Misses: 2400100  Evictions: 2381204  Overflows: 0  Memory Usage: 131073kB
        --  hit ratio 0.38%               → almost every row rescans anyway
        --  Evictions ≈ Misses, memory at budget → the cache is churning
        --  planner expected ~40,000 distinct user_id values; there were ~2.4M
        ->  Index Scan using users_pkey on users u  (actual rows=1 loops=2400100)

Cache Mode: logical means rows are cached by key equality; binary appears when the key type’s equality is not guaranteed to match its binary representation, and the executor compares bytes instead.

The four Memoize fields to read Four fields are annotated. Cache Key names the repeated parameter. Hits divided by hits plus misses gives the hit ratio. Evictions near misses means churn. Memory Usage at the budget confirms the cache is full. Cache Key: s.user_id the value that must repeat Hits: 9120 Misses: 2400100 hit ratio 0.38% Evictions: 2381204 ≈ Misses → cache churning Memory Usage: 131073kB at work_mem × hash_mem_multiplier

Step-by-Step Resolution #

  1. Find Memoize under a Nested Loop and note its Cache Key.

  2. Compute the hit ratio: Hits / (Hits + Misses). Above ~50% with no evictions, Memoize is saving work. Near zero, it is overhead.

  3. Check Evictions and Memory Usage. Evictions close to Misses with memory at the budget means the cache is too small for the working set of keys.

  4. Compare estimated and actual distinct keys.

    SELECT n_distinct FROM pg_stats WHERE tablename = 'sessions' AND attname = 'user_id';
SELECT count(DISTINCT user_id) FROM sessions WHERE <the query's filters>;

    A large underestimate is why the planner expected hits. Fixing n_distinct often makes the planner drop Memoize — or choose a hash join — on its own.

  5. Test alternatives in a rolled-back transaction.

    BEGIN;
SET LOCAL enable_memoize = off;
EXPLAIN (ANALYZE, BUFFERS) <query>;
ROLLBACK;

BEGIN;
SET LOCAL work_mem = '256MB';   -- a larger cache, if the key set is bounded
EXPLAIN (ANALYZE, BUFFERS) <query>;
ROLLBACK;

  6. Apply the smallest durable fix: correct the statistic, or scope enable_memoize = off to the one statement’s transaction if the estimate cannot be fixed.

Helpful cache versus churning cache Two stacked bars representing all outer rows. For order lines by product, nearly the whole bar is hits and a sliver is misses, with no evictions. For sessions by user, a sliver is hits and nearly the whole bar is misses, most of which caused an eviction. product_id key hits 99.9% user_id key misses 99.6% — most of them also evicted an entry same node type; the number of distinct keys decides whether it pays

Before and After #

-- BEFORE: churning Memoize on sessions.user_id
Memoize  Hits: 9120  Misses: 2400100  Evictions: 2381204          Execution Time: 21902.4 ms

-- AFTER: n_distinct override on sessions.user_id, ANALYZE → planner chose a hash join
Hash Join  Hash Cond: (s.user_id = u.id)  Batches: 1                Execution Time: 3102.7 ms

Why Memoize is costed as cheap even when it is not #

The planner estimates a hit ratio from two numbers: how many times the inner side will be called (the outer row estimate) and how many distinct keys those calls will carry (from n_distinct of the outer join column, scaled to the outer row estimate). If it expects 2.4 million calls over 40,000 distinct keys, and the cache can hold all 40,000 entries, it predicts that 98% of calls are hits and costs the inner scan at 2% of its uncached price. The nested loop then looks far cheaper than a hash join that would need to build a table over the whole users relation.

Every input to that calculation can be wrong in the direction that favours Memoize. An underestimated n_distinct inflates the predicted hit ratio. An underestimated inner result width makes more entries appear to fit in memory. A filter on the outer side that happens to select rows with unusually diverse keys breaks the assumption that distinct keys scale with rows. The executor does not revisit the decision, so the cache churns for the entire execution.

Memoize under LATERAL and correlated subqueries #

The same node appears above the inner side of a LATERAL subquery, and correlated subqueries that the planner pulls up into parameterized joins can use it too. The hit ratio logic is identical: a lateral “top three orders per customer” query over a list of customers with repeats benefits, while the same query over a list of unique customers gains nothing. When Cache Key lists several columns, all of them must repeat together for a hit — a key of (customer_id, region) is less cacheable than customer_id alone if regions vary. Removing an unnecessary correlation column from a lateral subquery can turn a churning cache into an effective one without any other change.

Common Pitfalls #

Assuming Memoize is always a win. It adds hashing and bookkeeping per outer row. Diagnostic signal: a hit ratio in single digits. Fix: correct distinct-key estimates or disable it for that statement.

Reading per-loop time as cheap. actual time=0.01 with loops=2409220 is 24 seconds. Diagnostic signal: large loops on the Memoize and its child. Fix: multiply by loops before judging.

Disabling Memoize globally after one bad plan. Many plans benefit substantially. Diagnostic signal: other lookups-by-foreign-key slowing down after the change. Fix: scope enable_memoize = off with SET LOCAL.

Overflows on large inner results. A key whose inner result exceeds the cache cannot be stored and always rescans. Diagnostic signal: Overflows above zero. Fix: the inner side returns too many rows per key for a nested loop; a hash or merge join is likely the better shape.

Frequently Asked Questions #

What does the Memoize node do? It caches the inner rows of a parameterized nested loop for each distinct parameter value, so repeated outer values skip the rescan. Added in PostgreSQL 14, controlled by enable_memoize.

How do I know whether Memoize is helping? Compare Hits with Misses. A high hit ratio with few Evictions means it saves inner scans; many evictions or overflows mean it is mostly overhead.

How much memory can Memoize use? Up to work_mem × hash_mem_multiplier. When full, it evicts least recently used entries.

Up: Merge Join vs Nested Loop