Content-Type: text/plain; charset=us-ascii
Mime-Version: 1.0 (Mac OS X Mail 9.2 \(3112\))
Subject: Re: improving GROUP BY estimation
From: Mark Dilger <hornschnorter@gmail.com>
In-Reply-To: <03A3B58D-6A2D-44FE-9B03-E21948CFCBAA@gmail.com>
Date: Thu, 25 Feb 2016 16:19:39 -0800
Cc: PostgreSQL-development <pgsql-hackers@postgresql.org>
Content-Transfer-Encoding: quoted-printable
Message-Id: <B9765D22-4BDC-4764-935C-2CBE329B0455@gmail.com>
References: <56CD0381.5060502@2ndquadrant.com>
 <03A3B58D-6A2D-44FE-9B03-E21948CFCBAA@gmail.com>
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org


> On Feb 25, 2016, at 3:16 PM, Mark Dilger <hornschnorter@gmail.com> wrote:
>=20
>=20
>> On Feb 23, 2016, at 5:12 PM, Tomas Vondra <tomas.vondra@2ndquadrant.com>=
 wrote:
>>=20
>> <snip>
>>=20
>> So much better. Clearly, there are cases where this will over-estimate t=
he cardinality - for example when the values are somehow correlated.
>>=20
>=20
> I applied your patch, which caused a few regression tests to fail.  Attac=
hed
> is a patch that includes the necessary changes to the expected test resul=
ts.
>=20
> It is not hard to write test cases where your patched version overestimat=
es
> 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 demonst=
rate
> this, happens to be one such example:
>=20
>=20
> CREATE TABLE t (a INT, b int);
> INSERT INTO t SELECT sqrt(gs)::int, gs FROM generate_series(1,10000000) g=
s;
> ANALYZE t;
> EXPLAIN SELECT a FROM t WHERE b < 1000 GROUP BY a;
>                          QUERY PLAN
> ---------------------------------------------------------------
> HashAggregate  (cost=3D169250.21..169258.71 rows=3D850 width=3D4)
>   Group Key: a
>   ->  Seq Scan on t  (cost=3D0.00..169247.71 rows=3D1000 width=3D4)
>         Filter: (b < 1000)
> (4 rows)
>=20
> SELECT COUNT(*) FROM (SELECT a FROM t WHERE b < 1000 GROUP BY a) AS ss;
> count=20
> -------=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
>    32
> (1 row)
>=20
>=20
>=20
> 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.
>=20
> As a patch review, I'd say that your patch does what you claim it does, a=
nd 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 a good=
 idea.
>=20
> Mark Dilger
>=20
>=20
> <estimate-num-groups-v2.txt>

Assuming the goal is to minimize the degree to which the estimates are inac=
curate, I=20
get better results by a kind of averaging of the old values from the curren=
t code base
and the new values from Tomas's patch.  I tried this and at least for the f=
ew examples
we've been throwing around, I found the results were not as wildly inaccura=
te in the
worst case examples than in either of the other two approaches:

diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfu=
ncs.c
index 46c95b0..c83135a 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -3414,6 +3414,8 @@ estimate_num_groups(PlannerInfo *root, List *groupExp=
rs, double input_rows,
                Assert(rel->reloptkind =3D=3D RELOPT_BASEREL);
                if (rel->tuples > 0)
                {
+                       double          old_factor;             /* The way =
it is currently done on master */
+                       double          new_factor;             /* The way =
Tomas Vondra proposes doing it */
                        /*
                         * Clamp to size of rel, or size of rel / 10 if mul=
tiple Vars. The
                         * fudge factor is because the Vars are probably co=
rrelated but we
@@ -3440,7 +3442,10 @@ estimate_num_groups(PlannerInfo *root, List *groupEx=
prs, double input_rows,
                        /*
                         * Multiply by restriction selectivity.
                         */
-                       reldistinct *=3D rel->rows / rel->tuples;
+                       old_factor =3D rel->rows / rel->tuples;           /=
* old way */
+                       new_factor =3D (1 - powl((reldistinct - 1) / reldis=
tinct, rel->rows));  /* Tomas's way */
+
+                       reldistinct *=3D sqrt(old_factor * new_factor);   /=
* average of old way and new way, sort of */
=20
                        /*
                         * Update estimate of total distinct groups.


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