Subject: Re: multivariate statistics (v19)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>,
 Michael Paquier <michael.paquier@gmail.com>
References: <5d1d62a6-6228-188c-e079-c1be59942168@2ndquadrant.com>
 <20160409.082146.2151665005996934911.t-ishii@sraoss.co.jp>
 <77be1e99-4f97-9a0c-64b7-472fa0ba4800@2ndquadrant.com>
 <20160410.023757.532440443943028713.t-ishii@sraoss.co.jp>
 <0924a7a9-a219-1366-d3bc-2ddd98bc9269@2ndquadrant.com>
 <CAB7nPqTU40Q5_NSgHVoMJfbyH1HDtqMbFDJ+kwFJSpam35b3Qg@mail.gmail.com>
 <f9a642d7-3ff4-63d1-4fb2-9a260056d3bc@2ndquadrant.com>
Cc: Tatsuo Ishii <ishii@postgresql.org>, Robert Haas <robertmhaas@gmail.com>,
 david@pgmasters.net, Tom Lane <tgl@sss.pgh.pa.us>,
 Alvaro Herrera <alvherre@2ndquadrant.com>, jeff.janes@gmail.com,
 PostgreSQL mailing lists <pgsql-hackers@postgresql.org>
From: Petr Jelinek <petr@2ndquadrant.com>
Message-ID: <3eb2a4b6-911b-29d9-7280-bbf4837acb05@2ndquadrant.com>
Date: Wed, 10 Aug 2016 13:50:49 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
 Thunderbird/45.2.0
MIME-Version: 1.0
In-Reply-To: <f9a642d7-3ff4-63d1-4fb2-9a260056d3bc@2ndquadrant.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org

On 10/08/16 13:33, Tomas Vondra wrote:
> On 08/10/2016 06:41 AM, Michael Paquier wrote:
>> On Wed, Aug 3, 2016 at 10:58 AM, Tomas Vondra
>>> 2) combining multiple statistics
>>>
>>> I think the ability to combine multivariate statistics (covering
>>> different
>>> subsets of conditions) is important and useful, but I'm starting to
>>> think
>>> that the current implementation may not be the correct one (which is
>>> why I
>>> haven't written the SGML docs about this part of the patch series yet).
>>>
>>> Assume there's a table "t" with 3 columns (a, b, c), and that we're
>>> estimating query:
>>>
>>>    SELECT * FROM t WHERE a = 1 AND b = 2 AND c = 3
>>>
>>> but that we only have two statistics (a,b) and (b,c). The current
>>> patch does
>>> about this:
>>>
>>>    P(a=1,b=2,c=3) = P(a=1,b=2) * P(c=3|b=2)
>>>
>>> i.e. it estimates the first two conditions using (a,b), and then
>>> estimates
>>> (c=3) using (b,c) with "b=2" as a condition. Now, this is very
>>> efficient,
>>> but it only works as long as the query contains conditions
>>> "connecting" the
>>> two statistics. So if we remove the "b=2" condition from the query, this
>>> stops working.
>>
>> This is trying to make the algorithm smarter than the user, which is
>> something I'd think we could live without. In this case statistics on
>> (a,c) or (a,b,c) are missing. And what if the user does not want to
>> make use of stats for (a,c) because he only defined (a,b) and (b,c)?
>>
>
> I don't think so. Obviously, if you have statistics covering all the
> conditions - great, we can't really do better than that.
>
> But there's a crucial relation between the number of dimensions of the
> statistics and accuracy of the statistics. Let's say you have statistics
> on 8 columns, and you split each dimension twice to build a histogram -
> that's 256 buckets right there, and we only get ~50% selectivity in each
> dimension (the actual histogram building algorithm is more complex, but
> you get the idea).
>

I think it makes sense to pursue this, but I also think we can easily 
live with not having it in the first version that gets committed and 
doing it as follow-up patch.

-- 
   Petr Jelinek                  http://www.2ndQuadrant.com/
   PostgreSQL Development, 24x7 Support, Training & Services


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers