Subject: Re: improving GROUP BY estimation
To: Mark Dilger <hornschnorter@gmail.com>
References: <56CD0381.5060502@2ndquadrant.com>
 <03A3B58D-6A2D-44FE-9B03-E21948CFCBAA@gmail.com>
Cc: PostgreSQL-development <pgsql-hackers@postgresql.org>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <56CFA373.3060105@2ndquadrant.com>
Date: Fri, 26 Feb 2016 01:59:31 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101
 Thunderbird/38.1.0
MIME-Version: 1.0
In-Reply-To: <03A3B58D-6A2D-44FE-9B03-E21948CFCBAA@gmail.com>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org

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