From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: Dean Rasheed <dean.a.rasheed@gmail.com>
Cc: Mark Dilger <hornschnorter@gmail.com>
Cc: Alexander Korotkov <a.korotkov@postgrespro.ru>
Cc: PostgreSQL-development <pgsql-hackers@postgresql.org>
Subject: Re: improving GROUP BY estimation
Date: Fri, 18 Mar 2016 01:37:56 +0100
Message-ID: <715c5c66-5fe1-a9aa-e28d-6c4114ba0fd6@2ndquadrant.com> (raw)
In-Reply-To: <1457906984.27231.16.camel@2ndquadrant.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>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>
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
--
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-v3.patch (binary/octet-stream, 2.7K) downloaddiff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.cindex 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.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, dean.a.rasheed@gmail.com, hornschnorter@gmail.com, a.korotkov@postgrespro.ru
Subject: Re: improving GROUP BY estimation
In-Reply-To: <715c5c66-5fe1-a9aa-e28d-6c4114ba0fd6@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