From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: Mark Dilger <hornschnorter@gmail.com>
Cc: PostgreSQL-development <pgsql-hackers@postgresql.org>
Subject: Re: improving GROUP BY estimation
Date: Fri, 26 Feb 2016 01:59:31 +0100
Message-ID: <56CFA373.3060105@2ndquadrant.com> (raw)
In-Reply-To: <03A3B58D-6A2D-44FE-9B03-E21948CFCBAA@gmail.com>
References: <56CD0381.5060502@2ndquadrant.com>
<03A3B58D-6A2D-44FE-9B03-E21948CFCBAA@gmail.com>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>
Hi,
On 02/26/2016 12:16 AM, Mark Dilger wrote:
>
> It is not hard to write test cases where your patched version overestimates
> the number of rows by a very similar factor as the old code underestimates
> them. My very first test, which was not specifically designed to demonstrate
> this, happens to be one such example:
>
>
> CREATE TABLE t (a INT, b int);
> INSERT INTO t SELECT sqrt(gs)::int, gs FROM generate_series(1,10000000) gs;
> ANALYZE t;
> EXPLAIN SELECT a FROM t WHERE b < 1000 GROUP BY a;
> QUERY PLAN
> ---------------------------------------------------------------
> HashAggregate (cost=169250.21..169258.71 rows=850 width=4)
> Group Key: a
> -> Seq Scan on t (cost=0.00..169247.71 rows=1000 width=4)
> Filter: (b < 1000)
> (4 rows)
>
> SELECT COUNT(*) FROM (SELECT a FROM t WHERE b < 1000 GROUP BY a) AS ss;
> count
> -------
> 32
> (1 row)
>
>
>
> So, it estimates 850 rows where only 32 are returned . Without
> applying your patch, it estimates just 1 row where 32 are returned.
> That's an overestimate of roughly 26 times, rather than an
> underestimate of 32 times.
The culprit here is that the two columns are not independent, but are
(rather strongly) correlated due to the way you've generated the data.
In cases like this (with correlated columns), it's mostly just luck how
accurate estimates you get, no matter which of the estimators you use.
It's pretty easy to generate arbitrary errors by breaking the
independence assumption, and it's not just this particular place of the
planner. And it won't change until we add some sort of smartness about
dependencies between columns.
I think over-estimates are a bit more acceptable in this case, e.g.
because of the HashAggregate OOM risk. Also, I've seen too many nested
loop cascades due to under-estimates recently, but that's a bit unrelated.
> As a patch review, I'd say that your patch does what you claim it
> does, and it applies cleanly, and passes the regression tests with
> my included modifications. I think there needs to be some discussion
> on the list about whether the patch is agood idea.
Yes, that's why I haven't bothered with fixing the regression tests in
the patch, actually.
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, hornschnorter@gmail.com
Subject: Re: improving GROUP BY estimation
In-Reply-To: <56CFA373.3060105@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