Re: BUG #15383: Join Filter cost estimation problem in 10.5

David Rowley <david.rowley@2ndquadrant.com> writes:
> I've attached a patch which is a partial revert of the costing code
> that was changed in 9c7f5229ad6.

I've spent some time thinking about this (sorry for the delay).
I don't think I like doing what you suggest here.  While it makes
Marko's example better, it will make other cases worse, because
it effectively causes the planner not to give any cost preference
to inner_unique plans.  That means it'll sometimes choose another
plan over a plan making use of inner_unique when we don't want it
to.  So that's not very nice, and it definitely makes me not want
to back-patch this: people aren't that happy with back-patching
plan-destabilizing changes even when we think they are 100% wins.

So what I'm wondering about is if we can't fix
compute_semi_anti_join_factors() to produce something sane without
trying to apply JOIN_SEMI estimation mode to non-semijoins.  It
only has to compute two things, and match_count seems pretty
trivial: it's 1 by definition for an inner_unique case.  All we
need is a rule for computing outer_match_frac.

I experimented with the attached, which estimates outer_match_frac
as joinrel size divided by outer rel size, relying on the knowledge
that no outer row matches more than one inner row.  This makes
Marko's case better, but it's not completely better: it underestimates
the cost of the expensive function by 3X compared to what pre-v10 did.
That is due to the point I made upthread:

>> Also worth noting here is that it's wrong in the first place to be
>> including the selectivity of the inequality qual in our calculation
>> of how many rows are going to be fed to the inequality qual :-(.
>> Again, the infrastructure involved isn't really broken for its
>> designed purpose, because with a normal semijoin there aren't any
>> filter quals to be considered separately; but that assumption breaks
>> down when you try to use that infrastructure for a regular join that
>> happens to have a unique inner side.

We're including the estimated selectivity of the expensive_func qual in
our estimate of how many rows will be fed to the expensive function :-(.

It's not easy to make this better, though: the places that use
outer_match_frac aren't really drawing a distinction between filter
quals and quals that relate to the uniqueness property, and that's
what we'd need in order to have a sane estimate here.  Nor does
compute_semi_anti_join_factors have any idea which quals are which.

I think we'd have to redesign those cost calculations completely to
get ideal answers, and I don't especially want to do that right now.
So I'm wondering about the attached as a stopgap.  It seems like it's
an improvement over what we have, even if not a full fix.

(BTW, another point is that the executor is also imperfect here:
it will keep scanning if the "expensive_func(gs1.i + gs2.i) > 0"
qual fails, though it could stop, because the inner_unique property
is not dependent on that qual.)

Notes:

* For ease of review, I didn't reindent the body of
compute_semi_anti_join_factors, though it'd need it.

* The one join.sql test case that changes plan seems to need a redesign;
the new plan is correct, but it seems like it's not testing what its
comment says it's for.

Thoughts?

            regards, tom lane

diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 4b9be13..fcdccf1 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -4078,7 +4078,7 @@ get_restriction_qual_cost(PlannerInfo *root, RelOptInfo *baserel,
  *    joinrel: join relation under consideration
  *    outerrel: outer relation under consideration
  *    innerrel: inner relation under consideration
- *    jointype: if not JOIN_SEMI or JOIN_ANTI, we assume it's inner_unique
+ *    jointype: if not JOIN_SEMI or JOIN_ANTI, must be an inner_unique case
  *    sjinfo: SpecialJoinInfo relevant to this join
  *    restrictlist: join quals
  * Output parameters:
@@ -4101,14 +4101,16 @@ compute_semi_anti_join_factors(PlannerInfo *root,
     List       *joinquals;
     ListCell   *l;

+    /* We have to do this differently for semi/anti joins vs. inner_unique */
+    if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+    {
     /*
      * In an ANTI join, we must ignore clauses that are "pushed down", since
      * those won't affect the match logic.  In a SEMI join, we do not
      * distinguish joinquals from "pushed down" quals, so just use the whole
-     * restrictinfo list.  For other outer join types, we should consider only
-     * non-pushed-down quals, so that this devolves to an IS_OUTER_JOIN check.
+     * restrictinfo list.
      */
-    if (IS_OUTER_JOIN(jointype))
+    if (jointype == JOIN_ANTI)
     {
         joinquals = NIL;
         foreach(l, restrictlist)
@@ -4128,7 +4130,7 @@ compute_semi_anti_join_factors(PlannerInfo *root,
     jselec = clauselist_selectivity(root,
                                     joinquals,
                                     0,
-                                    (jointype == JOIN_ANTI) ? JOIN_ANTI : JOIN_SEMI,
+                                    jointype,
                                     sjinfo);

     /*
@@ -4155,7 +4157,7 @@ compute_semi_anti_join_factors(PlannerInfo *root,
                                     &norm_sjinfo);

     /* Avoid leaking a lot of ListCells */
-    if (IS_OUTER_JOIN(jointype))
+    if (jointype == JOIN_ANTI)
         list_free(joinquals);

     /*
@@ -4178,6 +4180,21 @@ compute_semi_anti_join_factors(PlannerInfo *root,
     }
     else
         avgmatch = 1.0;
+    }
+    else
+    {
+        /*
+         * Must be an inner_unique case.  match_count is 1 by definition, and
+         * we can compute outer_match_frac as joinrel size / outerrel size.
+         * For paranoia's sake, clamp that to 0..1.
+         */
+        if (outerrel->rows > 0)
+            jselec = joinrel->rows / outerrel->rows;
+        else
+            jselec = 1.0;
+        CLAMP_PROBABILITY(jselec);
+        avgmatch = 1.0;
+    }

     semifactors->outer_match_frac = jselec;
     semifactors->match_count = avgmatch;
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 593aec2..b58ca75 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -5712,15 +5712,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)