Subject: Memoize ANTI and SEMI JOIN inner

From: Andrei Lepikhov <[email-masked]>
Date: Thu, 6 Mar 2025 14:08:59 +0100

Hi,

In case of NestLoop with parameterised inner semi-join for each outer 
tuple requires only a single tuple from its inner relation to produce a 
result. It seems that the same principle applies to an anti-join. This 
approach could effectively allow the Memoize node to enhance the 
performance of pulled-up EXISTS and NOT EXISTS sublinks.

In attachment see a sketch of the feature. Since we are using single_row 
mode, adapting this method to cache semi-join inner results should not 
be extremely complex. However, I am unsure about potential corner cases 
and would appreciate any feedback or criticisms regarding this approach.

-- 
regards, Andrei Lepikhov
From e47abde1f6a2c8c8d7fa588df72e59c0cd049d4c Mon Sep 17 00:00:00 2001
From: "Andrei V. Lepikhov" <[email-masked]>
Date: Wed, 25 Dec 2024 14:33:12 +0700
Subject: [PATCH v0] Memoise the inner of SEMI- and ANTI-join.

To get 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 feasible.

It is clear that the semi-join operates correctly: it returns the outer tuple
as soon as the first tuple is received from the inner query. In contrast, the
behaviour of the anti-join is less straightforward. If anti-join had a join
clause not pushed to the parameterised inner, it would be possible to read more
than a single tuple from the inner, which causes inconsistency. However,
it seems that this is an impossible case for the current planner.
---
 src/backend/commands/explain.c          | 9 +++++++++
 src/backend/optimizer/path/costsize.c   | 2 +-
 src/backend/optimizer/path/joinpath.c   | 5 +++--
 src/backend/optimizer/util/pathnode.c   | 2 +-
 src/test/regress/expected/join.out      | 3 ++-
 src/test/regress/expected/subselect.out | 3 ++-
 6 files changed, 18 insertions(+), 6 deletions(-)

diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index d8a7232cedb..c90067dadcb 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -3632,6 +3632,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);
 	}
 	else
 	{
@@ -3639,6 +3643,11 @@ show_memoize_info(MemoizeState *mstate, List *ancestors, ExplainState *es)
 		appendStringInfo(es->str, "Cache Key: %s\n", keystr.data);
 		ExplainIndentText(es);
 		appendStringInfo(es->str, "Cache Mode: %s\n", mstate->binary_mode ? "binary" : "logical");
+		if (mstate->singlerow)
+		{
+			ExplainIndentText(es);
+			appendStringInfo(es->str, "Store Mode: %s\n", "singlerow");
+		}
 	}
 
 	pfree(keystr.data);
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 73d78617009..4cca5a7395c 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..89738b483ef 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)
@@ -725,7 +726,7 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
 	 */
 	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
@@ -808,7 +809,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/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)
 
-- 
2.48.1

---

From: Andrei Lepikhov <[email-masked]>
Date: Wed, 19 Mar 2025 18:15:54 +0100

> and would appreciate any feedback or criticisms regarding this approach.
I found a corner case that breaks this approach: when NestLoop has a 
join clause or a filter, it may filter inner tuples, thus scanning more 
than only one time for each outer. You can see the reproduction script 
in the attachment. Each of the reproduction queries throws the error:
ERROR: cache entry already complete

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.

-- 
regards, Andrei Lepikhov

---

From: David Rowley <[email-masked]>
Date: Thu, 20 Mar 2025 19:02:16 +1300

> 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:

nlstate->js.single_match = (node->join.inner_unique ||
node->join.jointype == JOIN_SEMI);

For making this work, I think the attached should be about the guts of
the code changes. I didn't look at the comments. Right now I can't
think of any reason why this can't be done, but some experimentation
might reveal some reason that it can't.

David

---

From: Andrei Lepikhov <[email-masked]>
Date: Fri, 21 Mar 2025 16:56:09 +0100

> nodeNestloop.c. To save doing additional checks at run-time, the code
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.

-- 
regards, Andrei Lepikhov

From c5897e31d2a95de04fa0e641aeff43f3118bcced Mon Sep 17 00:00:00 2001
From: "Andrei V. Lepikhov" <[email-masked]>
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);

 	if (!es->analyze)
index f6f77b8fe19..941ba6e1d49 100644
 
index 18891ce9156..c75408f552b 100644
 
 	/* 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;
 }
 
 -- 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

---

From: Alena Rybakina <[email-masked]>
Date: Mon, 31 Mar 2025 05:33:49 +0300

Hi!

On 21.03.2025 18:56, Andrei Lepikhov wrote:
> 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: Alena Rybakina <[email-masked]>
Date: Mon, 31 Mar 2025 05:50:07 +0300

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:
> 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),

 	/*

 
 
 	if (!es->analyze)

 
 	/*
 
 	/*
 
 	return pathnode;
 }

---

From: David Rowley <[email-masked]>
Date: Mon, 31 Mar 2025 16:04:18 +1300

On Mon, 31 Mar 2025 at 15:33, Alena Rybakina <[email-masked]> wrote:
> 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.

add_paths_to_joinrel() just chooses not to populate inner_unique for
SEMI and ANTI joins because, as of today's master, it's pretty
pointless to determine that because the executor will short-circuit
and skip to the next outer tuple for those join types anyway. I don't
follow why having both these flags set would cause trouble. It seems
perfectly legitimate that add_paths_to_joinrel() could choose to set
the inner_unique flag for these join types, and if it did, the Assert
you're proposing would fail for no good reason.

David

---

From: Alena Rybakina <[email-masked]>
Date: Mon, 31 Mar 2025 06:21:43 +0300

On 31.03.2025 06:04, David Rowley wrote:
> On Mon, 31 Mar 2025 at 15:33, Alena Rybakina<[email-masked]>  wrote:
I tend to agree with you that someone might set this flag to true for 
these join types in the future.

However, is it necessary to check that extra->inner_unique must be false 
for SEMI/ANTI joins here, or am I missing something? It looks a little 
confusing at this point.

if(!extra->inner_unique&& (jointype== JOIN_SEMI|| jointype== JOIN_ANTI))

     single_mode= true;

--

Regards,
Alena Rybakina
Postgres Professional

---

From: David Rowley <[email-masked]>
Date: Mon, 31 Mar 2025 16:33:03 +1300

On Mon, 31 Mar 2025 at 16:21, Alena Rybakina <[email-masked]> wrote:
> However, is it necessary to check that extra->inner_unique must be false for SEMI/ANTI joins here, or am I missing something? It looks a little confusing at this point.

If it is necessary, I don't see the reason for it. It was me that
worked on unique joins and I see no reason why a SEMI or ANTI join
couldn't be marked as unique. The reason they're not today is that the
only point of the unique join optimisation is so that during
execution, the join nodes could skip to the next outer tuple after
matching the current outer to an inner.  If the join is unique, then
there are no more join partners to find for the current outer after
matching it up once. With SEMI and ANTI joins, we skip to the next
outer tuple after finding a match anyway, so there's no point in going
to the trouble of setting the inner_unique flag.

I can't say definitively that we won't find a reason in the future
that we should set inner_unique for SEMI/ANTI joins, so I don't follow
the need for the Assert.

Maybe you're seeing something that I'm not. What do you think will
break if both flags are true?

David

---

From: Alena Rybakina <[email-masked]>
Date: Mon, 31 Mar 2025 09:34:54 +0300

> break if both flags are true?
Actually, I was mainly confused by the code itself - the check seemed to 
contradict the explanation. It looked like we were enforcing that
inner_unique must be false for SEMI/ANTI joins, even though it's not 
actually important for those join types.
That’s why I originally proposed either adding an Assert or removing 
this flag from check altogether, just to make it more explicit.

So, I agree with your explanation — by the definition of SEMI and ANTI 
joins, there's no need to set inner_unique, and also no need to assert 
against it.
These joins skip to the next outer tuple once they find a match (or fail 
to find one, in the case of ANTI).

I updated the diff, where I left changes only in the code comment.

 	/*

---

From: Andrei Lepikhov <[email-masked]>
Date: Mon, 31 Mar 2025 09:45:18 +0200

> break if both flags are true?
I considered targeting PG 19 and July Comitfest for this feature, but 
currently, I don't see any further development needed here. What are 
your thoughts, David? Does it make sense to commit this to PG 18?

I have no reason to rush the process, but this feature seems beneficial 
for practice. When the internal structure is a bushy join tree, 
producing even a single tuple can be costly. SQL Server's Spool node 
addresses this issue, and people sometimes experience confusion 
detecting degradation during migration with specific queries.

-- 
regards, Andrei Lepikhov

---

From: Richard Guo <[email-masked]>
Date: Mon, 31 Mar 2025 18:03:43 +0900

> might reveal some reason that it can't.

I reviewed this patch and I have some concerns about the following
code:

    if (extra->inner_unique &&
        (inner_path->param_info == NULL ||
         bms_num_members(inner_path->param_info->ppi_serials) <
         list_length(extra->restrictlist)))
        return NULL;

I understand that this check is used to ensure that the entire join
condition is parameterized in the case of unique joins, so that we can
safely mark the cache entry as complete after reading the first tuple.
However, ppi_clauses includes join clauses available from all outer
rels, not just the current outer rel, while extra->restrictlist only
includes the restriction clauses for the current join.  This means the
check could pass even if a restriction clause isn't parameterized, as
long as another join clause, which doesn't belong to the current join,
is included in ppi_clauses.

Thanks
Richard

---

From: David Rowley <[email-masked]>
Date: Mon, 31 Mar 2025 22:39:14 +1300

> is included in ppi_clauses.

Shouldn't you be more concerned about master here than the patch given
that the code you pasted is from master?

David

---

From: Andrei Lepikhov <[email-masked]>
Date: Mon, 31 Mar 2025 11:46:08 +0200

> is included in ppi_clauses.
Initially, I had the same concern. But if ppi_clauses contains a qual, 
it should refer to this join and, as a result, be in the 
extra->restrictlist, isn't it?
I thought about references to the other side of an OUTER JOIN, but if 
the subquery refers to LHS, it just not be transformed to the SEMI/ANTI 
join.
Anyway, if you provide an example or just a sketch, I will be happy to 
discover it.

-- 
regards, Andrei Lepikhov

---

From: Richard Guo <[email-masked]>
Date: Mon, 31 Mar 2025 18:50:04 +0900

> that the code you pasted is from master?

Right.  This code is from the master branch, not the patch.  It caught
my attention while I was reviewing the patch and noticed it modifies
this code.

Thanks
Richard

---

From: Richard Guo <[email-masked]>
Date: Mon, 31 Mar 2025 19:18:37 +0900

> extra->restrictlist, isn't it?

Hmm, I don't think so.  As I mentioned upthread, ppi_clauses includes
join clauses available from all outer rels, not just the current one.
So a clause included in ppi_clauses is not necessarily included in
extra->restrictlist.  As an example, consider

create table t (a int, b int);

explain (costs off)
select * from t t1 join t t2 join
    lateral (select *, t1.a+t2.a as x from t t3 offset 0) t3
    on t2.a = t3.a
  on t1.b = t3.b;
                       QUERY PLAN
---------------------------------------------------------
 Nested Loop
   ->  Seq Scan on t t2
   ->  Nested Loop
         ->  Seq Scan on t t1
         ->  Subquery Scan on t3
               Filter: ((t2.a = t3.a) AND (t1.b = t3.b))
               ->  Seq Scan on t t3_1
(7 rows)

t3's ppi_clauses includes "t2.a = t3.a" and "t1.b = t3.b", while t1/t3
join's restrictlist only includes "t1.b = t3.b".

Thanks
Richard

---

From: Andrei Lepikhov <[email-masked]>
Date: Mon, 31 Mar 2025 12:33:12 +0200

> join's restrictlist only includes "t1.b = t3.b".
I attempted to make your query ab it closer to our case:

SET enable_mergejoin = f;
SET enable_hashjoin = f;
SET enable_material = f;
CREATE INDEX ON t(a);

explain (costs off)
select * from t t1 join t t2
   on EXISTS (select *, t1.a+t2.a as x from t t3
     WHERE t2.a = t3.a AND t1.b = t3.b);

and I don't get the case. As I see, ANTI/SEMI join just transforms to 
the regular join and it is still not the case. May you be more specific?

-- 
regards, Andrei Lepikhov

---

From: Richard Guo <[email-masked]>
Date: Tue, 1 Apr 2025 16:18:58 +0900

> the regular join and it is still not the case. May you be more specific?

Upthread, you said that a qual contained in ppi_clauses will also be
included in extra->restrictlist.  I provided this example to show that
this is not true.  And it seems to me that this discrepancy makes the
check I mentioned earlier not reliable in all cases.  As I explained
earlier, this check could pass even if a restriction clause isn't
parameterized, as long as another join clause, which doesn't belong to
the current join, is included in ppi_clauses.  This is not correct.

This isn't about your patch, but about the master code.  However, if
this code is incorrect, your patch will also behave incorrectly, since
you patch relies on and extends this check.

Thanks
Richard

---

From: Richard Guo <[email-masked]>
Date: Wed, 9 Apr 2025 15:48:33 +0900

> might reveal some reason that it can't.

I conducted some experiments, and I'm afraid it's not safe to consider
Memoize for semi or anti joins, unless the inner side is provably
unique.  As an example, please consider:

create table t (a int, b boolean);
insert into t select i%3, false from generate_series(1,100)i;
analyze t;

select * from t t1 where t1.a in
 (select a from t t2 where t2.b in
  (select t1.b from t t3 where t2.a > 1 offset 0));
ERROR:  cache entry already complete

With the proposed patch, this query results in an error.

The problem is that join clauses from the upper level may be moved to
the semi join.  For a given outer tuple, the first inner tuple that
satisfies the current parameters will mark the cache entry as complete
because singlerow is set to true.  However, if that inner tuple and
the current outer tuple don't satisfy the join clauses, the second
inner tuple that satisfies the parameters will complain that the cache
entry is already marked as complete.

If the inner side is provably unique, there will be no such problem,
as there won't be a second matching tuple.  OTOH, in this case, the
semi join will be reduced to an inner join by reduce_unique_semijoins.
Therefore, it doesn't make much sense to prove inner_unique for semi
joins in add_paths_to_joinrel.

Perhaps we could spend some planner cycles proving inner_unique for
anti joins, so that Memoize nodes can be considered for them?

Thanks
Richard

---

From: Richard Guo <[email-masked]>
Date: Thu, 10 Apr 2025 19:36:14 +0900

On Wed, Apr 9, 2025 at 6:18 PM David Rowley <[email-masked]> wrote:
> On Wed, 9 Apr 2025 at 18:48, Richard Guo <[email-masked]> wrote:

> Worth a try. It should be pretty easy to enable, as far as I can see.
> It might just be a case of shuffling the cases around in the switch
> statement in add_paths_to_joinrel().

Right.  Here is a patch for that.

Thanks
Richard

---

From: Andres Freund <[email-masked]>
Date: Tue, 13 May 2025 09:51:42 -0400

Hi,

> Right.  Here is a patch for that.

This is failing on CI:
https://cirrus-ci.com/github/postgresql-cfbot/postgresql/cf%2F5636
https://api.cirrus-ci.com/v1/artifact/task/5411026402803712/testrun/build-32/testrun/regress/regress/regression.diffs

diff -U3 /tmp/cirrus-ci-build/src/test/regress/expected/memoize.out /tmp/cirrus-ci-build/build-32/testrun/regress/regress/results/memoize.out
--- /tmp/cirrus-ci-build/src/test/regress/expected/memoize.out	2025-04-12 11:24:10.866868945 +0000
+++ /tmp/cirrus-ci-build/build-32/testrun/regress/regress/results/memoize.out	2025-04-12 11:32:44.454864476 +0000
@@ -525,7 +525,7 @@
                      ->  Unique (actual rows=2.67 loops=N)
                            ->  Sort (actual rows=67.33 loops=N)
                                  Sort Key: t2_1.a
-                                 Sort Method: quicksort  Memory: 27kB
+                                 Sort Method: quicksort  Memory: 18kB
                                  ->  Seq Scan on tab_anti t2_1 (actual rows=100.00 loops=N)
 (15 rows)

There shouldn't be Memory mentioned in tests added to the tree.

Greetings,

Andres

---

From: Richard Guo <[email-masked]>
Date: Wed, 14 May 2025 11:13:56 +0900

> +++ /tmp/cirrus-ci-build/build-32/testrun/regress/regress/results/memoize.out   2025-04-12 11:32:44.454864476 +0000

Thanks for pointing this out.  You're right — Memory usage should be
hidden from the output of EXPLAIN ANALYZE.  I'm a bit surprised the
existing explain_memoize function doesn't already handle that; I
guess it's because the plans in memoize.sql don't currently include
any Sort nodes.  In any case, I've added a regexp_replace to filter
out 'Memory: \d+kB' in explain_memoize.

Thanks
Richard

---

From: Richard Guo <[email-masked]>
Date: Wed, 2 Jul 2025 11:08:01 +0900

> Right.  Here is a patch for that.

Here's a rebased version with no other changes.

David, Andrei, would you like to take another look?  I'm planning to
push it soon.

Thanks
Richard

---

From: wenhui qiu <[email-masked]>
Date: Wed, 2 Jul 2025 11:48:11 +0800

HI

> - if (!extra->inner_unique && (jointype == JOIN_SEMI ||
> - jointype == JOIN_ANTI))
> + if ((jointype == JOIN_SEMI || jointype == JOIN_ANTI) &&
> + !extra->inner_unique)
To be nitpicky, this change is meant to align with the earlier comment
modifications to improve code readability, right? Everything else looks
good to me."

Thanks

---

From: Andrei Lepikhov <[email-masked]>
Date: Wed, 2 Jul 2025 11:01:39 +0200

> modifications to improve code readability, right? Everything else looks 
Yep, I also found only this flaw.
Comments looks clear to me, test is quite stable.

May be correct the line:
INSERT INTO tab_anti SELECT i%3, false FROM generate_series(1,100)i;
with a backspace or an 'AS' keyword?

-- 
regards, Andrei Lepikhov