I realized that I uploaded my diff file with a small mistake - sorry
about that. I've corrected it with this message so your tests can pass
in the CI.
On 31.03.2025 05:33, Alena Rybakina wrote:
Hi!
On 21.03.2025 18:56, Andrei Lepikhov wrote:
On 20/3/2025 07:02, David Rowley wrote:
On Thu, 20 Mar 2025 at 06:16, Andrei Lepikhov <lepi...@gmail.com>
wrote:
How can we be sure that semi or anti-join needs only one tuple? I
think
it would be enough to control the absence of join clauses and
filters in
the join. Unfortunately, we only have such a guarantee in the plan
creation stage (maybe even setrefs.c). So, it seems we need to
invent an
approach like AlternativeSubplan.
I suggest looking at what 9e215378d did. You might be able to also
allow semi and anti-joins providing the cache keys cover the entire
join condition. I think this might be safe as Nested Loop will only
ask its inner subnode for the first match before skipping to the next
outer row and with anti-join, there's no reason to look for additional
rows after the first. Semi-join and unique joins do the same thing in
nodeNestloop.c. To save doing additional checks at run-time, the code
does:
Thank you for the clue! I almost took the wrong direction.
I have attached the new patch, which includes corrected comments for
better clarification of the changes, as well as some additional tests.
I now feel much more confident about this version since I have
resolved that concern.
I reviewed your patch and made a couple of suggestions.
The first change is related to your comment (and the one before it). I
fixed some grammar issues and simplified the wording to make it
clearer and easier to understand.
The second change involves adding an Assert when generating the
Memoize path. Based on the existing comment and the surrounding logic
(shown below),
I believe it's worth asserting that both inner_unique and single_mode
are not true at the same time — just as a safety check.
/*
* We may do this for SEMI or ANTI joins when they need only one tuple from
* the inner side to produce the result. Following if condition checks that
* rule.
*
* XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
* = true. Should we? See add_paths_to_joinrel()
*/
if(!extra->inner_unique&& (jointype== JOIN_SEMI||
jointype== JOIN_ANTI))
single_mode= true;
--
Regards,
Alena Rybakina
Postgres Professional
diff --git a/src/backend/optimizer/path/joinpath.c
b/src/backend/optimizer/path/joinpath.c
index c75408f552b..252cb712943 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -728,14 +728,16 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
single_mode = true;
/*
- * Memoize normally marks cache entries as complete when it runs out of
- * tuples to read from its subplan. However, with unique joins, Nested
- * Loop will skip to the next outer tuple after finding the first
matching
- * inner tuple. Another case is a semi or anti join. If number of join
- * clauses, pushed to the inner as parameterised filter no less than the
- * number of join clauses, that means all the clauses have been pushed
to
- * the inner and any tuple coming from the inner side will be
successfully
- * used to build the join result.
+ * Normally, memoize marks cache entries as complete when it exhausts
+ * all tuples from its subplan. However, in unique joins, Nested Loop
+ * will skip to the next outer tuple after finding the first matching
+ * inner tuple.
+ * Another case is a SEMI or ANTI joins. If the number of join clauses,
+ * pushed to the inner as parameterised filter is equal to or greater
+ * than the total number of join clauses. This implies that all relevant
+ * join conditions have been applied on the inner side, so any returned
+ * inner tuple will be guaranteed to satisfy the join condition, making
+ * it safe to memoize.
* This means that we may not read the inner side of the
* join to completion which leaves no opportunity to mark the cache
entry
* as complete. To work around that, when the join is unique we
@@ -808,6 +810,8 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
&hash_operators,
&binary_mode))
{
+ Assert(!(extra->inner_unique && single_mode));
+
return (Path *) create_memoize_path(root,
innerrel,
inner_path,
From c5897e31d2a95de04fa0e641aeff43f3118bcced Mon Sep 17 00:00:00 2001
From: "Andrei V. Lepikhov" <lepi...@gmail.com>
Date: Fri, 21 Mar 2025 15:55:40 +0100
Subject: [PATCH v1] Memoise the inner of SEMI- and ANTI-join.
To produce the result of semi-join or anti-join, we only need one tuple from
the parameterised inner. The Postgres core already includes Memoize's
single_row mode for the case when it is proved that inner returns only a single
value. Thus, implementing similar logic for semi-joins and anti-joins is
quite doable.
Usually, these types of join need only single tuple from the inner to produce
result for each outer tuple. But if after pushing parameterised clauses down to
the inner the NestLoop still have some join clauses or filters, it may reject
some inner tuples during execution and call the inner more than once. To prevent
that we check that all the restrictions have been pushed to the inner.
---
src/backend/commands/explain.c | 4 +
src/backend/optimizer/path/costsize.c | 2 +-
src/backend/optimizer/path/joinpath.c | 21 +++--
src/backend/optimizer/util/pathnode.c | 2 +-
src/test/regress/expected/join.out | 3 +-
src/test/regress/expected/memoize.out | 102 ++++++++++++++++++++++++
src/test/regress/expected/subselect.out | 3 +-
src/test/regress/sql/memoize.sql | 49 ++++++++++++
8 files changed, 174 insertions(+), 12 deletions(-)
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index 391b34a2af2..1b4b3b740ab 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -3628,6 +3628,10 @@ show_memoize_info(MemoizeState *mstate, List *ancestors, ExplainState *es)
ExplainPropertyText("Cache Key", keystr.data, es);
ExplainPropertyText("Cache Mode", mstate->binary_mode ? "binary" : "logical", es);
+ /* Report only in the single mode case to not break current tests */
+ if (mstate->singlerow)
+ ExplainPropertyText("Store Mode", "singlerow", es);
+
pfree(keystr.data);
if (!es->analyze)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index f6f77b8fe19..941ba6e1d49 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -2545,7 +2545,7 @@ cost_memoize_rescan(PlannerInfo *root, MemoizePath *mpath,
ListCell *lc;
Cost input_startup_cost = mpath->subpath->startup_cost;
Cost input_total_cost = mpath->subpath->total_cost;
- double tuples = mpath->subpath->rows;
+ double tuples = mpath->singlerow ? 1 : mpath->subpath->rows;
double calls = mpath->calls;
int width = mpath->subpath->pathtarget->width;
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 18891ce9156..c75408f552b 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -682,6 +682,7 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
ListCell *lc;
bool binary_mode;
List *ph_lateral_vars;
+ bool single_mode = false;
/* Obviously not if it's disabled */
if (!enable_memoize)
@@ -715,23 +716,27 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
return NULL;
/*
- * Currently we don't do this for SEMI and ANTI joins unless they're
- * marked as inner_unique. This is because nested loop SEMI/ANTI joins
- * don't scan the inner node to completion, which will mean memoize cannot
- * mark the cache entry as complete.
+ * We may do this for SEMI or ANTI joins when they need only one tuple from
+ * the inner side to produce the result. Following if condition checks that
+ * rule.
*
* XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
* = true. Should we? See add_paths_to_joinrel()
*/
if (!extra->inner_unique && (jointype == JOIN_SEMI ||
jointype == JOIN_ANTI))
- return NULL;
+ single_mode = true;
/*
* Memoize normally marks cache entries as complete when it runs out of
* tuples to read from its subplan. However, with unique joins, Nested
* Loop will skip to the next outer tuple after finding the first matching
- * inner tuple. This means that we may not read the inner side of the
+ * inner tuple. Another case is a semi or anti join. If number of join
+ * clauses, pushed to the inner as parameterised filter no less than the
+ * number of join clauses, that means all the clauses have been pushed to
+ * the inner and any tuple coming from the inner side will be successfully
+ * used to build the join result.
+ * This means that we may not read the inner side of the
* join to completion which leaves no opportunity to mark the cache entry
* as complete. To work around that, when the join is unique we
* automatically mark cache entries as complete after fetching the first
@@ -753,7 +758,7 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
* the inner scan's filter instead of the join filter. Maybe it's worth
* considering doing that?
*/
- if (extra->inner_unique &&
+ if ((extra->inner_unique || single_mode) &&
(inner_path->param_info == NULL ||
bms_num_members(inner_path->param_info->ppi_serials) <
list_length(extra->restrictlist)))
@@ -808,7 +813,7 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
inner_path,
param_exprs,
hash_operators,
- extra->inner_unique,
+ extra->inner_unique || single_mode,
binary_mode,
outer_path->rows);
}
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 93e73cb44db..9b4c0f96193 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -1707,7 +1707,7 @@ create_memoize_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
*/
pathnode->path.startup_cost = subpath->startup_cost + cpu_tuple_cost;
pathnode->path.total_cost = subpath->total_cost + cpu_tuple_cost;
- pathnode->path.rows = subpath->rows;
+ pathnode->path.rows = (pathnode->singlerow) ? 1 : subpath->rows;
return pathnode;
}
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index a57bb18c24f..e8293c3c87d 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -6469,10 +6469,11 @@ select * from sj t1
-> Memoize
Cache Key: t1.a, t1.b
Cache Mode: binary
+ Store Mode: singlerow
-> Sample Scan on sj
Sampling: system (t1.b)
Filter: (t1.a = a)
-(8 rows)
+(9 rows)
-- Ensure that SJE does not form a self-referential lateral dependency
explain (costs off)
diff --git a/src/test/regress/expected/memoize.out b/src/test/regress/expected/memoize.out
index 38dfaf021c9..3ad473b211d 100644
--- a/src/test/regress/expected/memoize.out
+++ b/src/test/regress/expected/memoize.out
@@ -500,3 +500,105 @@ RESET max_parallel_workers_per_gather;
RESET parallel_tuple_cost;
RESET parallel_setup_cost;
RESET min_parallel_table_scan_size;
+--
+-- Tests on Memoize under SEMI and ANTI joins.
+--
+CREATE TABLE mem_semi_inner_a (x int, z int);
+CREATE TABLE mem_semi_inner_b (x int, y int);
+CREATE TABLE mem_semi_inner_c (x int, y int, z int);
+INSERT INTO mem_semi_inner_a (x,z)
+ (SELECT value%2, -42 FROM generate_series(1,10) AS value);
+INSERT INTO mem_semi_inner_b (x,y)
+ (SELECT value%5, -value%5-1 FROM generate_series(1,10) AS value);
+INSERT INTO mem_semi_inner_c (x,y,z)
+ (SELECT value%50, value, -42 FROM generate_series(1,100) AS value);
+CREATE INDEX ON mem_semi_inner_b(x);
+CREATE INDEX ON mem_semi_inner_c(x,z);
+VACUUM ANALYZE mem_semi_inner_a,mem_semi_inner_b,mem_semi_inner_c;
+-- Force NestLoop and IndexScan. Hope, the Memoize node win the cost
+-- competition on the inner c table scan.
+SET enable_hashjoin = 'off';
+SET enable_mergejoin = 'off';
+SET enable_seqscan = 'off';
+-- Primitive example of semi and anti join caching the inner's result
+EXPLAIN (COSTS OFF)
+SELECT a.x FROM mem_semi_inner_a a
+WHERE EXISTS (SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x);
+ QUERY PLAN
+----------------------------------------------------------------------------------
+ Nested Loop Semi Join
+ -> Seq Scan on mem_semi_inner_a a
+ Disabled: true
+ -> Memoize
+ Cache Key: a.x
+ Cache Mode: logical
+ Store Mode: singlerow
+ -> Index Only Scan using mem_semi_inner_c_x_z_idx on mem_semi_inner_c c
+ Index Cond: (x = a.x)
+(9 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT a.x FROM mem_semi_inner_a a
+WHERE NOT EXISTS (SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x);
+ QUERY PLAN
+----------------------------------------------------------------------------------
+ Nested Loop Anti Join
+ -> Seq Scan on mem_semi_inner_a a
+ Disabled: true
+ -> Memoize
+ Cache Key: a.x
+ Cache Mode: logical
+ Store Mode: singlerow
+ -> Index Only Scan using mem_semi_inner_c_x_z_idx on mem_semi_inner_c c
+ Index Cond: (x = a.x)
+(9 rows)
+
+-- Check the query plans contain the Memoize node over the "Scan b" operator
+-- and does not contain memoize over "Scan c".
+EXPLAIN (COSTS OFF)
+SELECT a.x, b.x FROM mem_semi_inner_a a
+ LEFT JOIN mem_semi_inner_b b ON (a.x=b.x)
+WHERE EXISTS (
+ SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x AND c.y=b.y AND c.z=a.z);
+ QUERY PLAN
+---------------------------------------------------------------------------------
+ Nested Loop Semi Join
+ Join Filter: ((c.x = a.x) AND (c.z = a.z))
+ -> Nested Loop
+ -> Seq Scan on mem_semi_inner_a a
+ Disabled: true
+ -> Memoize
+ Cache Key: a.x
+ Cache Mode: logical
+ -> Index Scan using mem_semi_inner_b_x_idx on mem_semi_inner_b b
+ Index Cond: (x = a.x)
+ -> Index Scan using mem_semi_inner_c_x_z_idx on mem_semi_inner_c c
+ Index Cond: (x = b.x)
+ Filter: (y = b.y)
+(13 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT a.x, b.x FROM mem_semi_inner_a a
+ LEFT JOIN mem_semi_inner_b b ON (a.x=b.x)
+WHERE NOT EXISTS (
+ SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x AND c.y=b.y AND c.z=a.z);
+ QUERY PLAN
+---------------------------------------------------------------------------------
+ Nested Loop Anti Join
+ Join Filter: (c.y = b.y)
+ -> Nested Loop Left Join
+ -> Seq Scan on mem_semi_inner_a a
+ Disabled: true
+ -> Memoize
+ Cache Key: a.x
+ Cache Mode: logical
+ -> Index Scan using mem_semi_inner_b_x_idx on mem_semi_inner_b b
+ Index Cond: (x = a.x)
+ -> Index Scan using mem_semi_inner_c_x_z_idx on mem_semi_inner_c c
+ Index Cond: ((x = a.x) AND (z = a.z))
+(12 rows)
+
+DROP TABLE mem_semi_inner_a,mem_semi_inner_b,mem_semi_inner_c;
+RESET enable_hashjoin;
+RESET enable_mergejoin;
+RESET enable_seqscan;
diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out
index d0db8a412ff..5ab56f8d71f 100644
--- a/src/test/regress/expected/subselect.out
+++ b/src/test/regress/expected/subselect.out
@@ -2642,6 +2642,7 @@ ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd);
-> Memoize
Cache Key: b.hundred, b.odd
Cache Mode: binary
+ Store Mode: singlerow
-> Subquery Scan on "ANY_subquery"
Filter: (b.hundred = "ANY_subquery".min)
-> Result
@@ -2650,5 +2651,5 @@ ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd);
-> Index Scan using tenk2_hundred on tenk2 c
Index Cond: (hundred IS NOT NULL)
Filter: (odd = b.odd)
-(16 rows)
+(17 rows)
diff --git a/src/test/regress/sql/memoize.sql b/src/test/regress/sql/memoize.sql
index c0d47fa875a..048c8e90ad0 100644
--- a/src/test/regress/sql/memoize.sql
+++ b/src/test/regress/sql/memoize.sql
@@ -244,3 +244,52 @@ RESET max_parallel_workers_per_gather;
RESET parallel_tuple_cost;
RESET parallel_setup_cost;
RESET min_parallel_table_scan_size;
+
+--
+-- Tests on Memoize under SEMI and ANTI joins.
+--
+
+CREATE TABLE mem_semi_inner_a (x int, z int);
+CREATE TABLE mem_semi_inner_b (x int, y int);
+CREATE TABLE mem_semi_inner_c (x int, y int, z int);
+INSERT INTO mem_semi_inner_a (x,z)
+ (SELECT value%2, -42 FROM generate_series(1,10) AS value);
+INSERT INTO mem_semi_inner_b (x,y)
+ (SELECT value%5, -value%5-1 FROM generate_series(1,10) AS value);
+INSERT INTO mem_semi_inner_c (x,y,z)
+ (SELECT value%50, value, -42 FROM generate_series(1,100) AS value);
+CREATE INDEX ON mem_semi_inner_b(x);
+CREATE INDEX ON mem_semi_inner_c(x,z);
+VACUUM ANALYZE mem_semi_inner_a,mem_semi_inner_b,mem_semi_inner_c;
+
+-- Force NestLoop and IndexScan. Hope, the Memoize node win the cost
+-- competition on the inner c table scan.
+SET enable_hashjoin = 'off';
+SET enable_mergejoin = 'off';
+SET enable_seqscan = 'off';
+
+-- Primitive example of semi and anti join caching the inner's result
+EXPLAIN (COSTS OFF)
+SELECT a.x FROM mem_semi_inner_a a
+WHERE EXISTS (SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x);
+EXPLAIN (COSTS OFF)
+SELECT a.x FROM mem_semi_inner_a a
+WHERE NOT EXISTS (SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x);
+
+-- Check the query plans contain the Memoize node over the "Scan b" operator
+-- and does not contain memoize over "Scan c".
+EXPLAIN (COSTS OFF)
+SELECT a.x, b.x FROM mem_semi_inner_a a
+ LEFT JOIN mem_semi_inner_b b ON (a.x=b.x)
+WHERE EXISTS (
+ SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x AND c.y=b.y AND c.z=a.z);
+EXPLAIN (COSTS OFF)
+SELECT a.x, b.x FROM mem_semi_inner_a a
+ LEFT JOIN mem_semi_inner_b b ON (a.x=b.x)
+WHERE NOT EXISTS (
+ SELECT 1 FROM mem_semi_inner_c c WHERE c.x=a.x AND c.y=b.y AND c.z=a.z);
+
+DROP TABLE mem_semi_inner_a,mem_semi_inner_b,mem_semi_inner_c;
+RESET enable_hashjoin;
+RESET enable_mergejoin;
+RESET enable_seqscan;
--
2.48.1
