Subject: Re: improving GROUP BY estimation
To: Dean Rasheed <dean.a.rasheed@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>
 <1457906984.27231.16.camel@2ndquadrant.com>
Cc: Mark Dilger <hornschnorter@gmail.com>,
 Alexander Korotkov <a.korotkov@postgrespro.ru>,
 PostgreSQL-development <pgsql-hackers@postgresql.org>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <715c5c66-5fe1-a9aa-e28d-6c4114ba0fd6@2ndquadrant.com>
Date: Fri, 18 Mar 2016 01:37:56 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:46.0) Gecko/20100101
 Thunderbird/46.0a2
MIME-Version: 1.0
In-Reply-To: <1457906984.27231.16.camel@2ndquadrant.com>
Content-Type: multipart/mixed;
 boundary="------------6FE268C615142A79024ABE54"
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org

This is a multi-part message in MIME format.
--------------6FE268C615142A79024ABE54
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit

On 03/13/2016 11:09 PM, Tomas Vondra wrote:
> 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:
>>>
...
 >>>
>>
>> I think that a better formula to use would be
>>
>> reldistinct *= (1 - powl(1 - rel-rows / rel->tuples, rel->tuples /
>> reldistinct)

Attached is a v3 of the patch using this formula instead of the original 
one. Interestingly, that apparently reduces the number of regression 
tests that get broken to a single one.

I'm not sure whether we need to provide a link to the PDF the formula 
comes from - perhaps we should?

I've also repeated the tests for the two tables (dependent and 
independent columns), comparing the actual number of groups and 
different estimates, and the results look like this (v3 is the formula 
used in this patch):


1) independent

                |   10 |   50 |  100 |  500 |  1000 |  5000
    ---------------------------------------------------------
         actual |  919 | 3829 | 6244 | 9944 | 10001 | 10001
        current |   10 |   50 |  102 |  516 |  1018 |  4996
       new (v1) |  973 | 4001 | 6382 | 9897 |  9951 |  9951
       new (v3) | 1117 | 3852 | 6229 | 9943 | 10004 | 10004


2) dependent

                 |  10 |   50 |  100 |  500 |  1000 |  5000
      --------------------------------------------------------
          actual |  10 |   50 |  100 |  500 |  1000 |  5000
         current |  10 |   53 |  105 |  508 |  1016 |  5014
        new (v1) | 880 | 4105 | 6472 | 9955 | 10018 | 10018
        new (v3) | 807 | 3680 | 6050 | 9916 |  9983 |  9983

I only collected numbers for the new estimator, the other numbers are 
just a copy from the previous message. So there might be minor 
differences due to slightly different ndistinct estimates etc.

Anyway, the numbers are obviously quite close to the formula from v1 of 
the patch, plus the formula gives better estimates when scanning nearly 
all rows.

regards

-- 
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

--------------6FE268C615142A79024ABE54
Content-Type: binary/octet-stream;
 name="estimate-num-groups-v3.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
 filename="estimate-num-groups-v3.patch"

diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index d396ef1..3630469 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -3439,9 +3439,12 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
 				reldistinct = clamp;
 
 			/*
-			 * Multiply by restriction selectivity.
+			 * Estimate the number of groups observed in the expected number of
+			 * rows, using a formula for selection without replacement, assuming
+			 * uniform distribution.
 			 */
-			reldistinct *= rel->rows / rel->tuples;
+			reldistinct *= (1 - powl(1 - rel->rows / rel->tuples,
+									 rel->tuples / reldistinct));
 
 			/*
 			 * Update estimate of total distinct groups.
diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out
index de64ca7..0fc93d9 100644
--- a/src/test/regress/expected/subselect.out
+++ b/src/test/regress/expected/subselect.out
@@ -807,27 +807,24 @@ select * from int4_tbl where
 explain (verbose, costs off)
 select * from int4_tbl o where (f1, f1) in
   (select f1, generate_series(1,2) / 10 g from int4_tbl i group by f1);
-                              QUERY PLAN                              
-----------------------------------------------------------------------
- Hash Join
+                           QUERY PLAN                           
+----------------------------------------------------------------
+ Hash Semi Join
    Output: o.f1
    Hash Cond: (o.f1 = "ANY_subquery".f1)
    ->  Seq Scan on public.int4_tbl o
          Output: o.f1
    ->  Hash
          Output: "ANY_subquery".f1, "ANY_subquery".g
-         ->  HashAggregate
+         ->  Subquery Scan on "ANY_subquery"
                Output: "ANY_subquery".f1, "ANY_subquery".g
-               Group Key: "ANY_subquery".f1, "ANY_subquery".g
-               ->  Subquery Scan on "ANY_subquery"
-                     Output: "ANY_subquery".f1, "ANY_subquery".g
-                     Filter: ("ANY_subquery".f1 = "ANY_subquery".g)
-                     ->  HashAggregate
-                           Output: i.f1, (generate_series(1, 2) / 10)
-                           Group Key: i.f1
-                           ->  Seq Scan on public.int4_tbl i
-                                 Output: i.f1
-(18 rows)
+               Filter: ("ANY_subquery".f1 = "ANY_subquery".g)
+               ->  HashAggregate
+                     Output: i.f1, (generate_series(1, 2) / 10)
+                     Group Key: i.f1
+                     ->  Seq Scan on public.int4_tbl i
+                           Output: i.f1
+(15 rows)
 
 select * from int4_tbl o where (f1, f1) in
   (select f1, generate_series(1,2) / 10 g from int4_tbl i group by f1);

--------------6FE268C615142A79024ABE54
Content-Type: text/plain
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
MIME-Version: 1.0


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

--------------6FE268C615142A79024ABE54--