From: Tom Lane <tgl@sss.pgh.pa.us>
To: Dean Rasheed <dean.a.rasheed@gmail.com>
Cc: Alvaro Herrera <alvherre@2ndquadrant.com>
Cc: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Cc: Alexander Korotkov <a.korotkov@postgrespro.ru>
Cc: Mark Dilger <hornschnorter@gmail.com>
Cc: PostgreSQL-development <pgsql-hackers@postgresql.org>
Subject: Re: improving GROUP BY estimation
Date: Thu, 31 Mar 2016 16:57:58 -0400
Message-ID: <7833.1459457878@sss.pgh.pa.us> (raw)
In-Reply-To: <CAEZATCUMr7nyW+PV1u77X8jtTasCO08GsFjV3CvAtrYEY_cQZQ@mail.gmail.com>
References: <20160331203407.GA162729@alvherre.pgsql>
<7329.1459456853@sss.pgh.pa.us>
<CAEZATCUMr7nyW+PV1u77X8jtTasCO08GsFjV3CvAtrYEY_cQZQ@mail.gmail.com>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>
Dean Rasheed <dean.a.rasheed@gmail.com> writes:
> On 31 March 2016 at 21:40, Tom Lane <tgl@sss.pgh.pa.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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: tgl@sss.pgh.pa.us, dean.a.rasheed@gmail.com, alvherre@2ndquadrant.com, tomas.vondra@2ndquadrant.com, a.korotkov@postgrespro.ru, hornschnorter@gmail.com
Subject: Re: improving GROUP BY estimation
In-Reply-To: <7833.1459457878@sss.pgh.pa.us>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox