Re: improving GROUP BY estimation

Hi, Dean!

On Fri, Mar 18, 2016 at 1:20 PM, Dean Rasheed <dean(dot)a(dot)rasheed(at)gmail(dot)com>
wrote:

> 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.
> */
>

+1
Thank you for work on this patch. The formula you propose and explanation
look great!

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company