Re: improving GROUP BY estimation

On 18 March 2016 at 00:37, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com> wrote:
>> On Sun, 2016-03-13 at 15:24 +0000, Dean Rasheed wrote:
>>> I think that a better formula to use would be
>>>
>>> reldistinct *= (1 - powl(1 - rel-rows / rel->tuples, rel->tuples /
>>> reldistinct)
>
> Attached is a v3 of the patch using this formula instead of the original
> one. Interestingly, that apparently reduces the number of regression tests
> that get broken to a single one.
>

Cool.

> I'm not sure whether we need to provide a link to the PDF the formula comes
> from - perhaps we should?
>

Probably a better URL to give is
http://www.adellera.it/investigations/distinct_balls/ which has a link
to the PDF version of the paper and also some supporting material.

However, while that paper is in general very clear, I don't think it
gives a very clear explanation of that particular formula, and it
doesn't explain what it represents. It merely says that if "i" can be
ignored "for some reason (e.g. i << Nr)", then that formula is an
approximation to the exact "without replacement" formula, which is the
subject of that paper.

But actually, that formula is the exact formula for the expected
number of distinct values when selecting *with replacement* from a
collection where each of the distinct values occurs an equal number of
times. So I think we should say that.

Perhaps something along the lines of:

/*
* Update the estimate based on the restriction selectivity.
*
* This uses the formula for the expected number of distinct values
* when selecting with replacement from a collection where each of
* the distinct values occurs an equal number of times (a uniform
* distribution of values). This is a very close approximation to
* the more correct method of selecting without replacement when
* the number of distinct values is quite large --- for example,
* see http://www.adellera.it/investigations/distinct_balls/.
* Additionally, it also turns out to work very well even when the
* number of distinct values is small.
*/

Regards,
Dean