Subject: Re: improving GROUP BY estimation
To: Alexander Korotkov <a.korotkov@postgrespro.ru>
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>
 <715c5c66-5fe1-a9aa-e28d-6c4114ba0fd6@2ndquadrant.com>
 <CAEZATCVd9cACCX_fiFSa0sHiUR5JdzrYL_1N79-PYQe9WSaTWA@mail.gmail.com>
 <CAPpHfdvcS+NVHW9b8ijJUEt=iCN6F6sLez87QzT0svqd8GgDVg@mail.gmail.com>
 <CAPpHfdswn19iSnpsukEJiAQSxK63Ewhkae=GDLuWrgvVHRP5jw@mail.gmail.com>
Cc: Mark Dilger <hornschnorter@gmail.com>,
 PostgreSQL-development <pgsql-hackers@postgresql.org>,
 Dean Rasheed <dean.a.rasheed@gmail.com>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <3457190a-29df-8ecc-6208-a780b8faeb64@2ndquadrant.com>
Date: Wed, 30 Mar 2016 15:03:41 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:47.0) Gecko/20100101
 Thunderbird/47.0a2
MIME-Version: 1.0
In-Reply-To: 
 <CAPpHfdswn19iSnpsukEJiAQSxK63Ewhkae=GDLuWrgvVHRP5jw@mail.gmail.com>
Content-Type: multipart/mixed;
 boundary="------------0727417844B022F84AA1AB58"
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org

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

Hi,

On 03/22/2016 03:40 PM, Alexander Korotkov wrote:
>
> I think you should send a revision of patch including comments proposed
> by Deam Rasheed.
> I'm switching patch status to waiting on author in commitfest.
>

Attached is v4 of the patch - the only difference w.r.t. v3 is that I've 
used the comment as proposed by Dean.

regards

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

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

diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index a6555e9..00755da 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -3439,9 +3439,20 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
 				reldistinct = clamp;
 
 			/*
-			 * Multiply by restriction selectivity.
+			 * Update the estimate based on the restriction selectivity.
+			 *
+			 * This uses the formula for the expected number of distinct values
+			 * when selecting with replacement from a collection where each of
+			 * the distinct values occurs an equal number of times (a uniform
+			 * distribution of values). This is a very close approximation to
+			 * the more correct method of selecting without replacement when
+			 * the number of distinct values is quite large --- for example,
+			 * see http://www.adellera.it/investigations/distinct_balls/.
+			 * Additionally, it also turns out to work very well even when the
+			 * number of distinct values is small.
 			 */
-			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);

--------------0727417844B022F84AA1AB58
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

--------------0727417844B022F84AA1AB58--