From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: Dean Rasheed <dean.a.rasheed@gmail.com>
Cc: Mark Dilger <hornschnorter@gmail.com>
Cc: Alexander Korotkov <a.korotkov@postgrespro.ru>
Cc: PostgreSQL-development <pgsql-hackers@postgresql.org>
Subject: Re: improving GROUP BY estimation
Date: Sun, 13 Mar 2016 23:09:44 +0100
Message-ID: <1457906984.27231.16.camel@2ndquadrant.com> (raw)
In-Reply-To: <CAEZATCU3hhRjGbvCydP-i3ik4FGX9OcXsK2ZG5TGuVnJOvb=kg@mail.gmail.com>
References: <56CD0381.5060502@2ndquadrant.com>
<03A3B58D-6A2D-44FE-9B03-E21948CFCBAA@gmail.com>
<56CFA373.3060105@2ndquadrant.com>
<7D1A65E8-7ED8-4268-9C24-8EA07E95D2BC@gmail.com>
<56CFCE96.5080306@2ndquadrant.com>
<CAPpHfdtEiXqj52kuGMEnw6EShrzj-0tFYwwxPqzdFvxYfCr+tQ@mail.gmail.com>
<56D867C3.3040309@2ndquadrant.com>
<904EB795-BCDD-4D68-8D44-274B40C4B2E9@gmail.com>
<56D88D93.5000509@2ndquadrant.com>
<CAPpHfdvOBwfGQ_F6Nk+eKF0e2Bx4Z_esg7==8KAjKqP6+5-ahA@mail.gmail.com>
<E00A6146-D40C-4E4E-92B2-D6F5017F9B19@gmail.com>
<1457097036.24980.28.camel@2ndquadrant.com>
<CAEZATCU3hhRjGbvCydP-i3ik4FGX9OcXsK2ZG5TGuVnJOvb=kg@mail.gmail.com>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>
Hi,
On Sun, 2016-03-13 at 15:24 +0000, Dean Rasheed wrote:
> On 4 March 2016 at 13:10, Tomas Vondra <tomas.vondra@2ndquadrant.com>
> wrote:
> >
> > The risk associated with over-estimation is that we may switch from
> > HashAggregate to GroupAggregate, and generally select paths better
> > suited for large number of rows. Not great, because the plan may
> > not be
> > optimal and thus run much slower - but that usually only happens on
> > small tables, because on large tables we would probably end up
> > using
> > those same paths anyway.
> >
> > With under-estimation, the main risks are much graver, as we may
> > end up
> > using HashAggregate only to get killed by OOM. When we're lucky not
> > to
> > hit that, my experience this often leads to a cascade of NestedLoop
> > nodes processing orders of magnitude more tuples than expected.
> > Awful.
> >
> > So I think the risk is asymmetric, and that's why I like the new
> > estimator more, because it tends to over-estimate, but in a very
> > reasonable way.
> >
> Agreed. Under-estimating is worse than over-estimating.
>
>
> - reldistinct *= rel->rows / rel->tuples;
> + reldistinct *= (1 - powl((reldistinct - 1) / reldistinct,
> rel->rows)
>
> Looking at this, I agree that this new formula from [1] is generally
> better than the old one in most (but not all) cases.
>
> One problem with it is that it no longer takes into account
> rel->tuples, which means that when returning all the tuples from the
> table, it no longer gives an estimate equal to the total number of
> distinct values in the table. In fact it tends to underestimate when
> returning nearly all the rows from the table.
Yes, that's a good point.
>
> The old formula is clearly not a good general-purpose estimate.
> However, there is one case where it does return an accurate estimate
> -- when all the values in the underlying table are distinct. In this
> case the new formula consistently produces underestimates, while the
> old formula works well. For example:
>
> CREATE TABLE t AS SELECT (100000000 * random())::int a,
> i::int b
> FROM generate_series(1,1000000) s(i);
> ANALYSE t;
>
> EXPLAIN ANALYSE
> SELECT a FROM t GROUP BY a;
>
> So there are clearly around 1 million distinct values for "a", but
> the new formula gives an estimate of around 630,000. That's not a
> massive underestimate, but it's sufficiently obvious and visible that
> it would be good to do better if we can.
>
>
> I think that a better formula to use would be
>
> reldistinct *= (1 - powl(1 - rel-rows / rel->tuples, rel->tuples /
> reldistinct)
>
> This comes from [2], which gives a general formula for selection
> without replacement, and then gives the above as an approximation to
> the uniform distribution case. It's not really made clear in that
> paper, but that approximation is actually the "with replacement"
> approximation, but starting from different initial assumptions to
> give a formula that has better boundary conditions and special-case
> behaviour, as described below.
>
> ...
>
> For most values of N and n, the approximation from [2] is almost
> indistinguishable from the exact formula, whereas the formula from
> [1] tends to underestimate when selecting a large number of distinct
> values (e.g., try setting n=900000 in the plot above).
Yes, I agree that formula you propose seems to behave better.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
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: tomas.vondra@2ndquadrant.com, dean.a.rasheed@gmail.com, hornschnorter@gmail.com, a.korotkov@postgrespro.ru
Subject: Re: improving GROUP BY estimation
In-Reply-To: <1457906984.27231.16.camel@2ndquadrant.com>
* 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