Subject: Re: PoC/WIP: Extended statistics on expressions
To: Dean Rasheed <dean.a.rasheed@gmail.com>
Cc: Justin Pryzby <pryzby@telsasoft.com>,
 PostgreSQL Hackers <pgsql-hackers@postgresql.org>
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>
From: Tomas Vondra <tomas.vondra@enterprisedb.com>
Message-ID: <ce50ee26-7135-c435-cae8-073ad59eba60@enterprisedb.com>
Date: Wed, 17 Mar 2021 22:30:59 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101
 Thunderbird/78.8.0
MIME-Version: 1.0
In-Reply-To: 
 <CAEZATCXcX0gm2LMb+xObroS-C+a5FXEqgR5RgQ9NWKjPC=9sNA@mail.gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Archived-At: 
 <https://www.postgresql.org/message-id/ce50ee26-7135-c435-cae8-073ad59eba60%40enterprisedb.com>
Precedence: bulk


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