Re: improving GROUP BY estimation

Dean Rasheed <dean(dot)a(dot)rasheed(at)gmail(dot)com> writes:
> On 31 March 2016 at 21:40, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> Let's use something like this:
>> See "Approximating block accesses in database organizations", S. B. Yao,
>> Communications of the ACM, Volume 20 Issue 4, April 1977 Pages 260-261

Actually, having now looked at both the Dellera paper and the Yao one,
what the latter shows seems to be equivalent to Dellera's equation (2)
(the first one in his section 2.2). But what the code is actually
using is the approximation in the second equation in 2.2, and that
one is certainly not in Yao, although it's not hard to see how you
get from the first to the second if you assume i << Nr.

I think it'd be worth writing out equation (2), attributing it to the Yao
paper, and then saying something like "Alberto Dellera points out that if
Nd is large, so that all the values of i are much less than Nr, then this
formula can be approximated by [the formula used in the code]. It turns
out that that formula also works well even when Nd is small."

regards, tom lane