postgres.git / summary / log / commit / refs
commit de7d7d4df80acceca1195d549bd2887d5bc8ab26
Author: Richard Guo <rguo@postgresql.org>
Date: Mon Nov 02 01:33:24 2026 +0000
First released in: 14.25, 15.20, 16.16, 17.12, 18.7, 19.0
Fix wrong results from Memoize with a Param inside a cache key
ExecReScanMemoize() purges the whole cache only when a Param changes
which is not part of the cache key; a change to a cache-key Param is
assumed to be handled by looking up a different cache entry. To that
end, create_memoize_plan() put every Param appearing in the cache key
expressions into keyparamids. That assumption holds only when the
cache key values determine the Param's value.
It fails for an upper-level Param which is buried inside a larger
cache-key expression and also appears elsewhere in the subplan. With
a cache key of "t2.hundred + t0.ten" and a filter "t1.twenty =
t0.ten", different (t2.hundred, t0.ten) pairs produce the same
cache-key value while the filter selects different rows, so one cache
entry wrongly serves both. Since t0.ten was included in keyparamids,
the cache was never purged when it changed.
Also, pull_paramids() collected PARAM_EXTERN Params too, whose numbers
are unrelated to those of PARAM_EXEC Params. An external Param in a
cache key could therefore keep a change to an unrelated executor Param
from purging the cache.
To fix, put into keyparamids only the Params whose values the cache
keys determine. These are the nestloop Params which replace the outer
rel's Vars in the cache keys, as the inner scan can only reference the
outer rel through the cache keys, and, in binary mode only, a Param
which is a cache key by itself. In logical mode the hash equality
operator may not distinguish values that affect the results
differently. Any other Param now purges the cache when it changes.
Also make pull_paramids() collect PARAM_EXEC Params only.
Purging alone would empty the cache on every rescan of the enclosing
plan whenever a buried Param changes, even when the Param is used
nowhere else and the old code was correct and kept its cache entries
across rescans. So also make each buried Param a cache key by itself,
which puts Memoize into binary mode, so that cache entries survive
across rescans with the same Param value. A buried Param whose type
can't be hashed is left to the purging, rather than giving up on
Memoize.
Back-patch to all supported branches.
Reported-by: Jacob Brazeal <jacob.brazeal@gmail.com>
Author: Richard Guo <guofenglinux@gmail.com>
Reviewed-by: David Rowley <dgrowleyml@gmail.com>
Reviewed-by: Yilin Zhang <jiezhilove@126.com>
Discussion: https://postgr.es/m/CA+COZaAHZT7T2G2F0-drdQB+StWJxOzqeDxp=ESp+YUiy-kOaQ@mail.gmail.com
Backpatch-through: 14
src/backend/optimizer/path/joinpath.c | 97 ++++++++++++++++++++------
src/backend/optimizer/plan/createplan.c | 27 +++++++-
src/backend/optimizer/util/clauses.c | 6 +-
src/include/nodes/execnodes.h | 3 +-
src/include/nodes/plannodes.h | 3 +-
src/test/regress/expected/memoize.out | 116 ++++++++++++++++++++++++++++++++
src/test/regress/sql/memoize.sql | 59 ++++++++++++++++
7 files changed, 286 insertions(+), 25 deletions(-)
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 429257fe622..38bf95540a6 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -95,6 +95,9 @@ static void generate_mergejoin_paths(PlannerInfo *root,
Path *inner_cheapest_total,
List *merge_pathkeys,
bool is_partial);
+static bool pull_exec_params_walker(Node *node, List **params);
+static bool memoize_add_cache_key(Node *expr, List **param_exprs,
+ List **operators, bool *binary_mode);
/*
@@ -400,6 +403,7 @@ paraminfo_get_equal_hashops(PlannerInfo *root, ParamPathInfo *param_info,
bool *binary_mode)
{
+ List *params;
ListCell *lc;
*param_exprs = NIL;
@@ -458,7 +462,6 @@ paraminfo_get_equal_hashops(PlannerInfo *root, ParamPathInfo *param_info,
foreach(lc, innerrel->lateral_vars)
{
Node *expr = (Node *) lfirst(lc);
- TypeCacheEntry *typentry;
/* Reject if there are any volatile functions */
if (contain_volatile_functions(expr))
@@ -468,36 +471,92 @@ paraminfo_get_equal_hashops(PlannerInfo *root, ParamPathInfo *param_info,
return false;
}
- typentry = lookup_type_cache(exprType(expr),
- TYPECACHE_HASH_PROC | TYPECACHE_EQ_OPR);
-
- /* can't use a memoize node without a valid hash equals operator */
- if (!OidIsValid(typentry->hash_proc) || !OidIsValid(typentry->eq_opr))
+ if (!memoize_add_cache_key(expr, param_exprs, operators, binary_mode))
{
list_free(*operators);
list_free(*param_exprs);
return false;
}
+ }
- *operators = lappend_oid(*operators, typentry->eq_opr);
- *param_exprs = lappend(*param_exprs, expr);
+ /*
+ * A Param buried inside a larger cache key expression isn't determined by
+ * the key's value, so create_memoize_plan() arranges for the cache to be
+ * purged whenever it changes, which commonly happens on every rescan of
+ * the enclosing plan. We're better off making a cache key of the Param
+ * by itself so that the cached results survive. This is only an
+ * optimization, so we needn't refuse to memoize when one isn't hashable.
+ */
+ params = NIL;
+ (void) pull_exec_params_walker((Node *) *param_exprs, ¶ms);
- /*
- * We must go into binary mode as we don't have too much of an idea of
- * how these lateral Vars are being used. See comment above when we
- * set *binary_mode for the non-lateral Var case. This could be
- * relaxed a bit if we had the RestrictInfos and knew the operators
- * being used, however for cases like Vars that are arguments to
- * functions we must operate in binary mode as we don't have
- * visibility into what the function is doing with the Vars.
- */
- *binary_mode = true;
- }
+ foreach(lc, params)
+ (void) memoize_add_cache_key((Node *) lfirst(lc), param_exprs,
+ operators, binary_mode);
/* We're okay to use memoize */
return true;
}
+/*
+ * memoize_add_cache_key
+ * Add 'expr' to the Memoize cache keys collected in *param_exprs and
+ * *operators, unless it's a cache key already.
+ *
+ * Returns false if 'expr' has a type which Memoize can't hash. It's up to the
+ * caller to decide whether that's fatal.
+ */
+static bool
+memoize_add_cache_key(Node *expr, List **param_exprs, List **operators,
+ bool *binary_mode)
+{
+ TypeCacheEntry *typentry;
+
+ typentry = lookup_type_cache(exprType(expr),
+ TYPECACHE_HASH_PROC | TYPECACHE_EQ_OPR);
+
+ /* can't use memoize without a valid hash proc and equals operator */
+ if (!OidIsValid(typentry->hash_proc) || !OidIsValid(typentry->eq_opr))
+ return false;
+
+ *operators = lappend_oid(*operators, typentry->eq_opr);
+ *param_exprs = lappend(*param_exprs, expr);
+
+ /*
+ * We must go into binary mode as we don't have too much of an idea of how
+ * 'expr' is being used. See the comment above where we set *binary_mode
+ * for the join clause case. This could be relaxed a bit if we knew the
+ * operators being used, however for cases like Vars that are arguments to
+ * functions, or Params appearing in quals we've not examined, we must
+ * operate in binary mode as we've no visibility into what's done with the
+ * value.
+ */
+ *binary_mode = true;
+
+ return true;
+}
+
+/*
+ * pull_exec_params_walker
+ * Collect the distinct PARAM_EXEC Params found in 'node' into *params.
+ */
+static bool
+pull_exec_params_walker(Node *node, List **params)
+{
+ if (node == NULL)
+ return false;
+ if (IsA(node, Param))
+ {
+ Param *param = (Param *) node;
+
+ if (param->paramkind == PARAM_EXEC &&
+ !list_member(*params, param))
+ *params = lappend(*params, param);
+ return false;
+ }
+ return expression_tree_walker(node, pull_exec_params_walker, params);
+}
+
/*
* get_memoize_path
* If possible, make and return a Memoize path atop of 'inner_path'.
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index fb824079201..f0637428947 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -1647,7 +1647,32 @@ create_memoize_plan(PlannerInfo *root, MemoizePath *best_path, int flags)
i++;
}
- keyparamids = pull_paramids((Expr *) param_exprs);
+ /*
+ * A Param may be left out of the cache purge on rescan only if its value
+ * is determined by the cache keys. That holds for the nestloop Params
+ * just introduced, as the inner scan's every reference to the outer rels
+ * is a cache key. It doesn't hold for an upper-level Param buried inside
+ * a larger key expression, as two Param values can produce the same key
+ * value while affecting the results elsewhere, say in a base qual.
+ */
+ keyparamids = bms_del_members(pull_paramids((Expr *) param_exprs),
+ pull_paramids((Expr *) best_path->param_exprs));
+
+ /*
+ * A Param which is a cache key by itself is determined by the keys too,
+ * but only in binary mode, as in logical mode the hash equality operator
+ * may not distinguish values that affect the results differently.
+ */
+ if (best_path->binary_mode)
+ {
+ foreach(lc, best_path->param_exprs)
+ {
+ Param *param = (Param *) lfirst(lc);
+
+ if (IsA(param, Param) && param->paramkind == PARAM_EXEC)
+ keyparamids = bms_add_member(keyparamids, param->paramid);
+ }
+ }
plan = make_memoize(subplan, operators, collations, param_exprs,
best_path->singlerow, best_path->binary_mode,
diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c
index 3c44924e2d7..790264107c0 100644
--- a/src/backend/optimizer/util/clauses.c
+++ b/src/backend/optimizer/util/clauses.c
@@ -5263,7 +5263,8 @@ substitute_actual_srf_parameters_mutator(Node *node,
/*
* pull_paramids
- * Returns a Bitmapset containing the paramids of all Params in 'expr'.
+ * Returns a Bitmapset containing the paramids of all PARAM_EXEC Params
+ * in 'expr'.
*/
Bitmapset *
pull_paramids(Expr *expr)
@@ -5284,7 +5285,8 @@ pull_paramids_walker(Node *node, Bitmapset **context)
{
Param *param = (Param *)node;
- *context = bms_add_member(*context, param->paramid);
+ if (param->paramkind == PARAM_EXEC)
+ *context = bms_add_member(*context, param->paramid);
return false;
}
return expression_tree_walker(node, pull_paramids_walker,
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 801d7630e9d..92a41c3459c 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -2160,8 +2160,7 @@ typedef struct MemoizeState
* by bit, false when using hash equality ops */
MemoizeInstrumentation stats; /* execution statistics */
SharedMemoizeInfo *shared_info; /* statistics for parallel workers */
- Bitmapset *keyparamids; /* Param->paramids of expressions belonging to
- * param_exprs */
+ Bitmapset *keyparamids; /* copy of Memoize.keyparamids */
} MemoizeState;
/* ----------------
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index 1c9357f6a77..f6bbfa1c37c 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -818,7 +818,8 @@ typedef struct Memoize
uint32 est_entries; /* The maximum number of entries that the
* planner expects will fit in the cache, or 0
* if unknown */
- Bitmapset *keyparamids; /* paramids from param_exprs */
+ Bitmapset *keyparamids; /* paramids which needn't purge the cache; see
+ * create_memoize_plan() */
} Memoize;
/* ----------------
diff --git a/src/test/regress/expected/memoize.out b/src/test/regress/expected/memoize.out
index 8184c95749d..bd742b2dcef 100644
--- a/src/test/regress/expected/memoize.out
+++ b/src/test/regress/expected/memoize.out
@@ -305,6 +305,122 @@ WHERE unique1 < 3
2
(1 row)
+-- Ensure a Param which is buried inside a larger cache key expression is made
+-- a cache key by itself too.
+-- Ensure we get a Memoize plan with both cache keys
+EXPLAIN (COSTS OFF)
+SELECT sum(c) FROM (
+ SELECT (SELECT count(*) FROM tenk1 t1
+ INNER JOIN tenk1 t2 ON t1.unique1 = t2.hundred + t0.ten
+ WHERE t1.twenty = t0.ten) AS c
+ FROM tenk1 t0 WHERE t0.unique1 < 2) s;
+ QUERY PLAN
+---------------------------------------------------------------------------
+ Aggregate
+ -> Index Scan using tenk1_unique1 on tenk1 t0
+ Index Cond: (unique1 < 2)
+ SubPlan 1
+ -> Aggregate
+ -> Nested Loop
+ -> Index Only Scan using tenk1_hundred on tenk1 t2
+ -> Memoize
+ Cache Key: (t2.hundred + t0.ten), t0.ten
+ Cache Mode: binary
+ -> Index Scan using tenk1_unique1 on tenk1 t1
+ Index Cond: (unique1 = (t2.hundred + t0.ten))
+ Filter: (twenty = t0.ten)
+(13 rows)
+
+-- Ensure the above query returns the correct result
+SELECT sum(c) FROM (
+ SELECT (SELECT count(*) FROM tenk1 t1
+ INNER JOIN tenk1 t2 ON t1.unique1 = t2.hundred + t0.ten
+ WHERE t1.twenty = t0.ten) AS c
+ FROM tenk1 t0 WHERE t0.unique1 < 2) s;
+ sum
+------
+ 1000
+(1 row)
+
+-- Ensure a buried Param which can't be made a cache key, here of type point,
+-- still purges the cache when it changes.
+-- Ensure we get a Memoize plan without the Param as a cache key
+EXPLAIN (COSTS OFF)
+SELECT sum(c) FROM (
+ SELECT (SELECT count(*) FROM tenk1 t1
+ INNER JOIN tenk1 t2
+ ON t1.unique1 = t2.hundred + (t0.p <-> point '(0,0)')::int
+ WHERE t1.twenty = (t0.p <-> point '(0,0)')::int) AS c
+ FROM (VALUES (point '(0,0)'), (point '(1,0)')) t0(p)) s;
+ QUERY PLAN
+-----------------------------------------------------------------------------------------------------------------------
+ Aggregate
+ -> Values Scan on "*VALUES*"
+ SubPlan 1
+ -> Aggregate
+ -> Nested Loop
+ -> Index Only Scan using tenk1_hundred on tenk1 t2
+ -> Memoize
+ Cache Key: (t2.hundred + (("*VALUES*".column1 <-> '(0,0)'::point))::integer)
+ Cache Mode: logical
+ -> Index Scan using tenk1_unique1 on tenk1 t1
+ Index Cond: (unique1 = (t2.hundred + (("*VALUES*".column1 <-> '(0,0)'::point))::integer))
+ Filter: (twenty = (("*VALUES*".column1 <-> '(0,0)'::point))::integer)
+(12 rows)
+
+-- Ensure the above query returns the correct result
+SELECT sum(c) FROM (
+ SELECT (SELECT count(*) FROM tenk1 t1
+ INNER JOIN tenk1 t2
+ ON t1.unique1 = t2.hundred + (t0.p <-> point '(0,0)')::int
+ WHERE t1.twenty = (t0.p <-> point '(0,0)')::int) AS c
+ FROM (VALUES (point '(0,0)'), (point '(1,0)')) t0(p)) s;
+ sum
+------
+ 1000
+(1 row)
+
+-- Ensure an external Param inside a cache key isn't mistaken for the executor
+-- Param of the same number. The initplan takes executor Param 0, so the
+-- point Param gets number 1, the same as $1.
+SET plan_cache_mode TO force_generic_plan;
+PREPARE memoize_extern_param(int) AS
+SELECT sum(c) FROM (
+ SELECT (SELECT sum(t1.unique1) FROM tenk1 t1
+ INNER JOIN tenk1 t2 ON t1.unique1 = t2.hundred + $1
+ AND t2.hundred >= (SELECT 0)
+ WHERE t1.twenty = (t0.p <-> point '(0,0)')::int) AS c
+ FROM (VALUES (point '(0,0)'), (point '(1,0)')) t0(p)) s;
+-- Ensure we get a Memoize plan with the external Param in the cache key
+EXPLAIN (COSTS OFF) EXECUTE memoize_extern_param(0);
+ QUERY PLAN
+---------------------------------------------------------------------------------------------------
+ Aggregate
+ -> Values Scan on "*VALUES*"
+ SubPlan 2
+ -> Aggregate
+ InitPlan 1 (returns $0)
+ -> Result
+ -> Nested Loop
+ -> Index Only Scan using tenk1_hundred on tenk1 t2
+ Index Cond: (hundred >= $0)
+ -> Memoize
+ Cache Key: (t2.hundred + $1)
+ Cache Mode: logical
+ -> Index Scan using tenk1_unique1 on tenk1 t1
+ Index Cond: (unique1 = (t2.hundred + $1))
+ Filter: (twenty = (("*VALUES*".column1 <-> '(0,0)'::point))::integer)
+(15 rows)
+
+-- Ensure the above query returns the correct result
+EXECUTE memoize_extern_param(0);
+ sum
+-------
+ 40500
+(1 row)
+
+DEALLOCATE memoize_extern_param;
+RESET plan_cache_mode;
RESET enable_seqscan;
RESET enable_mergejoin;
RESET work_mem;
diff --git a/src/test/regress/sql/memoize.sql b/src/test/regress/sql/memoize.sql
index 5bd888e2b3d..c9cff1f01d7 100644
--- a/src/test/regress/sql/memoize.sql
+++ b/src/test/regress/sql/memoize.sql
@@ -165,6 +165,65 @@ WHERE unique1 < 3
INNER JOIN tenk1 t2 ON t1.unique1 = t2.hundred
WHERE t0.ten = t1.twenty AND t0.two <> t2.four OFFSET 0);
+-- Ensure a Param which is buried inside a larger cache key expression is made
+-- a cache key by itself too.
+
+-- Ensure we get a Memoize plan with both cache keys
+EXPLAIN (COSTS OFF)
+SELECT sum(c) FROM (
+ SELECT (SELECT count(*) FROM tenk1 t1
+ INNER JOIN tenk1 t2 ON t1.unique1 = t2.hundred + t0.ten
+ WHERE t1.twenty = t0.ten) AS c
+ FROM tenk1 t0 WHERE t0.unique1 < 2) s;
+
+-- Ensure the above query returns the correct result
+SELECT sum(c) FROM (
+ SELECT (SELECT count(*) FROM tenk1 t1
+ INNER JOIN tenk1 t2 ON t1.unique1 = t2.hundred + t0.ten
+ WHERE t1.twenty = t0.ten) AS c
+ FROM tenk1 t0 WHERE t0.unique1 < 2) s;
+
+-- Ensure a buried Param which can't be made a cache key, here of type point,
+-- still purges the cache when it changes.
+
+-- Ensure we get a Memoize plan without the Param as a cache key
+EXPLAIN (COSTS OFF)
+SELECT sum(c) FROM (
+ SELECT (SELECT count(*) FROM tenk1 t1
+ INNER JOIN tenk1 t2
+ ON t1.unique1 = t2.hundred + (t0.p <-> point '(0,0)')::int
+ WHERE t1.twenty = (t0.p <-> point '(0,0)')::int) AS c
+ FROM (VALUES (point '(0,0)'), (point '(1,0)')) t0(p)) s;
+
+-- Ensure the above query returns the correct result
+SELECT sum(c) FROM (
+ SELECT (SELECT count(*) FROM tenk1 t1
+ INNER JOIN tenk1 t2
+ ON t1.unique1 = t2.hundred + (t0.p <-> point '(0,0)')::int
+ WHERE t1.twenty = (t0.p <-> point '(0,0)')::int) AS c
+ FROM (VALUES (point '(0,0)'), (point '(1,0)')) t0(p)) s;
+
+-- Ensure an external Param inside a cache key isn't mistaken for the executor
+-- Param of the same number. The initplan takes executor Param 0, so the
+-- point Param gets number 1, the same as $1.
+SET plan_cache_mode TO force_generic_plan;
+PREPARE memoize_extern_param(int) AS
+SELECT sum(c) FROM (
+ SELECT (SELECT sum(t1.unique1) FROM tenk1 t1
+ INNER JOIN tenk1 t2 ON t1.unique1 = t2.hundred + $1
+ AND t2.hundred >= (SELECT 0)
+ WHERE t1.twenty = (t0.p <-> point '(0,0)')::int) AS c
+ FROM (VALUES (point '(0,0)'), (point '(1,0)')) t0(p)) s;
+
+-- Ensure we get a Memoize plan with the external Param in the cache key
+EXPLAIN (COSTS OFF) EXECUTE memoize_extern_param(0);
+
+-- Ensure the above query returns the correct result
+EXECUTE memoize_extern_param(0);
+
+DEALLOCATE memoize_extern_param;
+RESET plan_cache_mode;
+
RESET enable_seqscan;
RESET enable_mergejoin;
RESET work_mem;
[parent: 35848657c67d]