Memoize ANTI and SEMI JOIN inner

diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 18891ce9156..03b4506e873 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -714,19 +714,6 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
 		ph_lateral_vars == NIL)
 		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.
-	 *
-	 * 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;
-
 	/*
 	 * Memoize normally marks cache entries as complete when it runs out of
 	 * tuples to read from its subplan.  However, with unique joins, Nested
@@ -753,7 +740,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 || jointype == JOIN_SEMI || jointype == JOIN_ANTI) &&
 		(inner_path->param_info == NULL ||
 		 bms_num_members(inner_path->param_info->ppi_serials) <
 		 list_length(extra->restrictlist)))
@@ -808,7 +795,7 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
 											inner_path,
 											param_exprs,
 											hash_operators,
-											extra->inner_unique,
+											extra->inner_unique || jointype == JOIN_SEMI || jointype == JOIN_ANTI,
 											binary_mode,
 											outer_path->rows);
 	}

From c5897e31d2a95de04fa0e641aeff43f3118bcced Mon Sep 17 00:00:00 2001
From: "Andrei V. Lepikhov" <lepihov@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

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,

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" <lepihov@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

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

From 942b88bdb6a2dd789e49fdcc947c748cac259a76 Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Wed, 9 Apr 2025 18:06:48 +0900
Subject: [PATCH v1] Enable use of Memoize for ANTI joins

Currently, we do not support Memoize for SEMI and ANTI joins because
nested loop SEMI/ANTI joins do not scan the inner relation to
completion, which prevents Memoize from marking the cache entry as
complete.  One might argue that we could mark the cache entry as
complete after fetching the first inner tuple, but that would not be
safe: if the first inner tuple and the current outer tuple do not
satisfy the join clauses, a second inner tuple matching the parameters
would find the cache entry already marked as complete.

However, if the inner side is provably unique, this issue doesn't
arise, since there would be no second matching tuple.  That said, this
doesn't help in the case of SEMI joins, because a SEMI join with a
provably unique inner side would already have been reduced to an inner
join by reduce_unique_semijoins.

Therefore, in this patch, we check whether the inner relation is
provably unique for ANTI joins and enable the use of Memoize in such
cases.
---
 src/backend/optimizer/path/joinpath.c | 47 +++++++++++----------
 src/test/regress/expected/memoize.out | 59 +++++++++++++++++++++++++++
 src/test/regress/sql/memoize.sql      | 26 ++++++++++++
 3 files changed, 110 insertions(+), 22 deletions(-)

diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 18891ce9156..064e73cc862 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -154,13 +154,17 @@ add_paths_to_joinrel(PlannerInfo *root,
 	/*
 	 * See if the inner relation is provably unique for this outer rel.
 	 *
-	 * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
-	 * matter since the executor can make the equivalent optimization anyway;
-	 * we need not expend planner cycles on proofs.  For JOIN_UNIQUE_INNER, we
-	 * must be considering a semijoin whose inner side is not provably unique
-	 * (else reduce_unique_semijoins would've simplified it), so there's no
-	 * point in calling innerrel_is_unique.  However, if the LHS covers all of
-	 * the semijoin's min_lefthand, then it's appropriate to set inner_unique
+	 * We have some special cases: for JOIN_SEMI, it doesn't matter since the
+	 * executor can make the equivalent optimization anyway.  It also doesn't
+	 * help enable use of Memoize, since a semijoin with a provably unique
+	 * inner side should have been reduced to an inner join in that case.
+	 * Therefore, we need not expend planner cycles on proofs.  (For
+	 * JOIN_ANTI, although it doesn't help the executor for the same reason,
+	 * it can benefit Memoize paths.)  For JOIN_UNIQUE_INNER, we must be
+	 * considering a semijoin whose inner side is not provably unique (else
+	 * reduce_unique_semijoins would've simplified it), so there's no point in
+	 * calling innerrel_is_unique.  However, if the LHS covers all of the
+	 * semijoin's min_lefthand, then it's appropriate to set inner_unique
 	 * because the path produced by create_unique_path will be unique relative
 	 * to the LHS.  (If we have an LHS that's only part of the min_lefthand,
 	 * that is *not* true.)  For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
@@ -169,12 +173,6 @@ add_paths_to_joinrel(PlannerInfo *root,
 	switch (jointype)
 	{
 		case JOIN_SEMI:
-		case JOIN_ANTI:
-
-			/*
-			 * XXX it may be worth proving this to allow a Memoize to be
-			 * considered for Nested Loop Semi/Anti Joins.
-			 */
 			extra.inner_unique = false; /* well, unproven */
 			break;
 		case JOIN_UNIQUE_INNER:
@@ -715,16 +713,21 @@ 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.
-	 *
-	 * XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
-	 * = true.  Should we?  See add_paths_to_joinrel()
+	 * Currently we don't do this for SEMI and ANTI joins, because nested loop
+	 * SEMI/ANTI joins don't scan the inner node to completion, which means
+	 * memoize cannot mark the cache entry as complete.  Nor can we mark the
+	 * cache entry as complete after fetching the first inner tuple, because
+	 * if that tuple and the current outer tuple don't satisfy the join
+	 * clauses, a second inner tuple that satisfies the parameters would find
+	 * the cache entry already marked as complete.  The only exception is when
+	 * the inner relation is provably unique, as in that case, there won't be
+	 * a second matching tuple and we can safely mark the cache entry as
+	 * complete after fetching the first inner tuple.  Note that in such
+	 * cases, the SEMI join should have been reduced to an inner join by
+	 * reduce_unique_semijoins.
 	 */
-	if (!extra->inner_unique && (jointype == JOIN_SEMI ||
-								 jointype == JOIN_ANTI))
+	if ((jointype == JOIN_SEMI || jointype == JOIN_ANTI) &&
+		!extra->inner_unique)
 		return NULL;
 
 	/*
diff --git a/src/test/regress/expected/memoize.out b/src/test/regress/expected/memoize.out
index 38dfaf021c9..73ced02e65b 100644
--- a/src/test/regress/expected/memoize.out
+++ b/src/test/regress/expected/memoize.out
@@ -500,3 +500,62 @@ RESET max_parallel_workers_per_gather;
 RESET parallel_tuple_cost;
 RESET parallel_setup_cost;
 RESET min_parallel_table_scan_size;
+-- Ensure memoize works for ANTI joins
+CREATE TABLE tab_anti (a int, b boolean);
+INSERT INTO tab_anti SELECT i%3, false FROM generate_series(1,100)i;
+ANALYZE tab_anti;
+-- Ensure we get a Memoize plan for ANTI join
+SELECT explain_memoize('
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;', false);
+                                      explain_memoize                                       
+--------------------------------------------------------------------------------------------
+ Aggregate (actual rows=1.00 loops=N)
+   ->  Nested Loop Anti Join (actual rows=33.00 loops=N)
+         ->  Seq Scan on tab_anti t1 (actual rows=100.00 loops=N)
+         ->  Memoize (actual rows=0.67 loops=N)
+               Cache Key: (t1.a + 1), t1.a
+               Cache Mode: binary
+               Hits: 97  Misses: 3  Evictions: Zero  Overflows: 0  Memory Usage: NkB
+               ->  Subquery Scan on t2 (actual rows=0.67 loops=N)
+                     Filter: ((t1.a + 1) = t2.a)
+                     Rows Removed by Filter: 2
+                     ->  Unique (actual rows=2.67 loops=N)
+                           ->  Sort (actual rows=67.33 loops=N)
+                                 Sort Key: t2_1.a
+                                 Sort Method: quicksort  Memory: 27kB
+                                 ->  Seq Scan on tab_anti t2_1 (actual rows=100.00 loops=N)
+(15 rows)
+
+-- And check we get the expected results.
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;
+ count 
+-------
+    33
+(1 row)
+
+-- Ensure we do not add memoize node for SEMI join
+EXPLAIN (COSTS OFF)
+SELECT * FROM tab_anti t1 WHERE t1.a IN
+ (SELECT a FROM tab_anti t2 WHERE t2.b IN
+  (SELECT t1.b FROM tab_anti t3 WHERE t2.a > 1 OFFSET 0));
+                   QUERY PLAN                    
+-------------------------------------------------
+ Nested Loop Semi Join
+   ->  Seq Scan on tab_anti t1
+   ->  Nested Loop Semi Join
+         Join Filter: (t1.a = t2.a)
+         ->  Seq Scan on tab_anti t2
+         ->  Subquery Scan on "ANY_subquery"
+               Filter: (t2.b = "ANY_subquery".b)
+               ->  Result
+                     One-Time Filter: (t2.a > 1)
+                     ->  Seq Scan on tab_anti t3
+(10 rows)
+
+DROP TABLE tab_anti;
diff --git a/src/test/regress/sql/memoize.sql b/src/test/regress/sql/memoize.sql
index c0d47fa875a..1370d2c9cfc 100644
--- a/src/test/regress/sql/memoize.sql
+++ b/src/test/regress/sql/memoize.sql
@@ -244,3 +244,29 @@ RESET max_parallel_workers_per_gather;
 RESET parallel_tuple_cost;
 RESET parallel_setup_cost;
 RESET min_parallel_table_scan_size;
+
+-- Ensure memoize works for ANTI joins
+CREATE TABLE tab_anti (a int, b boolean);
+INSERT INTO tab_anti SELECT i%3, false FROM generate_series(1,100)i;
+ANALYZE tab_anti;
+
+-- Ensure we get a Memoize plan for ANTI join
+SELECT explain_memoize('
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;', false);
+
+-- And check we get the expected results.
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;
+
+-- Ensure we do not add memoize node for SEMI join
+EXPLAIN (COSTS OFF)
+SELECT * FROM tab_anti t1 WHERE t1.a IN
+ (SELECT a FROM tab_anti t2 WHERE t2.b IN
+  (SELECT t1.b FROM tab_anti t3 WHERE t2.a > 1 OFFSET 0));
+
+DROP TABLE tab_anti;
-- 
2.43.0

From 3b1dd3d81b4b7db068d8f7bdf40854c8d0d3edfb Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Wed, 9 Apr 2025 18:06:48 +0900
Subject: [PATCH v2] Enable use of Memoize for ANTI joins

Currently, we do not support Memoize for SEMI and ANTI joins because
nested loop SEMI/ANTI joins do not scan the inner relation to
completion, which prevents Memoize from marking the cache entry as
complete.  One might argue that we could mark the cache entry as
complete after fetching the first inner tuple, but that would not be
safe: if the first inner tuple and the current outer tuple do not
satisfy the join clauses, a second inner tuple matching the parameters
would find the cache entry already marked as complete.

However, if the inner side is provably unique, this issue doesn't
arise, since there would be no second matching tuple.  That said, this
doesn't help in the case of SEMI joins, because a SEMI join with a
provably unique inner side would already have been reduced to an inner
join by reduce_unique_semijoins.

Therefore, in this patch, we check whether the inner relation is
provably unique for ANTI joins and enable the use of Memoize in such
cases.
---
 src/backend/optimizer/path/joinpath.c | 47 +++++++++++----------
 src/test/regress/expected/memoize.out | 60 +++++++++++++++++++++++++++
 src/test/regress/sql/memoize.sql      | 27 ++++++++++++
 3 files changed, 112 insertions(+), 22 deletions(-)

diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 26f0336f1e4..b9e46a40e1f 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -154,13 +154,17 @@ add_paths_to_joinrel(PlannerInfo *root,
 	/*
 	 * See if the inner relation is provably unique for this outer rel.
 	 *
-	 * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
-	 * matter since the executor can make the equivalent optimization anyway;
-	 * we need not expend planner cycles on proofs.  For JOIN_UNIQUE_INNER, we
-	 * must be considering a semijoin whose inner side is not provably unique
-	 * (else reduce_unique_semijoins would've simplified it), so there's no
-	 * point in calling innerrel_is_unique.  However, if the LHS covers all of
-	 * the semijoin's min_lefthand, then it's appropriate to set inner_unique
+	 * We have some special cases: for JOIN_SEMI, it doesn't matter since the
+	 * executor can make the equivalent optimization anyway.  It also doesn't
+	 * help enable use of Memoize, since a semijoin with a provably unique
+	 * inner side should have been reduced to an inner join in that case.
+	 * Therefore, we need not expend planner cycles on proofs.  (For
+	 * JOIN_ANTI, although it doesn't help the executor for the same reason,
+	 * it can benefit Memoize paths.)  For JOIN_UNIQUE_INNER, we must be
+	 * considering a semijoin whose inner side is not provably unique (else
+	 * reduce_unique_semijoins would've simplified it), so there's no point in
+	 * calling innerrel_is_unique.  However, if the LHS covers all of the
+	 * semijoin's min_lefthand, then it's appropriate to set inner_unique
 	 * because the path produced by create_unique_path will be unique relative
 	 * to the LHS.  (If we have an LHS that's only part of the min_lefthand,
 	 * that is *not* true.)  For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
@@ -169,12 +173,6 @@ add_paths_to_joinrel(PlannerInfo *root,
 	switch (jointype)
 	{
 		case JOIN_SEMI:
-		case JOIN_ANTI:
-
-			/*
-			 * XXX it may be worth proving this to allow a Memoize to be
-			 * considered for Nested Loop Semi/Anti Joins.
-			 */
 			extra.inner_unique = false; /* well, unproven */
 			break;
 		case JOIN_UNIQUE_INNER:
@@ -715,16 +713,21 @@ 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.
-	 *
-	 * XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
-	 * = true.  Should we?  See add_paths_to_joinrel()
+	 * Currently we don't do this for SEMI and ANTI joins, because nested loop
+	 * SEMI/ANTI joins don't scan the inner node to completion, which means
+	 * memoize cannot mark the cache entry as complete.  Nor can we mark the
+	 * cache entry as complete after fetching the first inner tuple, because
+	 * if that tuple and the current outer tuple don't satisfy the join
+	 * clauses, a second inner tuple that satisfies the parameters would find
+	 * the cache entry already marked as complete.  The only exception is when
+	 * the inner relation is provably unique, as in that case, there won't be
+	 * a second matching tuple and we can safely mark the cache entry as
+	 * complete after fetching the first inner tuple.  Note that in such
+	 * cases, the SEMI join should have been reduced to an inner join by
+	 * reduce_unique_semijoins.
 	 */
-	if (!extra->inner_unique && (jointype == JOIN_SEMI ||
-								 jointype == JOIN_ANTI))
+	if ((jointype == JOIN_SEMI || jointype == JOIN_ANTI) &&
+		!extra->inner_unique)
 		return NULL;
 
 	/*
diff --git a/src/test/regress/expected/memoize.out b/src/test/regress/expected/memoize.out
index 38dfaf021c9..150dc1b44cf 100644
--- a/src/test/regress/expected/memoize.out
+++ b/src/test/regress/expected/memoize.out
@@ -25,6 +25,7 @@ begin
         ln := regexp_replace(ln, 'Heap Fetches: \d+', 'Heap Fetches: N');
         ln := regexp_replace(ln, 'loops=\d+', 'loops=N');
         ln := regexp_replace(ln, 'Index Searches: \d+', 'Index Searches: N');
+        ln := regexp_replace(ln, 'Memory: \d+kB', 'Memory: NkB');
         return next ln;
     end loop;
 end;
@@ -500,3 +501,62 @@ RESET max_parallel_workers_per_gather;
 RESET parallel_tuple_cost;
 RESET parallel_setup_cost;
 RESET min_parallel_table_scan_size;
+-- Ensure memoize works for ANTI joins
+CREATE TABLE tab_anti (a int, b boolean);
+INSERT INTO tab_anti SELECT i%3, false FROM generate_series(1,100)i;
+ANALYZE tab_anti;
+-- Ensure we get a Memoize plan for ANTI join
+SELECT explain_memoize('
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;', false);
+                                      explain_memoize                                       
+--------------------------------------------------------------------------------------------
+ Aggregate (actual rows=1.00 loops=N)
+   ->  Nested Loop Anti Join (actual rows=33.00 loops=N)
+         ->  Seq Scan on tab_anti t1 (actual rows=100.00 loops=N)
+         ->  Memoize (actual rows=0.67 loops=N)
+               Cache Key: (t1.a + 1), t1.a
+               Cache Mode: binary
+               Hits: 97  Misses: 3  Evictions: Zero  Overflows: 0  Memory Usage: NkB
+               ->  Subquery Scan on t2 (actual rows=0.67 loops=N)
+                     Filter: ((t1.a + 1) = t2.a)
+                     Rows Removed by Filter: 2
+                     ->  Unique (actual rows=2.67 loops=N)
+                           ->  Sort (actual rows=67.33 loops=N)
+                                 Sort Key: t2_1.a
+                                 Sort Method: quicksort  Memory: NkB
+                                 ->  Seq Scan on tab_anti t2_1 (actual rows=100.00 loops=N)
+(15 rows)
+
+-- And check we get the expected results.
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;
+ count 
+-------
+    33
+(1 row)
+
+-- Ensure we do not add memoize node for SEMI join
+EXPLAIN (COSTS OFF)
+SELECT * FROM tab_anti t1 WHERE t1.a IN
+ (SELECT a FROM tab_anti t2 WHERE t2.b IN
+  (SELECT t1.b FROM tab_anti t3 WHERE t2.a > 1 OFFSET 0));
+                   QUERY PLAN                    
+-------------------------------------------------
+ Nested Loop Semi Join
+   ->  Seq Scan on tab_anti t1
+   ->  Nested Loop Semi Join
+         Join Filter: (t1.a = t2.a)
+         ->  Seq Scan on tab_anti t2
+         ->  Subquery Scan on "ANY_subquery"
+               Filter: (t2.b = "ANY_subquery".b)
+               ->  Result
+                     One-Time Filter: (t2.a > 1)
+                     ->  Seq Scan on tab_anti t3
+(10 rows)
+
+DROP TABLE tab_anti;
diff --git a/src/test/regress/sql/memoize.sql b/src/test/regress/sql/memoize.sql
index c0d47fa875a..8d1cdd6990c 100644
--- a/src/test/regress/sql/memoize.sql
+++ b/src/test/regress/sql/memoize.sql
@@ -26,6 +26,7 @@ begin
         ln := regexp_replace(ln, 'Heap Fetches: \d+', 'Heap Fetches: N');
         ln := regexp_replace(ln, 'loops=\d+', 'loops=N');
         ln := regexp_replace(ln, 'Index Searches: \d+', 'Index Searches: N');
+        ln := regexp_replace(ln, 'Memory: \d+kB', 'Memory: NkB');
         return next ln;
     end loop;
 end;
@@ -244,3 +245,29 @@ RESET max_parallel_workers_per_gather;
 RESET parallel_tuple_cost;
 RESET parallel_setup_cost;
 RESET min_parallel_table_scan_size;
+
+-- Ensure memoize works for ANTI joins
+CREATE TABLE tab_anti (a int, b boolean);
+INSERT INTO tab_anti SELECT i%3, false FROM generate_series(1,100)i;
+ANALYZE tab_anti;
+
+-- Ensure we get a Memoize plan for ANTI join
+SELECT explain_memoize('
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;', false);
+
+-- And check we get the expected results.
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;
+
+-- Ensure we do not add memoize node for SEMI join
+EXPLAIN (COSTS OFF)
+SELECT * FROM tab_anti t1 WHERE t1.a IN
+ (SELECT a FROM tab_anti t2 WHERE t2.b IN
+  (SELECT t1.b FROM tab_anti t3 WHERE t2.a > 1 OFFSET 0));
+
+DROP TABLE tab_anti;
-- 
2.43.0

From bd3adf290d31151d1939f3505b1846eae1300c79 Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Wed, 9 Apr 2025 18:06:48 +0900
Subject: [PATCH v3] Enable use of Memoize for ANTI joins

Currently, we do not support Memoize for SEMI and ANTI joins because
nested loop SEMI/ANTI joins do not scan the inner relation to
completion, which prevents Memoize from marking the cache entry as
complete.  One might argue that we could mark the cache entry as
complete after fetching the first inner tuple, but that would not be
safe: if the first inner tuple and the current outer tuple do not
satisfy the join clauses, a second inner tuple matching the parameters
would find the cache entry already marked as complete.

However, if the inner side is provably unique, this issue doesn't
arise, since there would be no second matching tuple.  That said, this
doesn't help in the case of SEMI joins, because a SEMI join with a
provably unique inner side would already have been reduced to an inner
join by reduce_unique_semijoins.

Therefore, in this patch, we check whether the inner relation is
provably unique for ANTI joins and enable the use of Memoize in such
cases.
---
 src/backend/optimizer/path/joinpath.c | 47 +++++++++++----------
 src/test/regress/expected/memoize.out | 60 +++++++++++++++++++++++++++
 src/test/regress/sql/memoize.sql      | 27 ++++++++++++
 3 files changed, 112 insertions(+), 22 deletions(-)

diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 7aa8f5d799c..ebedc5574ca 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -154,13 +154,17 @@ add_paths_to_joinrel(PlannerInfo *root,
 	/*
 	 * See if the inner relation is provably unique for this outer rel.
 	 *
-	 * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
-	 * matter since the executor can make the equivalent optimization anyway;
-	 * we need not expend planner cycles on proofs.  For JOIN_UNIQUE_INNER, we
-	 * must be considering a semijoin whose inner side is not provably unique
-	 * (else reduce_unique_semijoins would've simplified it), so there's no
-	 * point in calling innerrel_is_unique.  However, if the LHS covers all of
-	 * the semijoin's min_lefthand, then it's appropriate to set inner_unique
+	 * We have some special cases: for JOIN_SEMI, it doesn't matter since the
+	 * executor can make the equivalent optimization anyway.  It also doesn't
+	 * help enable use of Memoize, since a semijoin with a provably unique
+	 * inner side should have been reduced to an inner join in that case.
+	 * Therefore, we need not expend planner cycles on proofs.  (For
+	 * JOIN_ANTI, although it doesn't help the executor for the same reason,
+	 * it can benefit Memoize paths.)  For JOIN_UNIQUE_INNER, we must be
+	 * considering a semijoin whose inner side is not provably unique (else
+	 * reduce_unique_semijoins would've simplified it), so there's no point in
+	 * calling innerrel_is_unique.  However, if the LHS covers all of the
+	 * semijoin's min_lefthand, then it's appropriate to set inner_unique
 	 * because the path produced by create_unique_path will be unique relative
 	 * to the LHS.  (If we have an LHS that's only part of the min_lefthand,
 	 * that is *not* true.)  For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
@@ -169,12 +173,6 @@ add_paths_to_joinrel(PlannerInfo *root,
 	switch (jointype)
 	{
 		case JOIN_SEMI:
-		case JOIN_ANTI:
-
-			/*
-			 * XXX it may be worth proving this to allow a Memoize to be
-			 * considered for Nested Loop Semi/Anti Joins.
-			 */
 			extra.inner_unique = false; /* well, unproven */
 			break;
 		case JOIN_UNIQUE_INNER:
@@ -715,16 +713,21 @@ 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.
-	 *
-	 * XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
-	 * = true.  Should we?  See add_paths_to_joinrel()
+	 * Currently we don't do this for SEMI and ANTI joins, because nested loop
+	 * SEMI/ANTI joins don't scan the inner node to completion, which means
+	 * memoize cannot mark the cache entry as complete.  Nor can we mark the
+	 * cache entry as complete after fetching the first inner tuple, because
+	 * if that tuple and the current outer tuple don't satisfy the join
+	 * clauses, a second inner tuple that satisfies the parameters would find
+	 * the cache entry already marked as complete.  The only exception is when
+	 * the inner relation is provably unique, as in that case, there won't be
+	 * a second matching tuple and we can safely mark the cache entry as
+	 * complete after fetching the first inner tuple.  Note that in such
+	 * cases, the SEMI join should have been reduced to an inner join by
+	 * reduce_unique_semijoins.
 	 */
-	if (!extra->inner_unique && (jointype == JOIN_SEMI ||
-								 jointype == JOIN_ANTI))
+	if ((jointype == JOIN_SEMI || jointype == JOIN_ANTI) &&
+		!extra->inner_unique)
 		return NULL;
 
 	/*
diff --git a/src/test/regress/expected/memoize.out b/src/test/regress/expected/memoize.out
index 38dfaf021c9..150dc1b44cf 100644
--- a/src/test/regress/expected/memoize.out
+++ b/src/test/regress/expected/memoize.out
@@ -25,6 +25,7 @@ begin
         ln := regexp_replace(ln, 'Heap Fetches: \d+', 'Heap Fetches: N');
         ln := regexp_replace(ln, 'loops=\d+', 'loops=N');
         ln := regexp_replace(ln, 'Index Searches: \d+', 'Index Searches: N');
+        ln := regexp_replace(ln, 'Memory: \d+kB', 'Memory: NkB');
         return next ln;
     end loop;
 end;
@@ -500,3 +501,62 @@ RESET max_parallel_workers_per_gather;
 RESET parallel_tuple_cost;
 RESET parallel_setup_cost;
 RESET min_parallel_table_scan_size;
+-- Ensure memoize works for ANTI joins
+CREATE TABLE tab_anti (a int, b boolean);
+INSERT INTO tab_anti SELECT i%3, false FROM generate_series(1,100)i;
+ANALYZE tab_anti;
+-- Ensure we get a Memoize plan for ANTI join
+SELECT explain_memoize('
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;', false);
+                                      explain_memoize                                       
+--------------------------------------------------------------------------------------------
+ Aggregate (actual rows=1.00 loops=N)
+   ->  Nested Loop Anti Join (actual rows=33.00 loops=N)
+         ->  Seq Scan on tab_anti t1 (actual rows=100.00 loops=N)
+         ->  Memoize (actual rows=0.67 loops=N)
+               Cache Key: (t1.a + 1), t1.a
+               Cache Mode: binary
+               Hits: 97  Misses: 3  Evictions: Zero  Overflows: 0  Memory Usage: NkB
+               ->  Subquery Scan on t2 (actual rows=0.67 loops=N)
+                     Filter: ((t1.a + 1) = t2.a)
+                     Rows Removed by Filter: 2
+                     ->  Unique (actual rows=2.67 loops=N)
+                           ->  Sort (actual rows=67.33 loops=N)
+                                 Sort Key: t2_1.a
+                                 Sort Method: quicksort  Memory: NkB
+                                 ->  Seq Scan on tab_anti t2_1 (actual rows=100.00 loops=N)
+(15 rows)
+
+-- And check we get the expected results.
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;
+ count 
+-------
+    33
+(1 row)
+
+-- Ensure we do not add memoize node for SEMI join
+EXPLAIN (COSTS OFF)
+SELECT * FROM tab_anti t1 WHERE t1.a IN
+ (SELECT a FROM tab_anti t2 WHERE t2.b IN
+  (SELECT t1.b FROM tab_anti t3 WHERE t2.a > 1 OFFSET 0));
+                   QUERY PLAN                    
+-------------------------------------------------
+ Nested Loop Semi Join
+   ->  Seq Scan on tab_anti t1
+   ->  Nested Loop Semi Join
+         Join Filter: (t1.a = t2.a)
+         ->  Seq Scan on tab_anti t2
+         ->  Subquery Scan on "ANY_subquery"
+               Filter: (t2.b = "ANY_subquery".b)
+               ->  Result
+                     One-Time Filter: (t2.a > 1)
+                     ->  Seq Scan on tab_anti t3
+(10 rows)
+
+DROP TABLE tab_anti;
diff --git a/src/test/regress/sql/memoize.sql b/src/test/regress/sql/memoize.sql
index c0d47fa875a..8d1cdd6990c 100644
--- a/src/test/regress/sql/memoize.sql
+++ b/src/test/regress/sql/memoize.sql
@@ -26,6 +26,7 @@ begin
         ln := regexp_replace(ln, 'Heap Fetches: \d+', 'Heap Fetches: N');
         ln := regexp_replace(ln, 'loops=\d+', 'loops=N');
         ln := regexp_replace(ln, 'Index Searches: \d+', 'Index Searches: N');
+        ln := regexp_replace(ln, 'Memory: \d+kB', 'Memory: NkB');
         return next ln;
     end loop;
 end;
@@ -244,3 +245,29 @@ RESET max_parallel_workers_per_gather;
 RESET parallel_tuple_cost;
 RESET parallel_setup_cost;
 RESET min_parallel_table_scan_size;
+
+-- Ensure memoize works for ANTI joins
+CREATE TABLE tab_anti (a int, b boolean);
+INSERT INTO tab_anti SELECT i%3, false FROM generate_series(1,100)i;
+ANALYZE tab_anti;
+
+-- Ensure we get a Memoize plan for ANTI join
+SELECT explain_memoize('
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;', false);
+
+-- And check we get the expected results.
+SELECT COUNT(*) FROM tab_anti t1 LEFT JOIN
+LATERAL (SELECT DISTINCT ON (a) a, b, t1.a AS x FROM tab_anti t2) t2
+ON t1.a+1 = t2.a
+WHERE t2.a IS NULL;
+
+-- Ensure we do not add memoize node for SEMI join
+EXPLAIN (COSTS OFF)
+SELECT * FROM tab_anti t1 WHERE t1.a IN
+ (SELECT a FROM tab_anti t2 WHERE t2.b IN
+  (SELECT t1.b FROM tab_anti t3 WHERE t2.a > 1 OFFSET 0));
+
+DROP TABLE tab_anti;
-- 
2.43.0