Re: cross column correlation revisted

On 14/07/10 13:12, PostgreSQL - Hans-Jürgen Schönig wrote:
> hello everybody,
>
> we are currently facing some serious issues with cross correlation issue.
> consider: 10% of all people have breast cancer. we have 2 genders (50:50).
> if i select all the men with breast cancer, i will get basically nobody - the planner will overestimate the output.
> this is the commonly known problem ...
>
> this cross correlation problem can be quite nasty in many many cases.
> underestimated nested loops can turn joins into a never ending nightmare and so on and so on.
>
> my ideas is the following:
> what if we allow users to specifiy cross-column combinations where we keep separate stats?
> maybe somehow like this ...
>
> ALTER TABLE x SET CORRELATION STATISTICS FOR (id = id2 AND id3=id4)
>
> or ...
>
> ALTER TABLE x SET CORRELATION STATISTICS FOR (x.id = y.id AND x.id2 = y.id2)
>
> clearly we cannot store correlation for all combinations of all columns so we somehow have to limit it.
>
> what is the general feeling about something like that?

+1 is my general feeling, it's good if you can tell the system to
collect additional statistics where needed. And once you have that, you
can write an agent or something to detect automatically which extra
statistics might be useful.

However, the problem is how to represent and store the
cross-correlation. For fields with low cardinality, like "gender" and
boolean "breast-cancer-or-not" you can count the prevalence of all the
different combinations, but that doesn't scale. Another often cited
example is zip code + street address. There's clearly a strong
correlation between them, but how do you represent that?

For scalar values we currently store a histogram. I suppose we could
create a 2D histogram for two columns, but that doesn't actually help
with the zip code + street address problem.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com