From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: Alexander Korotkov <a.korotkov@postgrespro.ru>
Cc: Mark Dilger <hornschnorter@gmail.com>
Cc: PostgreSQL-development <pgsql-hackers@postgresql.org>
Cc: Dean Rasheed <dean.a.rasheed@gmail.com>
Subject: Re: improving GROUP BY estimation
Date: Wed, 30 Mar 2016 15:03:41 +0200
Message-ID: <3457190a-29df-8ecc-6208-a780b8faeb64@2ndquadrant.com> (raw)
In-Reply-To: <CAPpHfdswn19iSnpsukEJiAQSxK63Ewhkae=GDLuWrgvVHRP5jw@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>
<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>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>
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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackersAttachments:estimate-num-groups-v4.patch (binary/octet-stream, 3.2K) downloaddiff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.cindex 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.outindex 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);
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, a.korotkov@postgrespro.ru, hornschnorter@gmail.com, dean.a.rasheed@gmail.com
Subject: Re: improving GROUP BY estimation
In-Reply-To: <3457190a-29df-8ecc-6208-a780b8faeb64@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