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

Melanie Plageman <melanieplageman(at)gmail(dot)com> writes:
> On a separate note, I had one additional code clarity feedback. I felt that
> eqjoinsel could be reorganized a bit for readability/clarity for the reader.
> ...
> Based on this assumption, I've attached a patch with a rough idea for an
> alternative structure that I think would be more clear to the reader.

Hmm, that doesn't really seem like an improvement to me. As things stand,
all the actual calculations are in eqjoinsel_inner/semi; eqjoinsel itself
is only responsible for some preliminary information lookup that's needed
in all cases. My patch expands the amount of "preliminary information"
but doesn't fundamentally change that division of responsibility. It
seems like what you want to do here does change that, and I don't see
the value of breaking down the division. I also don't like the fact
that we might calculate a value that won't be used; admittedly, it's a
pretty cheap calculation so that doesn't matter much, but by the same
token we'd not be saving a lot of code by moving it.

> That's a good point. Taking another look at that clamping logic, I
> realized that I don't really understand why that clamping would be done
> for a semi-join and not for an inner join. It seems like for an inner
> join it is also true that the the nd1 cannot be greater than outer rel
> estimated tuples and nd2 could not be greater than inner rel estimated
> tuples.

The main way that eqjoinsel_inner uses those values is this bit:

* We do not have MCV lists for both sides. Estimate the join
* selectivity as MIN(1/nd1,1/nd2)*(1-nullfrac1)*(1-nullfrac2). This
* is plausible if we assume that the join operator is strict and the
* non-null values are about equally distributed: a given non-null
* tuple of rel1 will join to either zero or N2*(1-nullfrac2)/nd2 rows
* of rel2, so total join rows are at most
* N1*(1-nullfrac1)*N2*(1-nullfrac2)/nd2 giving a join selectivity of
* not more than (1-nullfrac1)*(1-nullfrac2)/nd2.

In the expression N2*(1-nullfrac2)/nd2, all three values are meant to be
measured across the whole of the rel2 relation; if we were to decrease nd2
to reflect the effects of earlier filtering, we'd get an incorrect
selectivity. The same applies to eqjoinsel_semi's calculations about the
outer rel, but *not* to the inner rel, as explained here:

* We clamp nd2 to be not more than what we estimate the inner relation's
* size to be. This is intuitively somewhat reasonable since obviously
* there can't be more than that many distinct values coming from the
* inner rel. The reason for the asymmetry (ie, that we don't clamp nd1
* likewise) is that this is the only pathway by which restriction clauses
* applied to the inner rel will affect the join result size estimate,
* since set_joinrel_size_estimates will multiply SEMI/ANTI selectivity by
* only the outer rel's size. If we clamped nd1 we'd be double-counting
* the selectivity of outer-rel restrictions.

(Here, both "outer rel's size" and "inner rel's size" mean the size after
earlier filtering steps.) So that's why we only clamp nd2 and only do so
in eqjoinsel_semi: in the other three cases, we'd be double-counting the
selectivity of earlier filters if we did that.

So basically the inconsistency here comes from the fact that we define
the meaning of join selectivity differently for inner and semi joins.
I've occasionally wondered if that was a bad choice and we should just
say that selectivity should always be calculated so that the join size
is outer size times inner size times selectivity. But that would
certainly not make for any less need for the selectivity estimator to
do things differently for inner and semi joins, so I am not seeing much
upside to changing it.

> Also, I don't understand when vardata2->rel->rows and inner_rel->rows would
> be different.

vardata2->rel->rows is going to reflect the size (post restriction quals)
of the base relation that var2 came from. inner_rel->rows will be the
same if the inner side of the current join is just that one base relation;
but if the inner side is a lower join of several base relations,
inner_rel->rows will be the size of that join.

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

> Sorry, typo, I was asking why
> selec = Min(selec, nd2 * selec_inner);
> could not be used instead of what is in the patch
> selec = Min(selec, inner_rel->rows * selec_inner);

Because the selectivity is defined as something you multiply the relation
size with, not the number of distinct values within the rel.

regards, tom lane