From: Tomas Vondra <tomas.vondra@enterprisedb.com>
To: Dean Rasheed <dean.a.rasheed@gmail.com>
Cc: Justin Pryzby <pryzby@telsasoft.com>
Cc: PostgreSQL Hackers <pgsql-hackers@postgresql.org>
Subject: Re: PoC/WIP: Extended statistics on expressions
Date: Wed, 17 Mar 2021 22:30:59 +0100
Message-ID: <ce50ee26-7135-c435-cae8-073ad59eba60@enterprisedb.com> (raw)
In-Reply-To: <CAEZATCXcX0gm2LMb+xObroS-C+a5FXEqgR5RgQ9NWKjPC=9sNA@mail.gmail.com>
References: <20210108023537.GA19743@telsasoft.com>
<f865af90-c19c-769e-8c65-19692e245479@enterprisedb.com>
<20210122022958.GC27167@telsasoft.com>
<acf27932-8159-8872-8fca-902c7a35b351@enterprisedb.com>
<CAEZATCXvarTUJthsnoSMzhQwivUqsxGcvSm_5h1L-yNapVyo-g@mail.gmail.com>
<2147e075-fef6-b1d5-e5f5-7f92ffefe827@enterprisedb.com>
<d571f2de-6246-4f6e-ca1d-32cc53a2016a@enterprisedb.com>
<f3820f57-dd45-8ea3-0c46-86629b0c0d41@enterprisedb.com>
<CAEZATCUo1xA4d5e=kXw5E0z7xKEi1oL_aLx=wBGT1A4vdc_gYw@mail.gmail.com>
<1913c1fe-13da-7250-adf4-befeda397536@enterprisedb.com>
<CAEZATCUooH7uPsPkMJEyf-KY_3Om7TTVo7Fo31JiXXgGCb=97g@mail.gmail.com>
<f0f7e00c-7ccb-9412-0147-a06a60777f06@enterprisedb.com>
<CAEZATCWF66BWJq-OwLuP5LGK6W9LDYxCQwLxqB36qmq3b1Ch8Q@mail.gmail.com>
<f4dac079-6bc4-ccc0-0fd8-3e2e2da28d92@enterprisedb.com>
<CAEZATCXz2WO9ZctRL68_HrsPbpre0GRmip83TgznoeLoWm4=Dg@mail.gmail.com>
<CAEZATCXcX0gm2LMb+xObroS-C+a5FXEqgR5RgQ9NWKjPC=9sNA@mail.gmail.com>
On 3/17/21 9:58 PM, Dean Rasheed wrote:
> On Wed, 17 Mar 2021 at 20:48, Dean Rasheed <dean.a.rasheed@gmail.com> wrote:
>>
>> For reference, here is the test case I was using (which isn't really very good for
>> catching dependence between columns):
>>
>
> And here's a test case with much more dependence between the columns:
>
> DROP TABLE IF EXISTS foo;
> CREATE TABLE foo (a int, b int, c int, d int);
> INSERT INTO foo SELECT x%2, x%5, x%10, x%15 FROM generate_series(1,100000) x;
> SELECT COUNT(DISTINCT a) FROM foo; -- 2
> SELECT COUNT(DISTINCT b) FROM foo; -- 5
> SELECT COUNT(DISTINCT c) FROM foo; -- 10
> SELECT COUNT(DISTINCT d) FROM foo; -- 15
> SELECT COUNT(DISTINCT (a+b)) FROM foo; -- 6
> SELECT COUNT(DISTINCT (c+d)) FROM foo; -- 20
> SELECT COUNT(DISTINCT ((a+b),c)) FROM foo; -- 10
> SELECT COUNT(DISTINCT ((a+b),(c+d))) FROM foo; -- 30
>
> -- 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 = 150, Actual = 30
> -- This estimate is ndistinct((a+b),c) * ndistinct(d) = 10*15,
> -- which is much better than ndistinct((a+b)) * ndistinct(c) *
> ndistinct(d) = 6*10*15 = 900
> -- Estimate with no stats = 1500
>
> -- 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 = 120, Actual = 30
> -- This estimate is ndistinct((a+b)) * ndistinct((c+d)) = 6*20
>
> Again, I'd say the current behaviour is pretty good.
>
Thanks!
I agree applying at least the [(a+b),c] stats is probably the right
approach, as it means we're considering at least the available
information about dependence between the columns.
I think to improve this, we'll need to teach the code to use overlapping
statistics, a bit like conditional probability. In this case we might do
something like this:
ndistinct((a+b),c) * (ndistinct((c+d)) / ndistinct(c))
Which in this case would be either, for the "less correlated" case
228 * 24 / 12 = 446 (actual = 478, current estimate = 480)
or, for the "more correlated" case
10 * 20 / 10 = 20 (actual = 30, current estimate = 120)
But that's clearly a matter for a future patch, and I'm sure there are
cases where this will produce worse estimates.
Anyway, I plan to go over the patches one more time, and start pushing
them sometime early next week. I don't want to leave it until the very
last moment in the CF.
regards
--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
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@enterprisedb.com, dean.a.rasheed@gmail.com, pryzby@telsasoft.com
Subject: Re: PoC/WIP: Extended statistics on expressions
In-Reply-To: <ce50ee26-7135-c435-cae8-073ad59eba60@enterprisedb.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