Re: Selectivity estimation for inet operators

On 09/07/2014 07:09 PM, Emre Hasegeli wrote:
>>>> I updated the patch to cover semi and anti joins with eqjoinsel_semi().
>>>> I think it is better than returning a constant.
>>>
>>> What you did there is utterly unacceptable from a modularity standpoint;
>>> and considering that the values will be nowhere near right, the argument
>>> that "it's better than returning a constant" seems pretty weak. I think
>>> you should just take that out again.
>>
>> I will try to come up with a better, data type specific implementation
>> in a week.
>
> New version with semi join estimation function attached.

Thanks. Overall, my impression of this patch is that it works very well.
But damned if I understood *how* it works :-). There's a lot of
statistics involved, and it's not easy to see why something is
multiplied by something else. I'm adding comments as I read through it.

I've gotten to the inet_semi_join_selec function:

> /*
> * Inet semi join selectivity estimation.
> */
> static Selectivity
> inet_semi_join_selec(bool mcv2_exists, Datum *mcv2_values, int mcv2_nvalues,
> bool his2_exists, Datum *his2_values, int his2_nvalues,
> double his2_weight, Datum *constvalue,
> FmgrInfo *proc, short opr_order)
> {
> if (mcv2_exists)
> {
> int i;
>
> for (i = 0; i < mcv2_nvalues; i++)
> {
> if (DatumGetBool(FunctionCall2Coll(proc, DEFAULT_COLLATION_OID,
> *constvalue, mcv2_values[i])))
> return 1.0;
> }
> }
>
> /* Do not bother if histogram weight is smaller than 0.1. */
> if (his2_exists && his2_weight > 0.1)
> {
> Selectivity his_selec;
>
> his_selec = inet_his_inclusion_selec(his2_values, his2_nvalues,
> constvalue, opr_order);
>
> if (his_selec > 0)
> return Min(1.0, his2_weight * his_selec);
> }
>
> return 0.0;
> }

This desperately needs comment at the top of the function explaining
what it does. Let me try to explain what I think it does:

This function calculates the probability that there is at least one row
in table B, which satisfies the "constant op column" qual. The constant
is passed as argument, and for table B, the MCV list and histogram is
provided. his2_weight is the total number of rows in B that are covered
by the histogram. For example, if the table has 1000 rows, and 10% of
the rows in the table are in the MCV, and another 10% are NULLs,
his_weight would be 800.

First, we check if the constant matches any of the most common values.
If it does, return 1.0, because then there is surely a match.

Next, we use the histogram to estimate the number of rows in the table
that matches the qual. If it amounts to more than 1 row, we return 1.0.
If it's between 0.0 and 1.0 rows, we return that number as the probability.

Now, I think that last step is wrong. Firstly, the "Do not bother if
histogram weight is smaller than 0.1" rule seems bogus. The his2_weight
is the total number of rows represented by the histogram, so surely it
can't be less than 1. It can't really be less than the statistics
target. Unless maybe if the histogram was collected when the table was
large, but it has since shrunk to contain only a few rows, but that
seems like a very bizarre corner case. At least it needs more comments
explaining what the test is all about, but I think we should just always
use the histogram (if it's available).

Secondly, if we estimate that there is on average 1.0 matching row in
the table, it does not follow that the probability that at least one row
matches is 1.0. Assuming a gaussian distribution with mean 1.0, the
probability that at least one row matches is 0.5. Assuming a gaussian
distribution here isn't quite right - I guess a Poisson distribution
would be more accurate - but it sure doesn't seem right as it is.

The error isn't very big, and perhaps you don't run into that very
often, so I'm not sure what the best way to fix that would be. My
statistics skills are a bit rusty, but I think the appropriate way would
be to apply the Poisson distribution, with the estimated number of
matched rows as the mean. The probability of at least one match would be
the cumulative distribution function at k=1. It sounds like overkill, if
this is case occurs only rarely. But then again, perhaps it's not all
that rare.

That said, I can't immediately find a test case where that error would
matter. I tried this:

create table inettbl1 (a inet);
insert into inettbl1 select '10.0.0.' || (g % 255) from
generate_series(1, 10) g;
analyze inettbl1;
explain analyze select count(*) from inettbl1 where a >>= ANY (SELECT a
from inettbl1);

The estimate for that is pretty accurate, 833 rows estimated vs 1000
actual, with the current patch. I'm afraid if we fixed
inet_semi_join_selec the way I suggest, the estimate would be smaller,
i.e. more wrong. Is there something else in the estimates that
accidentally compensates for this currently?

Thoughts?

- Heikki