Horton

Re: PoC/WIP: Extended statistics on expressions

Dean Rasheed <dean.a.rasheed@gmail.com>

View thread View on postgr.es
From: Dean Rasheed <dean.a.rasheed@gmail.com>
To: Tomas Vondra <tomas.vondra@enterprisedb.com>
Cc: Justin Pryzby <pryzby@telsasoft.com>, PostgreSQL Hackers <pgsql-hackers@postgresql.org>
Date: 2021-03-17T20:48:51Z
Lists: pgsql-hackers 
On Wed, 17 Mar 2021 at 19:07, Tomas Vondra
<tomas.vondra@enterprisedb.com> wrote:
>
> On 3/17/21 7:54 PM, Dean Rasheed wrote:
> >
> > it might have been better to estimate the first case as
> >
> >      ndistinct((a+b)) * ndistinct(c) * ndistinct(d)
> >
> > and the second case as
> >
> >      ndistinct((a+b)) * ndistinct((c+d))
>
> OK. I might be confused, but isn't that what the algorithm currently
> does? Or am I just confused about what the first/second case refers to?
>

No, it currently estimates the first case as ndistinct((a+b),c) *
ndistinct(d). Having said that, maybe that's OK after all. It at least
makes an effort to account for any correlation between (a+b) and
(c+d), using the known correlation between (a+b) and c. For reference,
here is the test case I was using (which isn't really very good for
catching dependence between columns):

DROP TABLE IF EXISTS foo;
CREATE TABLE foo (a int, b int, c int, d int);
INSERT INTO foo SELECT x%10, x%11, x%12, x%13 FROM generate_series(1,100000) x;
SELECT COUNT(DISTINCT a) FROM foo; -- 10
SELECT COUNT(DISTINCT b) FROM foo; -- 11
SELECT COUNT(DISTINCT c) FROM foo; -- 12
SELECT COUNT(DISTINCT d) FROM foo; -- 13
SELECT COUNT(DISTINCT (a+b)) FROM foo; -- 20
SELECT COUNT(DISTINCT (c+d)) FROM foo; -- 24
SELECT COUNT(DISTINCT ((a+b),c)) FROM foo; -- 228
SELECT COUNT(DISTINCT ((a+b),(c+d))) FROM foo; -- 478

-- First case: stats on [(a+b),c]
CREATE STATISTICS s1(ndistinct) ON (a+b),c FROM foo;
ANALYSE foo;
EXPLAIN ANALYSE
SELECT (a+b), (c+d) FROM foo GROUP BY (a+b), (c+d);
  -- Estimate = 2964, Actual = 478
  -- This estimate is ndistinct((a+b),c) * ndistinct(d) = 228*13

-- Second case: stats on (c+d) as well
CREATE STATISTICS s2 ON (c+d) FROM foo;
ANALYSE foo;
EXPLAIN ANALYSE
SELECT (a+b), (c+d) FROM foo GROUP BY (a+b), (c+d);
  -- Estimate = 480, Actual = 478
  -- This estimate is ndistinct((a+b)) * ndistinct((c+d)) = 20*24

I think that's probably pretty reasonable behaviour, given incomplete
stats (the estimate with no extended stats is capped at 10000).

Regards,
Dean

Commits

  1. Disallow extended statistics on system columns

  2. Identify simple column references in extended statistics

  3. Don't print extra parens around expressions in extended stats

  4. Change position of field "transformed" in struct CreateStatsStmt.

  5. Add transformed flag to nodes/*funcs.c for CREATE STATISTICS

  6. Stabilize stats_ext test with other collations

  7. Extended statistics on expressions

  8. Reduce duration of stats_ext regression tests

  9. Allow composite types in catalog bootstrap

  10. Convert Typ from array to list in bootstrap

  11. Disallow CREATE STATISTICS on system catalogs