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

David Rowley <david(dot)rowley(at)2ndquadrant(dot)com> writes:
> On 14 September 2018 at 05:57, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> Yeah. This evidently got broken sometime during v10 development,
>> because 9.6 and below generate a more reasonable cost:

> This seems to be a result of using the semifactors.outer_match_frac in
> final_cost_hashjoin(). This is calculated to be very low @
> 3.3333333333333335e-05, which results in outer_matched_rows being set
> to 0 in:

So after poking around for awhile, my conclusion is that the cost
estimation aspects of the inner_unique patch are completely broken,
and it's not going to be very easy to fix.

The core issue here is that compute_semi_anti_join_factors was never
designed to work for any joins that aren't really SEMI or ANTI joins,
and just taking out the assert about that doesn't fix it. In
particular, passing jointype == JOIN_SEMI to clauselist_selectivity,
when the underlying sjinfo has jointype == JOIN_INNER, isn't a supported
combination. If you look at eqjoinsel() you will notice that it pays
no attention at all to the jointype parameter, only to sjinfo->jointype.
Therefore what we get out of the first clauselist_selectivity is the
same value as we get from the second one (ie, inner-join selectivity)
leading to entirely insane results from compute_semi_anti_join_factors.

There are more problems though. If you change eqjoinsel() to look at
the jointype parameter, you get a cost estimate of around 4000, which
is because outer_match_frac gets set to 0.16667, which is better but
still not exactly good. The reason for that is that eqjoinsel_semi
punts (due to lack of any stats for the generate_series RTE) and
returns 0.5, and likewise we get a default estimate of 0.33333 from
the inequality on the expensive_func result, so 0.16667 is the
combined jselec estimate. So the default estimate from eqjoinsel_semi
is unrelated to the default estimate from eqjoinsel_inner, which is
unhelpful for what we're doing here, plus scalargtjoinsel didn't
adjust its behavior at all. We have, in fact, not really built out
the semijoin estimation infrastructure anywhere except eqjoinsel and
neqjoinsel (though I see somebody made it work for networkjoinsel).
This is mostly tolerable for the purposes of real SEMI and ANTI joins,
because it's relatively hard/unusual for those to have join quals that
aren't equality quals. But if you expect that infrastructure to give
you sane results for random other joins, you're going to be sorely
disappointed.

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.

So my conclusion here is that we probably ought to revert the changes
in compute_semi_anti_join_factors that made it not reject other join
types, and that unique_inner cases need some other cost estimation
mechanism that doesn't depend on pretending that a join is a SEMI
join when it isn't.

(Another, longer-term project is to rationalize the situation with
joinsel functions getting jointype parameters that are different
from sjinfo->jointype. The cases where that can happen are pretty
random and underdocumented, and to the extent that there's any
guidance at all, it's the comment at the head of selfuncs.c that
says it's better to ignore jointype in favor of sjinfo->jointype.
So I'd not be very much on board with just changing eqjoinsel
even if that were enough to fix this completely --- we'd need to
take a very hard look at a bunch of cases to figure out what behavior
we really want the estimators to have. In the end it might be best to
just refuse to allow those values to be different.)

regards, tom lane