Content-Type: multipart/mixed;
 boundary="Apple-Mail=_9A596657-155C-4CE3-8612-5EF4863A8469"
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: <56CD0381.5060502@2ndquadrant.com>
Date: Thu, 25 Feb 2016 15:16:05 -0800
Cc: PostgreSQL-development <pgsql-hackers@postgresql.org>
Message-Id: <03A3B58D-6A2D-44FE-9B03-E21948CFCBAA@gmail.com>
References: <56CD0381.5060502@2ndquadrant.com>
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org


--Apple-Mail=_9A596657-155C-4CE3-8612-5EF4863A8469
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=us-ascii


> 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 th=
e cardinality - for example when the values are somehow correlated.
>=20

I applied your patch, which caused a few regression tests to fail.  Attached
is a patch that includes the necessary changes to the expected test results.

It is not hard to write test cases where your patched version overestimates
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 demonstra=
te
this, happens to be one such example:


CREATE TABLE t (a INT, b int);
INSERT INTO t SELECT sqrt(gs)::int, gs FROM generate_series(1,10000000) gs;
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)

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)


So, it estimates 850 rows where only 32 are returned .  Without applying yo=
ur patch,
it estimates just 1 row where 32 are returned.  That's an overestimate of r=
oughly 26 times,
rather than an underestimate of 32 times.

As a patch review, I'd say that your patch does what you claim it does, and=
 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 i=
dea.

Mark Dilger


--Apple-Mail=_9A596657-155C-4CE3-8612-5EF4863A8469
Content-Disposition: attachment;
	filename=estimate-num-groups-v2.txt
Content-Type: text/plain;
	name="estimate-num-groups-v2.txt"
Content-Transfer-Encoding: quoted-printable

diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfu=
ncs.c
index 46c95b0..82a7f7f 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -3438,9 +3438,9 @@ estimate_num_groups(PlannerInfo *root, List *groupExp=
rs, double input_rows,
 				reldistinct =3D clamp;
=20
 			/*
-			 * Multiply by restriction selectivity.
+			 * Estimate number of distinct values expected in given number of rows.
 			 */
-			reldistinct *=3D rel->rows / rel->tuples;
+			reldistinct *=3D (1 - powl((reldistinct - 1) / reldistinct, rel->rows));
=20
 			/*
 			 * Update estimate of total distinct groups.
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected=
/join.out
index 59d7877..d9dd5ca 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -3951,17 +3951,17 @@ select d.* from d left join (select * from b group =
by b.id, b.c_id) s
   on d.a =3D s.id;
               QUERY PLAN=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
 ---------------------------------------
- Merge Left Join
-   Merge Cond: (d.a =3D s.id)
-   ->  Sort
-         Sort Key: d.a
-         ->  Seq Scan on d
+ Merge Right Join
+   Merge Cond: (s.id =3D d.a)
    ->  Sort
          Sort Key: s.id
          ->  Subquery Scan on s
                ->  HashAggregate
                      Group Key: b.id
                      ->  Seq Scan on b
+   ->  Sort
+         Sort Key: d.a
+         ->  Seq Scan on d
 (11 rows)
=20
 -- similarly, but keying off a DISTINCT clause
@@ -3970,17 +3970,17 @@ select d.* from d left join (select distinct * from=
 b) s
   on d.a =3D s.id;
                  QUERY PLAN=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=
=20=20=20
 ---------------------------------------------
- Merge Left Join
-   Merge Cond: (d.a =3D s.id)
-   ->  Sort
-         Sort Key: d.a
-         ->  Seq Scan on d
+ Merge Right Join
+   Merge Cond: (s.id =3D d.a)
    ->  Sort
          Sort Key: s.id
          ->  Subquery Scan on s
                ->  HashAggregate
                      Group Key: b.id, b.c_id
                      ->  Seq Scan on b
+   ->  Sort
+         Sort Key: d.a
+         ->  Seq Scan on d
 (11 rows)
=20
 -- check join removal works when uniqueness of the join condition is enfor=
ced
diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/exp=
ected/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=20=20=20=20=20=20=20=20=20=20=20=
=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
-----------------------------------------------------------------------
- Hash Join
+                           QUERY PLAN=20=20=20=20=20=20=20=20=20=20=20=20=
=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
+----------------------------------------------------------------
+ Hash Semi Join
    Output: o.f1
    Hash Cond: (o.f1 =3D "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 =3D "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 =3D "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)
=20
 select * from int4_tbl o where (f1, f1) in
   (select f1, generate_series(1,2) / 10 g from int4_tbl i group by f1);
diff --git a/src/test/regress/expected/union.out b/src/test/regress/expecte=
d/union.out
index 016571b..f2e297e 100644
--- a/src/test/regress/expected/union.out
+++ b/src/test/regress/expected/union.out
@@ -263,16 +263,16 @@ ORDER BY 1;
 SELECT q2 FROM int8_tbl INTERSECT SELECT q1 FROM int8_tbl;
         q2=20=20=20=20=20=20=20=20
 ------------------
- 4567890123456789
               123
+ 4567890123456789
 (2 rows)
=20
 SELECT q2 FROM int8_tbl INTERSECT ALL SELECT q1 FROM int8_tbl;
         q2=20=20=20=20=20=20=20=20
 ------------------
+              123
  4567890123456789
  4567890123456789
-              123
 (3 rows)
=20
 SELECT q2 FROM int8_tbl EXCEPT SELECT q1 FROM int8_tbl ORDER BY 1;
@@ -305,16 +305,16 @@ SELECT q1 FROM int8_tbl EXCEPT SELECT q2 FROM int8_tb=
l;
 SELECT q1 FROM int8_tbl EXCEPT ALL SELECT q2 FROM int8_tbl;
         q1=20=20=20=20=20=20=20=20
 ------------------
- 4567890123456789
               123
+ 4567890123456789
 (2 rows)
=20
 SELECT q1 FROM int8_tbl EXCEPT ALL SELECT DISTINCT q2 FROM int8_tbl;
         q1=20=20=20=20=20=20=20=20
 ------------------
+              123
  4567890123456789
  4567890123456789
-              123
 (3 rows)
=20
 SELECT q1 FROM int8_tbl EXCEPT ALL SELECT q1 FROM int8_tbl FOR NO KEY UPDA=
TE;
@@ -343,8 +343,8 @@ SELECT f1 FROM float8_tbl EXCEPT SELECT f1 FROM int4_tb=
l ORDER BY 1;
 SELECT q1 FROM int8_tbl INTERSECT SELECT q2 FROM int8_tbl UNION ALL SELECT=
 q2 FROM int8_tbl;
         q1=20=20=20=20=20=20=20=20=20
 -------------------
-  4567890123456789
                123
+  4567890123456789
                456
   4567890123456789
                123
@@ -355,15 +355,15 @@ SELECT q1 FROM int8_tbl INTERSECT SELECT q2 FROM int8=
_tbl UNION ALL SELECT q2 FR
 SELECT q1 FROM int8_tbl INTERSECT (((SELECT q2 FROM int8_tbl UNION ALL SEL=
ECT q2 FROM int8_tbl)));
         q1=20=20=20=20=20=20=20=20
 ------------------
- 4567890123456789
               123
+ 4567890123456789
 (2 rows)
=20
 (((SELECT q1 FROM int8_tbl INTERSECT SELECT q2 FROM int8_tbl))) UNION ALL =
SELECT q2 FROM int8_tbl;
         q1=20=20=20=20=20=20=20=20=20
 -------------------
-  4567890123456789
                123
+  4567890123456789
                456
   4567890123456789
                123
@@ -419,8 +419,8 @@ HINT:  There is a column named "q2" in table "*SELECT* =
2", but it cannot be refe
 SELECT q1 FROM int8_tbl EXCEPT (((SELECT q2 FROM int8_tbl ORDER BY q2 LIMI=
T 1)));
         q1=20=20=20=20=20=20=20=20
 ------------------
- 4567890123456789
               123
+ 4567890123456789
 (2 rows)
=20
 --

--Apple-Mail=_9A596657-155C-4CE3-8612-5EF4863A8469
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

--Apple-Mail=_9A596657-155C-4CE3-8612-5EF4863A8469--