Re: two dimensional statistics in Postgres

On 06/11/14 23:15, Katharina Büchse wrote:
> 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.
> 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 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 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.
> 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 tests that were made in DB2 within a project called 
> CORDS which detects correlations even between different tables).
>
> I'd be grateful for any advices and discussions.
> Regards,
>
> Katharina
>
>
Could you store a 2 dimensional histogram in a one dimensional array: 
A[z] = value, where z = col * rowSize + row (zero starting index)?


Cheers,
Gavin