Hi,

Attached is v2.

Changes since v1:
- Rebased onto master 11591f273e6a (2026-11-17).
- Update contrib/pg_plan_advice/expected/gather.out: the corrected
  costing changes the plan recorded there from a parallel hash join to
  a merge join. make check and check-world pass with the update.

The costing logic itself is unchanged.

Regards,
He Kuang
From 3d62a3b9f7fd680e43acb24779a9654ea451e687 Mon Sep 17 00:00:00 2001
From: He Kuang <[email protected]>
Date: Tue, 17 Nov 2026 21:51:17 +0800
Subject: [PATCH v2] Fix hash join costing when the inner side is provably
 unique

compute_semi_anti_join_factors() is called for any join whose inner side
is provably unique -- a plain inner join, and equally a LEFT, RIGHT or
FULL join -- because the executor stops at the first match and the
fraction of outer rows that find a match is then what the cost model
wants, just as for a semi join.  It asks clauselist_selectivity() for the
semi-join selectivity, but hands it the SpecialJoinInfo of the actual
join, and eqjoinsel() decides what it is being asked from
sjinfo->jointype plus min_lefthand/righthand -- not from the jointype
argument alone.  With a non-SEMI sjinfo the answer is the ordinary
equality selectivity: the fraction of the Cartesian product that matches,
not the fraction of outer rows that find a match.

For a unique inner side the two differ by the size of the inner relation.
An outer relation of 1,200,000 rows joined to a 100,000-row unique inner
relation gets outer_match_frac = 1e-5 instead of 1 (taking the outer
key's ndistinct to be no larger than the inner's, as holds for a
foreign-key reference).  The join's row estimate is fine -- EXPLAIN
prints rows = 1,200,418 for this node -- but the cost side of the same
node charges the per-output-tuple CPU work on hashjointuples = 12,
pricing 1,200,000 output tuples as if there were 12: a
five-orders-of-magnitude understatement of that term, enough to hide a
merge join that is cheaper to execute.

Ask with a SpecialJoinInfo that describes the same join as a SEMI join.

There is a second half to this.  outer_matched_rows is exact for a real
SEMI or ANTI join, where it *is* the output.  For a plain inner join it is
not: what leaves the join is the joinrel row estimate, which is what every
other node in the plan is built on.  The two agree when the semi-join
question is asked correctly and there is a single hash clause; they need
not agree otherwise, because eqjoinsel_semi() takes the minimum over the
clauses while calc_joinrel_size_estimate() multiplies them.  So charge the
output tuples on the joinrel row count for inner joins.  For the outer
join types keep charging outer_matched_rows: the fix above already
corrects that number for them -- their outer_match_frac was subject to
the same bug -- but what a LEFT or FULL join emits on top of the matched
rows is a different question, deliberately left alone here.

contrib/pg_plan_advice records the plans chosen for a join whose inner
side is unique, so the corrected cost changes those plans as well: the
parallel hash join in gather.out becomes a merge join.  Update that
expected output accordingly.
---
 contrib/pg_plan_advice/expected/gather.out | 63 +++++++++++-----------
 src/backend/optimizer/path/costsize.c      | 56 ++++++++++++++++++-
 src/test/regress/expected/aggregates.out   | 32 ++++++-----
 src/test/regress/expected/join.out         | 23 ++++----
 4 files changed, 113 insertions(+), 61 deletions(-)

diff --git a/contrib/pg_plan_advice/expected/gather.out 
b/contrib/pg_plan_advice/expected/gather.out
index 60f2b32e24f..1032e618bb8 100644
--- a/contrib/pg_plan_advice/expected/gather.out
+++ b/contrib/pg_plan_advice/expected/gather.out
@@ -26,48 +26,50 @@ VACUUM ANALYZE gt_part;
 -- By default, we expect Gather Merge with a parallel hash join.
 EXPLAIN (COSTS OFF, PLAN_ADVICE)
        SELECT * FROM gt_fact f JOIN gt_dim d ON f.dim_id = d.id ORDER BY d.id;
-                      QUERY PLAN                       
--------------------------------------------------------
+                    QUERY PLAN                    
+--------------------------------------------------
  Gather Merge
    Workers Planned: 1
-   ->  Sort
-         Sort Key: f.dim_id
-         ->  Parallel Hash Join
-               Hash Cond: (f.dim_id = d.id)
+   ->  Merge Join
+         Merge Cond: (f.dim_id = d.id)
+         ->  Sort
+               Sort Key: f.dim_id
                ->  Parallel Seq Scan on gt_fact f
-               ->  Parallel Hash
-                     ->  Parallel Seq Scan on gt_dim d
+         ->  Sort
+               Sort Key: d.id
+               ->  Seq Scan on gt_dim d
  Generated Plan Advice:
    JOIN_ORDER(f d)
-   HASH_JOIN(d)
+   MERGE_JOIN_PLAIN(d)
    SEQ_SCAN(f d)
    GATHER_MERGE((f d))
-(14 rows)
+(15 rows)
 
 -- Force Gather or Gather Merge of both relations together.
 BEGIN;
 SET LOCAL pg_plan_advice.advice = 'gather_merge((f d))';
 EXPLAIN (COSTS OFF, PLAN_ADVICE)
        SELECT * FROM gt_fact f JOIN gt_dim d ON f.dim_id = d.id ORDER BY d.id;
-                      QUERY PLAN                       
--------------------------------------------------------
+                    QUERY PLAN                    
+--------------------------------------------------
  Gather Merge
    Workers Planned: 1
-   ->  Sort
-         Sort Key: f.dim_id
-         ->  Parallel Hash Join
-               Hash Cond: (f.dim_id = d.id)
+   ->  Merge Join
+         Merge Cond: (f.dim_id = d.id)
+         ->  Sort
+               Sort Key: f.dim_id
                ->  Parallel Seq Scan on gt_fact f
-               ->  Parallel Hash
-                     ->  Parallel Seq Scan on gt_dim d
+         ->  Sort
+               Sort Key: d.id
+               ->  Seq Scan on gt_dim d
  Supplied Plan Advice:
    GATHER_MERGE((f d)) /* matched */
  Generated Plan Advice:
    JOIN_ORDER(f d)
-   HASH_JOIN(d)
+   MERGE_JOIN_PLAIN(d)
    SEQ_SCAN(f d)
    GATHER_MERGE((f d))
-(16 rows)
+(17 rows)
 
 SET LOCAL pg_plan_advice.advice = 'gather((f d))';
 EXPLAIN (COSTS OFF, PLAN_ADVICE)
@@ -355,26 +357,27 @@ BEGIN;
 SET LOCAL pg_plan_advice.advice = 'gather((f d)) no_gather(f)';
 EXPLAIN (COSTS OFF, PLAN_ADVICE)
        SELECT * FROM gt_fact f JOIN gt_dim d ON f.dim_id = d.id ORDER BY d.id;
-                      QUERY PLAN                       
--------------------------------------------------------
+                     QUERY PLAN                     
+----------------------------------------------------
  Gather Merge
    Workers Planned: 1
-   ->  Sort
-         Sort Key: f.dim_id
-         ->  Parallel Hash Join
-               Hash Cond: (f.dim_id = d.id)
+   ->  Merge Join
+         Merge Cond: (f.dim_id = d.id)
+         ->  Sort
+               Sort Key: f.dim_id
                ->  Parallel Seq Scan on gt_fact f
-               ->  Parallel Hash
-                     ->  Parallel Seq Scan on gt_dim d
+         ->  Sort
+               Sort Key: d.id
+               ->  Seq Scan on gt_dim d
  Supplied Plan Advice:
    GATHER((f d)) /* matched, conflicting, failed */
    NO_GATHER(f) /* matched, conflicting, failed */
  Generated Plan Advice:
    JOIN_ORDER(f d)
-   HASH_JOIN(d)
+   MERGE_JOIN_PLAIN(d)
    SEQ_SCAN(f d)
    GATHER_MERGE((f d))
-(17 rows)
+(18 rows)
 
 COMMIT;
 -- Test interaction of NO_GATHER with partitioned tables.  By default, we
diff --git a/src/backend/optimizer/path/costsize.c 
b/src/backend/optimizer/path/costsize.c
index f760ef9aa3a..11e57333966 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -4710,8 +4710,37 @@ final_cost_hashjoin(PlannerInfo *root, HashPath *path,
                                                                           (1.0 
- extra->semifactors.outer_match_frac));
        else if (path->jpath.jointype == JOIN_ANTI)
                hashjointuples = outer_path_rows - outer_matched_rows;
-       else if (path->jpath.jointype == JOIN_SEMI || extra->inner_unique)
+       else if (path->jpath.jointype == JOIN_SEMI)
                hashjointuples = outer_matched_rows;
+       else if (extra->inner_unique)
+       {
+               if (path->jpath.jointype == JOIN_INNER)
+               {
+                       /*
+                        * A plain inner join with a provably unique inner side 
stops at the
+                        * first match, but the tuples it emits are the join's 
output, i.e.
+                        * the joinrel row estimate that every other node in 
the plan is
+                        * built on.  outer_matched_rows agrees with that when 
the semi-join
+                        * question is asked correctly and there is a single 
hash clause; it
+                        * need not agree otherwise, since eqjoinsel_semi() 
takes the
+                        * minimum over the clauses while the join size estimate
+                        * multiplies them.  Charge the join's own row 
estimate, so the
+                        * output count priced here is the same one the rest of 
the plan
+                        * is built on.
+                        */
+                       hashjointuples = path->jpath.path.rows;
+               }
+               else
+               {
+                       /*
+                        * Outer joins: what they emit is not the matched outer 
rows
+                        * either (a FULL join also emits unmatched inner 
rows), but
+                        * correcting that is a separate question, so keep the 
old
+                        * estimate.
+                        */
+                       hashjointuples = outer_matched_rows;
+               }
+       }
        else
                hashjointuples = approx_tuple_count(root, &path->jpath, 
hashclauses);
 
@@ -5373,6 +5402,8 @@ compute_semi_anti_join_factors(PlannerInfo *root,
        Selectivity nselec;
        Selectivity avgmatch;
        SpecialJoinInfo norm_sjinfo;
+       SpecialJoinInfo semi_sjinfo;
+       SpecialJoinInfo *sel_sjinfo;
        List       *joinquals;
        ListCell   *l;
 
@@ -5399,14 +5430,35 @@ compute_semi_anti_join_factors(PlannerInfo *root,
 
        /*
         * Get the JOIN_SEMI or JOIN_ANTI selectivity of the join clauses.
+        *
+        * eqjoinsel() decides whether it is being asked a semi-join question 
from
+        * sjinfo->jointype and sjinfo->min_lefthand/righthand, not from its
+        * jointype argument alone.  The caller can be any join whose inner side
+        * is proven unique -- a plain inner join, or a LEFT, RIGHT or FULL join
+        * (see add_paths_to_joinrel) -- and the sjinfo we get describes that
+        * join, not a semi join, so the answer we get back is the ordinary
+        * equality selectivity -- the fraction of the Cartesian product that
+        * matches, not the fraction of outer rows that find a match.  Build a
+        * SpecialJoinInfo that describes the same join as a SEMI join before
+        * asking, so that jselec means what the rest of this function and its
+        * callers assume it means.
         */
+       sel_sjinfo = sjinfo;
+       if (jointype != JOIN_SEMI && jointype != JOIN_ANTI &&
+               jointype != JOIN_RIGHT_SEMI && jointype != JOIN_RIGHT_ANTI)
+       {
+               init_dummy_sjinfo(&semi_sjinfo, outerrel->relids, 
innerrel->relids);
+               semi_sjinfo.jointype = JOIN_SEMI;
+               sel_sjinfo = &semi_sjinfo;
+       }
+
        jselec = clauselist_selectivity(root,
                                                                        
joinquals,
                                                                        0,
                                                                        
(jointype == JOIN_ANTI ||
                                                                         
jointype == JOIN_RIGHT_ANTI) ?
                                                                        
JOIN_ANTI : JOIN_SEMI,
-                                                                       sjinfo);
+                                                                       
sel_sjinfo);
 
        /*
         * Also get the normal inner-join selectivity of the join clauses, to
diff --git a/src/test/regress/expected/aggregates.out 
b/src/test/regress/expected/aggregates.out
index 275263c293f..408c0ebdbf5 100644
--- a/src/test/regress/expected/aggregates.out
+++ b/src/test/regress/expected/aggregates.out
@@ -1645,31 +1645,29 @@ explain (costs off) select a,c from t1 group by a,c,d;
 explain (costs off) select *
 from t1 inner join t2 on t1.a = t2.x and t1.b = t2.y
 group by t1.a,t1.b,t1.c,t1.d,t2.x,t2.y,t2.z;
-                      QUERY PLAN                      
-------------------------------------------------------
- HashAggregate
+                      QUERY PLAN                       
+-------------------------------------------------------
+ Group
    Group Key: t1.a, t1.b
-   ->  Hash Join
-         Hash Cond: ((t2.x = t1.a) AND (t2.y = t1.b))
-         ->  Seq Scan on t2
-         ->  Hash
-               ->  Seq Scan on t1
-(7 rows)
+   ->  Merge Join
+         Merge Cond: ((t1.a = t2.x) AND (t1.b = t2.y))
+         ->  Index Scan using t1_pkey on t1
+         ->  Index Scan using t2_pkey on t2
+(6 rows)
 
 -- Test case where t1 can be optimized but not t2
 explain (costs off) select t1.*,t2.x,t2.z
 from t1 inner join t2 on t1.a = t2.x and t1.b = t2.y
 group by t1.a,t1.b,t1.c,t1.d,t2.x,t2.z;
-                      QUERY PLAN                      
-------------------------------------------------------
+                      QUERY PLAN                       
+-------------------------------------------------------
  HashAggregate
    Group Key: t1.a, t1.b, t2.z
-   ->  Hash Join
-         Hash Cond: ((t2.x = t1.a) AND (t2.y = t1.b))
-         ->  Seq Scan on t2
-         ->  Hash
-               ->  Seq Scan on t1
-(7 rows)
+   ->  Merge Join
+         Merge Cond: ((t1.a = t2.x) AND (t1.b = t2.y))
+         ->  Index Scan using t1_pkey on t1
+         ->  Index Scan using t2_pkey on t2
+(6 rows)
 
 -- Cannot optimize when PK is deferrable
 explain (costs off) select * from t3 group by a,b,c;
diff --git a/src/test/regress/expected/join.out 
b/src/test/regress/expected/join.out
index 526430a5ea0..76961fab8c7 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -12626,15 +12626,15 @@ select * from fkest f1
                      QUERY PLAN                      
 -----------------------------------------------------
  Hash Join
-   Hash Cond: ((f2.x = f1.x) AND (f2.x10b = f1.x10))
+   Hash Cond: ((f1.x = f2.x) AND (f1.x10 = f2.x10b))
    ->  Hash Join
-         Hash Cond: (f3.x = f2.x)
+         Hash Cond: (f3.x = f1.x)
          ->  Seq Scan on fkest f3
          ->  Hash
-               ->  Seq Scan on fkest f2
+               ->  Seq Scan on fkest f1
                      Filter: (x100 = 2)
    ->  Hash
-         ->  Seq Scan on fkest f1
+         ->  Seq Scan on fkest f2
                Filter: (x100 = 2)
 (11 rows)
 
@@ -12726,15 +12726,14 @@ select * from j1 inner join j3 on j1.id = j3.id;
 -----------------------------------
  Hash Join
    Output: j1.id, j3.id
-   Inner Unique: true
-   Hash Cond: (j3.id = j1.id)
-   ->  Seq Scan on public.j3
-         Output: j3.id
-   ->  Hash
+   Hash Cond: (j1.id = j3.id)
+   ->  Seq Scan on public.j1
          Output: j1.id
-         ->  Seq Scan on public.j1
-               Output: j1.id
-(10 rows)
+   ->  Hash
+         Output: j3.id
+         ->  Seq Scan on public.j3
+               Output: j3.id
+(9 rows)
 
 -- ensure left join is marked as unique
 explain (verbose, costs off)
-- 
2.43.0

Reply via email to