Index correlation versus multi-column indexes

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: pgsql-hackers(at)postgreSQL(dot)org
Cc: Maxim Boguk <mboguk(at)masterhost(dot)ru>
Subject: Index correlation versus multi-column indexes
Date: 2009-02-27 18:25:51
Message-ID: 21437.1235759151@sss.pgh.pa.us
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

I looked into Maxim Boguk's complaint here:
http://archives.postgresql.org/pgsql-general/2009-02/msg01226.php
in which the planner preferred to use an index despite the column
being searched on being a lower-order column in that index.

It turns out that the reason the planner is preferring the "wrong" index
is that that index has a very high indexCorrelation score, evidently
because its first column is well correlated with the table ordering.
This causes cost_index to compute very low estimated heap access costs,
outweighing the increased index access costs due to the index's
relatively poor match to the query.

Now we already knew that btcostestimate's estimate of index correlation
was pretty bogus for multicolumn indexes. However, I now realize that
there's another issue here as well, which would apply even if the index
ordering correlation estimate were perfect. If you look closely at what
cost_index is doing with the number, you'll realize that it is
effectively assuming that high index correlation means that an indexscan
returns TIDs that are adjacent or nearly so in the heap. Even given
a perfect match of index and heap order, this fails to hold when the
indexscan quals contain constraints on lower-order index columns,
because we'll be skipping sections of the index in such cases.

So apparently we need to rethink this, and derate the correlation effect
somehow when there are constraints on non-first columns. I'm not
entirely sure what the model ought to be. Thoughts?

regards, tom lane

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Tom Lane 2009-02-27 19:43:26 Re: BUG #4680: Server crashed if using wrong (mismatch) conversion functions
Previous Message Heikki Linnakangas 2009-02-27 16:57:27 Re: BUG #4680: Server crashed if using wrong (mismatch) conversion functions