Re: Pathify RHS unique-ification for semijoin planning

Hi Richard,

Thanks for the patch! I applied your patch and played around with it.

I have a question about the following test case you added in
subselect.sql:

+-- Ensure that we can unique-ify expressions more complex than plain Vars
+explain (verbose, costs off)
+select * from semijoin_unique_tbl t1, semijoin_unique_tbl t2
+where (t1.a, t2.a) in (select a+1, b+1 from semijoin_unique_tbl t3)
+order by t1.a, t2.a;
+ QUERY PLAN

+------------------------------------------------------------------------------------------------
+ Incremental Sort
+ Output: t1.a, t1.b, t2.a, t2.b
+ Sort Key: t1.a, t2.a
+ Presorted Key: t1.a
+ -> Merge Join
+ Output: t1.a, t1.b, t2.a, t2.b
+ Merge Cond: (t1.a = ((t3.a + 1)))
+ -> Index Only Scan using semijoin_unique_tbl_a_b_idx on
public.semijoin_unique_tbl t1
+ Output: t1.a, t1.b
+ -> Sort
+ Output: t2.a, t2.b, t3.a, ((t3.a + 1))
+ Sort Key: ((t3.a + 1))
+ -> Hash Join
+ Output: t2.a, t2.b, t3.a, (t3.a + 1)
+ Hash Cond: (t2.a = (t3.b + 1))
+ -> Seq Scan on public.semijoin_unique_tbl t2
+ Output: t2.a, t2.b
+ -> Hash
+ Output: t3.a, t3.b
+ -> HashAggregate
+ Output: t3.a, t3.b
+ Group Key: (t3.a + 1), (t3.b + 1)
+ -> Seq Scan on
public.semijoin_unique_tbl t3
+ Output: t3.a, t3.b, (t3.a + 1),
(t3.b + 1)
+(24 rows)

I was under the impression that we wanted Unique on top of a sorted
node for the inner of the SIMI join. However, the expected output uses
a HashAgg instead. Is this expected?

While looking at the code, I also had a question about the following
changes in costsize.c:

--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -3963,7 +3963,9 @@ final_cost_mergejoin(PlannerInfo *root, MergePath
*path,
* The whole issue is moot if we are working from a unique-ified outer
* input, or if we know we don't need to mark/restore at all.
*/
- if (IsA(outer_path, UniquePath) || path->skip_mark_restore)
+ if (IsA(outer_path, UniquePath) ||
+ IsA(outer_path, AggPath) ||
+ path->skip_mark_restore)

and

@@ -4358,7 +4360,7 @@ final_cost_hashjoin(PlannerInfo *root, HashPath *path,
* because we avoid contaminating the cache with a value that's wrong for
* non-unique-ified paths.
*/
- if (IsA(inner_path, UniquePath))
+ if (IsA(inner_path, UniquePath) || IsA(inner_path, AggPath))

I'm curious why AggPath was added in these two cases. To investigate,
I reverted these two changes regarding AggPath, and reran make
installcheck, and got the following diff:

diff -U3
/Users/alex.wang/workspace/postgres/src/test/regress/expected/subselect.out
/Users/alex.wang/workspace/postgres/src/test/regress/results/subselect.out
---
/Users/alex.wang/workspace/postgres/src/test/regress/expected/subselect.out
2025-07-30 14:47:02
+++
/Users/alex.wang/workspace/postgres/src/test/regress/results/subselect.out
2025-07-30 17:35:33
@@ -747,33 +747,32 @@
select * from semijoin_unique_tbl t1, semijoin_unique_tbl t2
where (t1.a, t2.a) in (select a+1, b+1 from semijoin_unique_tbl t3)
order by t1.a, t2.a;
- QUERY PLAN

-------------------------------------------------------------------------------------------------
- Incremental Sort
+ QUERY PLAN

+------------------------------------------------------------------------------------------------------
+ Merge Join
Output: t1.a, t1.b, t2.a, t2.b
- Sort Key: t1.a, t2.a
- Presorted Key: t1.a
- -> Merge Join
- Output: t1.a, t1.b, t2.a, t2.b
- Merge Cond: (t1.a = ((t3.a + 1)))
+ Merge Cond: ((t3.a + 1) = t1.a)
+ -> Nested Loop
+ Output: t2.a, t2.b, t3.a
+ -> Unique
+ Output: t3.a, t3.b, ((t3.a + 1)), ((t3.b + 1))
+ -> Sort
+ Output: t3.a, t3.b, ((t3.a + 1)), ((t3.b + 1))
+ Sort Key: ((t3.a + 1)), ((t3.b + 1))
+ -> Seq Scan on public.semijoin_unique_tbl t3
+ Output: t3.a, t3.b, (t3.a + 1), (t3.b + 1)
+ -> Memoize
+ Output: t2.a, t2.b
+ Cache Key: (t3.b + 1)
+ Cache Mode: logical
+ -> Index Only Scan using semijoin_unique_tbl_a_b_idx on
public.semijoin_unique_tbl t2
+ Output: t2.a, t2.b
+ Index Cond: (t2.a = (t3.b + 1))
+ -> Materialize
+ Output: t1.a, t1.b
-> Index Only Scan using semijoin_unique_tbl_a_b_idx on
public.semijoin_unique_tbl t1
Output: t1.a, t1.b
- -> Sort
- Output: t2.a, t2.b, t3.a, ((t3.a + 1))
- Sort Key: ((t3.a + 1))
- -> Hash Join
- Output: t2.a, t2.b, t3.a, (t3.a + 1)
- Hash Cond: (t2.a = (t3.b + 1))
- -> Seq Scan on public.semijoin_unique_tbl t2
- Output: t2.a, t2.b
- -> Hash
- Output: t3.a, t3.b
- -> HashAggregate
- Output: t3.a, t3.b
- Group Key: (t3.a + 1), (t3.b + 1)
- -> Seq Scan on
public.semijoin_unique_tbl t3
- Output: t3.a, t3.b, (t3.a + 1),
(t3.b + 1)
-(24 rows)
+(23 rows)

-- encourage use of parallel plans
set parallel_setup_cost=0;
@@ -2818,21 +2817,23 @@
SELECT * FROM tenk1 A INNER JOIN tenk2 B
ON A.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd)
WHERE a.thousand < 750;
- QUERY PLAN
--------------------------------------------------
+ QUERY PLAN
+-------------------------------------------------------------
Hash Join
Hash Cond: (c.odd = b.odd)
- -> Hash Join
- Hash Cond: (a.hundred = c.hundred)
- -> Seq Scan on tenk1 a
- Filter: (thousand < 750)
- -> Hash
- -> HashAggregate
- Group Key: c.odd, c.hundred
- -> Seq Scan on tenk2 c
+ -> Nested Loop
+ -> HashAggregate
+ Group Key: c.odd, c.hundred
+ -> Seq Scan on tenk2 c
+ -> Memoize
+ Cache Key: c.hundred
+ Cache Mode: logical
+ -> Index Scan using tenk1_hundred on tenk1 a
+ Index Cond: (hundred = c.hundred)
+ Filter: (thousand < 750)
-> Hash
-> Seq Scan on tenk2 b
-(12 rows)
+(14 rows)

The second diff looks fine to me. However, the first diff in the
subselect test happened to be the test that I asked about.

Here's the comparison of the two EXPLAIN ANALYZE results:

-- setup:
create table semijoin_unique_tbl (a int, b int);
insert into semijoin_unique_tbl select i%10, i%10 from
generate_series(1,1000)i;
create index on semijoin_unique_tbl(a, b);
analyze semijoin_unique_tbl;

-- query:
EXPLAIN ANALYZE
select * from semijoin_unique_tbl t1, semijoin_unique_tbl t2
where (t1.a, t2.a) in (select a+1, b+1 from semijoin_unique_tbl t3)
order by t1.a, t2.a;

-- results:
Output of your original v5 patch:

QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Incremental Sort (cost=93.94..297.51 rows=2500 width=16) (actual
time=4.153..25.257 rows=90000.00 loops=1)
Sort Key: t1.a, t2.a
Presorted Key: t1.a
Full-sort Groups: 9 Sort Method: quicksort Average Memory: 27kB Peak
Memory: 27kB
Pre-sorted Groups: 9 Sort Method: quicksort Average Memory: 697kB
Peak Memory: 697kB
Buffers: shared hit=61
-> Merge Join (cost=74.81..166.49 rows=2500 width=16) (actual
time=0.964..13.341 rows=90000.00 loops=1)
Merge Cond: (t1.a = ((t3.a + 1)))
Buffers: shared hit=61
-> Index Only Scan using semijoin_unique_tbl_a_b_idx on
semijoin_unique_tbl t1 (cost=0.15..43.08 rows=1000 width=8) (actual
time=0.040..0.276 rows=1000.00 loops=1)
Heap Fetches: 1000
Index Searches: 1
Buffers: shared hit=51
-> Sort (cost=74.66..75.91 rows=500 width=12) (actual
time=0.867..4.366 rows=89901.00 loops=1)
Sort Key: ((t3.a + 1))
Sort Method: quicksort Memory: 53kB
Buffers: shared hit=10
-> Hash Join (cost=27.25..52.25 rows=500 width=12) (actual
time=0.401..0.711 rows=900.00 loops=1)
Hash Cond: (t2.a = (t3.b + 1))
Buffers: shared hit=10
-> Seq Scan on semijoin_unique_tbl t2
(cost=0.00..15.00 rows=1000 width=8) (actual time=0.027..0.106
rows=1000.00 loops=1)
Buffers: shared hit=5
-> Hash (cost=26.00..26.00 rows=100 width=8) (actual
time=0.361..0.361 rows=10.00 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 9kB
Buffers: shared hit=5
-> HashAggregate (cost=25.00..26.00 rows=100
width=8) (actual time=0.349..0.352 rows=10.00 loops=1)
Group Key: (t3.a + 1), (t3.b + 1)
Batches: 1 Memory Usage: 32kB
Buffers: shared hit=5
-> Seq Scan on semijoin_unique_tbl t3
(cost=0.00..20.00 rows=1000 width=16) (actual time=0.012..0.150
rows=1000.00 loops=1)
Buffers: shared hit=5
Planning Time: 0.309 ms
Execution Time: 28.552 ms
(33 rows)

Output of the v5 patch + my modification that removes the changes in
costsize.c about AggPath:

QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Merge Join (cost=70.14..316.44 rows=2500 width=16) (actual
time=0.862..13.484 rows=90000.00 loops=1)
Merge Cond: ((t3.a + 1) = t1.a)
Buffers: shared hit=105 read=6
-> Nested Loop (cost=69.99..227.12 rows=500 width=12) (actual
time=0.778..1.225 rows=900.00 loops=1)
Buffers: shared hit=54 read=6
-> Unique (cost=69.83..77.33 rows=100 width=16) (actual
time=0.685..0.782 rows=10.00 loops=1)
Buffers: shared read=5
-> Sort (cost=69.83..72.33 rows=1000 width=16) (actual
time=0.684..0.723 rows=1000.00 loops=1)
Sort Key: ((t3.a + 1)), ((t3.b + 1))
Sort Method: quicksort Memory: 56kB
Buffers: shared read=5
-> Seq Scan on semijoin_unique_tbl t3
(cost=0.00..20.00 rows=1000 width=16) (actual time=0.324..0.479
rows=1000.00 loops=1)
Buffers: shared read=5
-> Memoize (cost=0.16..2.19 rows=100 width=8) (actual
time=0.010..0.035 rows=90.00 loops=10)
Cache Key: (t3.b + 1)
Cache Mode: logical
Hits: 0 Misses: 10 Evictions: 0 Overflows: 0 Memory
Usage: 36kB
Buffers: shared hit=54 read=1
-> Index Only Scan using semijoin_unique_tbl_a_b_idx on
semijoin_unique_tbl t2 (cost=0.15..2.18 rows=100 width=8) (actual
time=0.005..0.015 rows=90.00 loops=10)
Index Cond: (a = (t3.b + 1))
Heap Fetches: 900
Index Searches: 10
Buffers: shared hit=54 read=1
-> Materialize (cost=0.15..45.58 rows=1000 width=8) (actual
time=0.014..3.613 rows=90001.00 loops=1)
Storage: Memory Maximum Storage: 20kB
Buffers: shared hit=51
-> Index Only Scan using semijoin_unique_tbl_a_b_idx on
semijoin_unique_tbl t1 (cost=0.15..43.08 rows=1000 width=8) (actual
time=0.010..0.126 rows=1000.00 loops=1)
Heap Fetches: 1000
Index Searches: 1
Buffers: shared hit=51
Planning:
Buffers: shared hit=69 read=20
Planning Time: 3.558 ms
Execution Time: 17.211 ms
(34 rows)

While both runs are fast (28ms vs. 17ms), the plan generated by the v5
patch is slower in this case.

The latter plan also seems closer to my expectation: Unique + Sort for
the inner side of the SEMI join.

What do you think?

Best,
Alex