Stats for multi-column indexes

I know the idea has come up a few times to do cross-column statistics to
improve plans when the data distributions are dependent. I found a
couple references in the archives:

http://archives.postgresql.org/pgsql-hackers/2006-09/msg02118.php
http://archives.postgresql.org/pgsql-hackers/2006-08/msg00924.php

We can already keep stats for a functional index. Is there a reason we
can't keep stats for a multi-column index?

Out of the two situations outlined by Jim Nasby here:

http://archives.postgresql.org/pgsql-hackers/2006-08/msg00948.php

It would not help with joins, but it would help with columns that are
referred to as a group (e.g. a=1 AND b<20).

Regards,
Jeff Davis

Jeff Davis <pgsql(at)j-davis(dot)com> writes:
> We can already keep stats for a functional index. Is there a reason we
> can't keep stats for a multi-column index?

The questions that need to be answered are (1) what stats are you gonna
collect, and (2) exactly what are you going to do with them when you
have 'em?

All the previous discussions have stalled on the question of how to
avoid trying to collect stats about an exponentially large number of
column combinations; we've never even reached the question of what
stats we'd actually want given that a particular combination has been
determined to be interesting. Perhaps that's a trivial question,
but it's been a mighty long time since I took statistics ...

regards, tom lane

On Mon, 2007-03-19 at 21:24 -0400, Tom Lane wrote:
> Jeff Davis <pgsql(at)j-davis(dot)com> writes:
> > We can already keep stats for a functional index. Is there a reason we
> > can't keep stats for a multi-column index?
>
> The questions that need to be answered are (1) what stats are you gonna
> collect, and (2) exactly what are you going to do with them when you
> have 'em?
>
> All the previous discussions have stalled on the question of how to
> avoid trying to collect stats about an exponentially large number of
> column combinations; we've never even reached the question of what
> stats we'd actually want given that a particular combination has been
> determined to be interesting. Perhaps that's a trivial question,
> but it's been a mighty long time since I took statistics ...
>

I know we can't keep stats on every combination of columns. My initial
idea would be to only keep stats about a multi-column index (and
probably optional for those, too).

My thinking was that we could keep a histogram (and MCVs, etc.) of the
non-scalar key in the multi-column index. That would provide the data
the planner needs to answer a query like "WHERE a = 1 and b < 1000" if a
and b are dependent and you have an index on (a,b).

It seemed within reach to me initially because I could use a functional
index (in which the function turns multiple values into a comparable
scalar) and postgresql would index that and keep stats. And when it has
those stats, it makes the correct plan. Of course, I have to litter the
SQL with unnecessary function calls (so that it can use the functional
index), which makes this undesirable.

AndrewSN pointed out on IRC that keeping a histogram of non-scalar
values is not as easy as I thought, because PostgreSQL doesn't allow
arrays of composite types, among other problems.

Is this a worthwhile area of exploration?

Regards,
Jeff Davis

Jeff Davis wrote:
>
> I know we can't keep stats on every combination of columns. My initial
> idea would be to only keep stats about a multi-column index (and
> probably optional for those, too).
>

Maybe you would want to keep single column indexes too, so that (more)
accurate estimates for bitmap-and type plans are possible.

Cheers

Mark

On Tue, 2007-03-20 at 14:14 +1200, Mark Kirkwood wrote:
> Jeff Davis wrote:
> >
> > I know we can't keep stats on every combination of columns. My initial
> > idea would be to only keep stats about a multi-column index (and
> > probably optional for those, too).
> >
>
> Maybe you would want to keep single column indexes too, so that (more)
> accurate estimates for bitmap-and type plans are possible.

We should allow the DBA to specify which groups of cols to keep
statistics on, if there is no index on that group.

That solves the combinatorial explosion problem.

--
Simon Riggs
EnterpriseDB http://www.enterprisedb.com

Simon Riggs wrote:
> On Tue, 2007-03-20 at 14:14 +1200, Mark Kirkwood wrote:
>> Jeff Davis wrote:
>>> I know we can't keep stats on every combination of columns. My initial
>>> idea would be to only keep stats about a multi-column index (and
>>> probably optional for those, too).
>>>
>> Maybe you would want to keep single column indexes too, so that (more)
>> accurate estimates for bitmap-and type plans are possible.
>
> We should allow the DBA to specify which groups of cols to keep
> statistics on, if there is no index on that group.
>
> That solves the combinatorial explosion problem.

This is one hint I think everyone can agree on. Being able to say that
values in different columns are related just gives the planner more
information to work with.

--
Richard Huxton
Archonet Ltd

Richard Huxton wrote:
> Simon Riggs wrote:
> >On Tue, 2007-03-20 at 14:14 +1200, Mark Kirkwood wrote:
> >>Jeff Davis wrote:
> >>>I know we can't keep stats on every combination of columns. My initial
> >>>idea would be to only keep stats about a multi-column index (and
> >>>probably optional for those, too).
> >>>
> >>Maybe you would want to keep single column indexes too, so that (more)
> >>accurate estimates for bitmap-and type plans are possible.
> >
> >We should allow the DBA to specify which groups of cols to keep
> >statistics on, if there is no index on that group.
> >
> >That solves the combinatorial explosion problem.
>
> This is one hint I think everyone can agree on. Being able to say that
> values in different columns are related just gives the planner more
> information to work with.

It was also suggested that column pairs in FK relationship could be
automatically enabled. So you don't need to specify those manually.

Now, the hard question is deciding what to keep track of. I don't think
MCV makes much sense, because what's the MCV of two columns? Some sort
of correlation index would seem to make certain sense.

--
Alvaro Herrera http://www.CommandPrompt.com/
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

Alvaro Herrera wrote:
> Now, the hard question is deciding what to keep track of. I don't
> think MCV makes much sense, because what's the MCV of two columns?

The combination that occurs most often.

--
Peter Eisentraut
http://developer.postgresql.org/~petere/

Alvaro Herrera <alvherre(at)commandprompt(dot)com> writes:
> It was also suggested that column pairs in FK relationship could be
> automatically enabled. So you don't need to specify those manually.

Actually, I think you don't particularly need stats for that in most
cases --- if the planner simply took note that the FK relationship
exists, it would know that each row of the FK side joins to exactly
one row of the PK side, which in typical cases is sufficient.

regards, tom lane

Tom,

> Actually, I think you don't particularly need stats for that in most
> cases --- if the planner simply took note that the FK relationship
> exists, it would know that each row of the FK side joins to exactly
> one row of the PK side, which in typical cases is sufficient.

Is it? What about the other direction? Currently, doesn't the planner
assume that the rowcount relationship is 1 to ( child total rows /
parent total rows) ? That's ok for tables with relatively even
distribution, but not for skewed ones.

--Josh Berkus

On Tue, 2007-03-20 at 09:03 +0000, Simon Riggs wrote:
> We should allow the DBA to specify which groups of cols to keep
> statistics on, if there is no index on that group.
>
> That solves the combinatorial explosion problem.
>

I think it would be a good first step if we could just keep stats on
multiple columns in the same table. If we can do more than that, great.

We could probably keep stats on multiple columns across different
tables, but I don't know how those statistics should be used. Using
statistics to estimate joins seems like a tricky problem. Maybe it's
already solved with known algorithms?

Regards,
Jeff Davis

On Tue, 2007-03-20 at 18:12 +0100, Josh Berkus wrote:
> Tom,
>
> > Actually, I think you don't particularly need stats for that in most
> > cases --- if the planner simply took note that the FK relationship
> > exists, it would know that each row of the FK side joins to exactly
> > one row of the PK side, which in typical cases is sufficient.
>
> Is it? What about the other direction? Currently, doesn't the planner
> assume that the rowcount relationship is 1 to ( child total rows /
> parent total rows) ? That's ok for tables with relatively even
> distribution, but not for skewed ones.
>

In theory, the PK constrains the available values of the FK, but doesn't
provide any additional information about the relationship between the
columns.

However, in practice there is limited space to store MCVs and limited
accuracy to n_distinct. So there may be a reason to store more
information, but I don't know what we'd store. Do we have reports of bad
estimates by the planner in this situation?

Regards,
Jeff Davis

Josh Berkus <josh(at)agliodbs(dot)com> writes:
>> Actually, I think you don't particularly need stats for that in most
>> cases --- if the planner simply took note that the FK relationship
>> exists, it would know that each row of the FK side joins to exactly
>> one row of the PK side, which in typical cases is sufficient.

> Is it? What about the other direction?

I recall that we had decided at the Greenplum meeting last year that
we could use a better heuristic if we noted that a join was being done
on an FK-and-PK combination, but I don't recall the details right at
the moment. Did anyone take notes?

regards, tom lane

On Mon, Mar 19, 2007 at 06:55:56PM -0700, Jeff Davis wrote:
> On Mon, 2007-03-19 at 21:24 -0400, Tom Lane wrote:
> > Jeff Davis <pgsql(at)j-davis(dot)com> writes:
> > > We can already keep stats for a functional index. Is there a reason we
> > > can't keep stats for a multi-column index?
> >
> > The questions that need to be answered are (1) what stats are you gonna
> > collect, and (2) exactly what are you going to do with them when you
> > have 'em?
> >
> > All the previous discussions have stalled on the question of how to
> > avoid trying to collect stats about an exponentially large number of
> > column combinations; we've never even reached the question of what
> > stats we'd actually want given that a particular combination has been
> > determined to be interesting. Perhaps that's a trivial question,
> > but it's been a mighty long time since I took statistics ...
> >
>
> I know we can't keep stats on every combination of columns. My initial
> idea would be to only keep stats about a multi-column index (and
> probably optional for those, too).
>
> My thinking was that we could keep a histogram (and MCVs, etc.) of the
> non-scalar key in the multi-column index. That would provide the data
> the planner needs to answer a query like "WHERE a = 1 and b < 1000" if a
> and b are dependent and you have an index on (a,b).
<snip>
> AndrewSN pointed out on IRC that keeping a histogram of non-scalar
> values is not as easy as I thought, because PostgreSQL doesn't allow
> arrays of composite types, among other problems.

I don't think the array problem is that big a deal, since PostgreSQL
doesn't enforce array dimensions at all. You can just make the arrays
for multi-column stats 2 dimensional, though handling indexes with
different data types among the columns would be a bit tricky... right
now the only choice I can think of would be to require that values could
be cast to and from text and just store text in the array. Though
obviously it'd be better to just allow arrays of composite types...

The other challenge is that you can't make all the same assumptions with
a multi-field histogram that you can with a single-field one. For
example, if this is our index:

a b
- -
1 1
1 2
...
1 1000
2 500
2 501
...
3 5000

The histogram would likely position the buckets such that 1,1000 and
2,500 would fall within one bucket, which means the planner has no idea
that b doesn't exceed 1000 when a is 1. I'm not sure how big of an issue
that is in reality, though, because the planner does know that the
bucket can only represent so many rows.

It might be worth coming up with a different means to store the
histogram for the multi-column case.

> Is this a worthwhile area of exploration?

ISTM it trips people up often enough to make it worth at least
exploring...
--
Jim Nasby jim(at)nasby(dot)net
EnterpriseDB http://enterprisedb.com 512.569.9461 (cell)

"Jim C. Nasby" <jim(at)nasby(dot)net> writes:
> It might be worth coming up with a different means to store the
> histogram for the multi-column case.

A separate array for each column involved seems a whole lot less
fragile than pretending we can handle mixed-type arrays.

We probably need a different catalog anyway, or at least a reimagining
of pg_statistic, since it doesn't hold more than one value of staattnum
per row.

regards, tom lane

On Tue, 2007-03-20 at 18:12, Josh Berkus wrote:
> Tom,
>
> > Actually, I think you don't particularly need stats for that in most
> > cases --- if the planner simply took note that the FK relationship
> > exists, it would know that each row of the FK side joins to exactly
> > one row of the PK side, which in typical cases is sufficient.
>
> Is it? What about the other direction? Currently, doesn't the planner
> assume that the rowcount relationship is 1 to ( child total rows /
> parent total rows) ? That's ok for tables with relatively even
> distribution, but not for skewed ones.

Wouldn't that be improved if the MCVs/histogram of the FK column are
taken into account ? Considering that the FK part is unique, the
skewness in the relationship is completely determined by the FK parts
histogram. That would give at least a lower/upper bound and MCVs to the
relationship.

Cheers,
Csaba.

This should read:

> Considering that the FK part is unique, the
^^PK^^
> skewness in the relationship is completely determined by the FK part's
> histogram. That would give at least a lower/upper bound and MCVs to the
> relationship.

Cheers,
Csaba.