[PATCH 2/2] 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.
---
src/backend/optimizer/path/costsize.c | 66 +++++++++++++++++++++++----
src/test/regress/expected/join.out | 23 +++++-----
2 files changed, 69 insertions(+), 20 deletions(-)

diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 66c0ad9d..ceb7bf88 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -4435,9 +4435,8 @@ initial_cost_hashjoin(PlannerInfo *root, JoinCostWorkspace *workspace,
}

/*
- * hash_join_joint_ndistinct
- * Estimate the joint ndistinct of the inner-side hash key columns of a
- * multi-clause hash join.
+ * Estimate the number of distinct values of the inner-side hash key, taken as
+ * a whole, for a multi-clause hash join.
*
* The per-clause loop in final_cost_hashjoin() keeps the smallest bucket
* fraction seen for any one clause, i.e. the largest ndistinct of any single
@@ -4448,9 +4447,8 @@ initial_cost_hashjoin(PlannerInfo *root, JoinCostWorkspace *workspace,
* implements exactly that estimate, and unlike a bare product it bounds the
* result by the number of input rows.
*
- * Returns -1.0, which no valid ndistinct can match, when the estimate cannot
- * be formed: fewer than two clauses, a clause whose inner-side operand is
- * not a plain Var of the inner relation, or a non-OpExpr clause.
+ * Returns -1.0 when there is nothing to add: fewer than two clauses, a key
+ * that is not a plain Var of the inner relation, or a non-OpExpr clause.
*/
static double
hash_join_joint_ndistinct(PlannerInfo *root, RelOptInfo *innerrel,
@@ -4794,8 +4792,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);

@@ -5457,6 +5484,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;

@@ -5483,14 +5512,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/join.out b/src/test/regress/expected/join.out
index 9aecac74..f42e54f4 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -12379,15 +12379,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)

@@ -12479,15 +12479,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