To: PostgreSQL-development <pgsql-hackers@postgresql.org>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Subject: improving GROUP BY estimation
Message-ID: <56CD0381.5060502@2ndquadrant.com>
Date: Wed, 24 Feb 2016 02:12:33 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101
 Thunderbird/38.1.0
MIME-Version: 1.0
Content-Type: multipart/mixed;
 boundary="------------040401030103010005010605"
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org

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

Hi,

while working of using correlation statistics when estimating GROUP BY 
(or generally whatever uses estimate_num_groups), I've noticed that we 
apply the selectivity in a rather naive way.

After estimating number of groups in the whole table - either by reading 
pg_stats.n_distinct for a single column, or multiplying (and doing some 
additional magic) for a group of columns, we do this:

    reldistinct *= rel->rows / rel->tuples;

which essentially applies the selectivity to the ndistinct estimate.

So when you have a table with 1000 distinct values in a column, and we 
read 10% of the table, we expect to get 100 distinct values.

But consider for example the table has 100M rows, that the column has 
n_distinct=10000 and we're reading 1% of the table (i.e. 1M rows). The 
current code will estimate the GROUP BY cardinality to be 100 (as 1% of 
the n_distinct), but in reality we're more likely to see all 10000 
distinct values.

Example:

CREATE TABLE t (a INT, b FLOAT);
INSERT INTO t SELECT (100000 * random())::int, random()
                 FROM generate_series(1,10000000) s(i);
ANALYZE t;

SELECT n_distinct FROM pg_stats WHERE attname = 'a';

  n_distinct
------------
       98882

-- 1% of the table
EXPLAIN ANALYZE SELECT a FROM t WHERE b < 0.01 GROUP BY a;

                                QUERY PLAN
-------------------------------------------------------------------------
  HashAggregate  (cost=179514.33..179523.45 rows=912 width=4)
                 (actual time=916.224..955.136 rows=63492 loops=1)
    Group Key: a
    ->  Seq Scan on t  (cost=0.00..179053.25 rows=92216 width=4)
                       (actual time=0.103..830.104 rows=100268 loops=1)
          Filter: (b < '0.01'::double precision)
          Rows Removed by Filter: 9899732
  Planning time: 1.237 ms
  Execution time: 982.600 ms
(7 rows)

-- 5% of the table
EXPLAIN ANALYZE SELECT a FROM t WHERE b < 0.05 GROUP BY a;

                                 QUERY PLAN
-------------------------------------------------------------------------
  HashAggregate  (cost=180296.06..180345.22 rows=4916 width=4)
                 (actual time=1379.519..1440.005 rows=99348 loops=1)
    Group Key: a
    ->  Seq Scan on t  (cost=0.00..179053.25 rows=497123 width=4)
                       (actual time=0.096..1000.494 rows=500320 loops=1)
          Filter: (b < '0.05'::double precision)
          Rows Removed by Filter: 9499680
  Planning time: 0.129 ms
  Execution time: 1480.986 ms
(7 rows)

This is getting especially bad when reading only a small fraction of a 
huge table - it's easy to construct cases with arbitrarily large error. 
And it's worth noting that the error is almost exclusively massive 
under-estimate, so the "wrong" direction as HashAggregate is still 
vulnerable to OOM (again, the larger the table the worse).

So I think a more appropriate way to estimate this would be to find the 
expected number of distinct values when sampling with replacements, as 
explained for example in [1].

Applied to the code, it means changing the line from

   reldistinct *= rel->rows / rel->tuples;

to

   reldistinct *= (1 - powl((reldistinct - 1) / reldistinct, rel->rows));

With this change, the estimates for the examples look like this:

                                QUERY PLAN
-------------------------------------------------------------------------
  HashAggregate  (cost=179283.79..179883.48 rows=59969 width=4)
                 (actual time=897.071..934.764 rows=63492 loops=1)
    Group Key: a
    ->  Seq Scan on t  (cost=0.00..179053.25 rows=92216 width=4)
                       (actual time=0.104..820.276 rows=100268 loops=1)
          Filter: (b < '0.01'::double precision)
          Rows Removed by Filter: 9899732
  Planning time: 1.261 ms
  Execution time: 962.812 ms
(7 rows)

and

                                 QUERY PLAN
-------------------------------------------------------------------------
  Group  (cost=232886.15..235371.76 rows=98234 width=4)
         (actual time=1519.545..2104.447 rows=99348 loops=1)
    Group Key: a
    ->  Sort  (cost=232886.15..234128.95 rows=497123 width=4)
              (actual time=1519.540..1838.575 rows=500320 loops=1)
          Sort Key: a
          Sort Method: external merge  Disk: 6824kB
          ->  Seq Scan on t  (cost=0.00..179053.25 rows=497123 width=4)
                      (actual time=0.090..1044.099 rows=500320 loops=1)
                Filter: (b < '0.05'::double precision)
                Rows Removed by Filter: 9499680
  Planning time: 0.133 ms
  Execution time: 2147.340 ms
(10 rows)

So much better. Clearly, there are cases where this will over-estimate 
the cardinality - for example when the values are somehow correlated.

But I'd argue over-estimating is better because of the OOM issues in 
Hash Aggregate.

regards

[1] 
http://math.stackexchange.com/questions/72223/finding-expected-number-of-distinct-values-selected-from-a-set-of-integers

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

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

diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.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 *groupExprs, double input_rows,
 				reldistinct = clamp;
 
 			/*
-			 * Multiply by restriction selectivity.
+			 * Estimate number of distinct values expected in given number of rows.
 			 */
-			reldistinct *= rel->rows / rel->tuples;
+			reldistinct *= (1 - powl((reldistinct - 1) / reldistinct, rel->rows));
 
 			/*
 			 * Update estimate of total distinct groups.

--------------040401030103010005010605
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

--------------040401030103010005010605--