From: Tomas Vondra <tv@fuzzy.cz>
To: pgsql-hackers@postgresql.org
Subject: Re: WIP: multivariate statistics / proof of concept
Date: Mon, 13 Oct 2014 21:47:24 +0200
Message-ID: <543C2C4C.6040800@fuzzy.cz> (raw)
In-Reply-To: <A737B7A37273E048B164557ADEF4A58B17D73648@ntex2010a.host.magwien.gv.at>
References: <543AFA15.4080608@fuzzy.cz>
<A737B7A37273E048B164557ADEF4A58B17D73648@ntex2010a.host.magwien.gv.at>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>
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
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: tv@fuzzy.cz
Subject: Re: WIP: multivariate statistics / proof of concept
In-Reply-To: <543C2C4C.6040800@fuzzy.cz>
* 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