Message-ID: <543C2C4C.6040800@fuzzy.cz>
Date: Mon, 13 Oct 2014 21:47:24 +0200
From: Tomas Vondra <tv@fuzzy.cz>
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
 rv:31.0) Gecko/20100101 Thunderbird/31.1.1
MIME-Version: 1.0
To: pgsql-hackers@postgresql.org
Subject: Re: WIP: multivariate statistics / proof of concept
References: <543AFA15.4080608@fuzzy.cz>
 <A737B7A37273E048B164557ADEF4A58B17D73648@ntex2010a.host.magwien.gv.at>
In-Reply-To: 
 <A737B7A37273E048B164557ADEF4A58B17D73648@ntex2010a.host.magwien.gv.at>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org

Hi!

On 13.10.2014 09:36, Albe Laurenz wrote:
> Tomas Vondra wrote:
>> attached is a WIP patch implementing multivariate statistics.
> 
> I think that is pretty useful.
> Oracle has an identical feature called "extended statistics".
> 
> That's probably an entirely different thing, but it would be very 
> nice to have statistics to estimate the correlation between columns 
> of different tables, to improve the estimate for the number of rows 
> in a join.

I don't have a clear idea of how that should work, but from the quick
look at how join selectivity estimation is implemented, I believe two
things might be possible:

 (a) using conditional probabilities

     Say we have a join "ta JOIN tb ON (ta.x = tb.y)"

     Currently, the selectivity is derived from stats on the two keys.
     Essentially probabilities P(x), P(y), represented by the MCV lists.
     But if there are additional WHERE conditions on the tables, and we
     have suitable multivariate stats, it's possible to use conditional
     probabilities.

     E.g. if the query actually uses

         ... ta JOIN tb ON (ta.x = tb.y) WHERE ta.z = 10

     and we have stats on (ta.x, ta.z), we can use P(x|z=10) instead.
     If the two columns are correlated, this might be much different.

 (b) using this for multi-column conditions

     If the join condition involves multiple columns, e.g.

         ON (ta.x = tb.y AND ta.p = tb.q)

     and we happen to have stats on (ta.x,ta.p) and (tb.y,tb.q), we may
     use this to compute the cardinality (pretty much as we do today).

But I haven't really worked on this so far, I suspect there are various
subtle issues and I certainly don't plan to address this in the first
phase of the patch.

Tomas


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