Re: BUG #15160: planner overestimates number of rows in join when there are more than 200 rows coming from CTE

Melanie Plageman <melanieplageman@gmail.com> writes:
> This patch applies cleanly and works for the case described in the original
> email. All existing regression tests pass with the addition of the explain plan
> update included in the patch.

Thanks for reviewing!

> I could not devise an example in which the previous method of calculating
> selectivity would have produced a better estimate. However, one question I have
> after thinking through the optimization is the following:
> ...
> To summarize:
> Selectivity Type                  |  if nd1 <= nd2 |   if nd1 > nd2 |
> ----------------------------------|----------------|-----------------
> inner-join selectivity * ntuples2 | ntuples2 / nd2 | ntuples2 / nd1 |
> semi-join selectivity             |              1 |      nd2 / nd1 |

Um, mumble.  Those functions could be using different values of nd2
thanks to the clamping logic near the head of eqjoinsel_semi, so I'm
not sure that the comparison you're making really holds.

> ... why not use the default NDVs number in the semi-join selectivity
> calculation?

Practical experience says that it doesn't work very well; see the thread
I referred to before,
https://www.postgresql.org/message-id/flat/201104112029.14738.uwe@oss4u.com
particularly my comment

::  While I don't have your specific example to try, I did some
::  experimenting with queries of this form, and I noticed that 8.4's
::  heuristic in eqjoinsel_semi() was going completely nuts and estimating
::  that all rows in the lefthand side have join partners (thus, no rows out
::  of the antijoin).  This is because it has stats for one side of the
::  comparison operator but not the other side (the one with the
::  sub-select).  But it's taking the totally-made-up ndistinct estimate for
::  the sub-select at face value.  It needs to be a bit warier I think.

That experience is what led to the "isdefault" checks that exist now
in eqjoinsel_semi.  I don't think that applying a clamp based on
eqjoinsel_inner is sufficient reason to remove those sanity checks.
In particular, even if the clamp removes the possibility of the semijoin
estimate being too high, it doesn't do anything to prevent a too-low
estimate due to using baseless numbers.

> If there is a reason to keep the existing formula, then I have an additional
> question about the proposed selectivity calculation:
>     selec = Min(selec, nd2 * selec_inner);
> When would it be incorrect to instead multiply by inner side NDVs?

I'm confused ... isn't that exactly what this is doing?

> In the function eqjoinsel_semi, on line 2759 of the patched, rebased code,
> could you not move the else condition:
>     uncertainfrac = 0.5;
> Up to the top of the if statement which starts on line 2663:
>     if (have_mcvs1 && have_mcvs2 && OidIsValid(opfuncoid))
> It seems like you already know and do not further modify the value of
> isdefault1 and isdefault2 and could exit faster before looping through all the
> MCVs in this case.

Not really, because we still need to know matchfreq1, so we still have
to do all the comparisons.  It's true that nmatches won't be used in
this case, but I don't see that we can get any meaningful savings by
not computing that.

> For the function eqjoinsel_inner, why pass in vardata1 and vardata2, as they
> appear not to be used? Neither are the isdefault flags.

It just seemed saner to keep the parameter lists similar for
eqjoinsel_inner and eqjoinsel_semi (a judgment call, I admit).
In practice, since there's only one call site for eqjoinsel_inner,
I'd expect it to get inlined so that there's no runtime cost anyway.

> This is in the existing code, however, I thought I would ask here:
> In eqjoinsel_semi, on line 2691 of the patched, rebased code, Why is this the
> min of the number of MCVs captured and the distinct values? It seems like if
> clamping resulted in an NDVs that is too low (i.e. impossibly low since the
> number of distinct values cannot be less than the number of MCVs), then you
> should bump it up to at least the number of MCVs:
>     clamped_nvalues2 = Min(sslot2->nvalues, nd2);

No, because sslot2->nvalues is the number of distinct values that ANALYZE
found in the whole table.  If nd2 got clamped to less than that, it's
because we have a WHERE clause that is filtering the table down to fewer
rows than there are distinct values in the table, so we can be sure
(at least, up to the reliability of the WHERE estimate) that not all of
the recorded MCVs are going to be present in the rows being joined.
We don't know which ones will be present, but it seems like a reasonable
bet that the most common ones will be present.  Since the list is already
ordered by decreasing frequency, just taking the first N of them gets us
that.  You could imagine trying to refine that, say by reducing the
number further to allow for some of the join input rows containing
non-MCVs, but I don't see an argument for increasing it.

> I also found the new comment added above the new selectivity calculation to be
> a little bit confusing:
>             /*
>              * We should never estimate the output of a semijoin to be more
>              * rows than the equivalent inner join; it's obviously impossible
>              * for that to happen.  The former is N1 * Psemi while the latter
>              * is N1 * N2 * Pinner, so we may clamp Psemi <= N2 * Pinner.
>              * Doing this is worthwhile because of the shakier estimation
>              * rules we use in eqjoinsel_semi, particularly in cases where it
>              * has to punt entirely.
>              */
>             selec = Min(selec, inner_rel->rows * selec_inner);

> After re-reading it several times, I understood what it
> was doing, however, it would be ideal if somehow the relationship between
> selectivity and cardinality were more clear.

Hm.  Maybe the "Psemi" and "Pinner" notation is not helpful ... would
"Ssemi" and "Sinner" be better?

            regards, tom lane