Re: two dimensional statistics in Postgres

Ahoj ;-)

On 06.11.2014 11:56, Tomas Vondra wrote:
> Hi,
>
> Dne 6 Listopad 2014, 11:15, Katharina Büchse napsal(a):
>> Hi,
>>
>> I'm a phd-student at the university of Jena, Thüringen, Germany, in the
>> field of data bases, more accurate query optimization.
>> I want to implement a system in PostgreSQL that detects column
>> correlations and creates statistical data about correlated columns for
>> the optimizer. Therefore I need to store two dimensional statistics
>> (especially two dimensional histograms) in PostgreSQL.
> Cool!
>
>> I had a look at the description of "WIP: multivariate statistics / proof
>> of concept", which looks really promising, I guess these statistics are
>> based on scans of the data? For my system I need both -- statistical
> Yes, it's based on a sample of the data.
>
>> data based on table scans (actually, samples are enough) and those based
>> on query feedback. Query feedback (tuple counts and, speaking a little
>> inaccurately, the where-part of the query itself) needs to be extracted
>> and there needs to be a decision for the optimizer, when to take
>> multivariate statistics and when to use the one dimensional ones. Oracle
>> in this case just disables one dimensional histograms if there is
>> already a multidimensional histogram, but this is not always useful,
>> especially in the case of a feedback based histogram (which might not
>> cover the whole data space). I want to use both kinds of histograms
> What do you mean by not covering the whole data space? I assume that when
> building feedback-based histogram, parts of the data will be filtered out
> because of WHERE clauses etc. Is that what you mean? I don't see how this
> could happen for regular histograms, though.
Yes, you're right. Because of the where clauses, some parts of the data
might be filtered out in feedback based histograms. This cannot happen
in "regular" histograms, but as I mentioned -- I would like to use both
kinds of histograms.
>
>> because correlations might occur only in parts of the data. In this case
>> a histogram based on a sample of the whole table might not get the point
>> and wouldn't help for the part of the data the user seems to be
>> interested in.
> Yeah, there may be dependencies that are difficult to spot in the whole
> dataset, but emerge once you filter to a specific subset.
>
> Now, how would that work in practice? Initially the query needs to be
> planned using regular stats (because there's no feedback yet), and then -
> when we decide the estimates are way off - may be re-planned using the
> feedback. The feedback is inherently query-specific, so I'm not sure if
> it's possible to reuse it for multiple queries (might be possible for
> "sufficiently similar" ones).
>
> Would this be done automatically for all queries / all conditions, or only
> when specifically enabled (on a table, columns, ...)?
The idea is the following: I want to find out correlations with two
different algorithms, one scanning some samples of the data, the other
analyzing query feedback. If both decide for a column combination that
it's correlated, then there should be made a "regular histogram" for
this combination. If only the "scanning"-algorithm says "correlated",
then it means that there is some correlation, but this is not
interesting for the user right now. So I would only "leave some note"
for the optimizer that there is correlation and if the user interest
changes and query results differ a lot from the estimates in the plan,
then again -- "regular histogram". If only the "feedback"-algorithm
decides that the columns are correlated, a histogram based on query
feedback is the most useful choice to support the work of the optimizer.
>
>> There are special data structures for storing multidimensional
>> histograms based on feedback and I already tried to implement one of
>> these in C. In the case of two dimensions they are of course not "for
>> free" (one dimensional would be much cheaper), but based on the
>> principle of maximum entropy they deliver really good results. I decided
>> for only two dimensions because in this case we have the best proportion
>> of cost and benefit when searching for correlation (here I'm relying on
> I think hardcoding the two-dimensions limit is wrong. I understand higher
> number of dimensions means more expensive operation, but if the user can
> influence it, I believe it's OK.
I don't know whether the user has to decide whether the statistical data
is based on feedback or on data scans. I guess it's enough if he gets
his histograms in higher dimensions based on data scans.
>
> Also, is there any particular reason why not to support other kinds of
> stats (say, MCV lists)? In the end it's just a different way to
> approximate the distribution, and it may be way cheaper than histograms.
The reason actually is just that 1) I have only limited time and cannot
cover every possibility to support the optimizer when there is
correlation and 2) there are good papers about feedback based histograms :-D
>
>> tests that were made in DB2 within a project called CORDS which detects
>> correlations even between different tables).
> Is this somehow related to LEO? I'm not familiar with the details, but
> from the description it might be related.
actually, LEO is purely feedback based, while CORDS is using data scans.
But some authors were involved in both projects I guess. LEO itself
never made it to be fully integrated in DB2, but some parts of it did.
What's interesting for me is the fact that in DB2 there's no possibility
for multidimensional histograms.
>
> regards
> Tomas
>
Katharina