Forum OpenACS Q&A: How does postgresql handle indexes on multiple columns?

Collapse
1: How does postgresql handle indexes on multiple columns?
Posted by Jonathan Ellis on 01/23/02 06:57 AM
I have a unique index on minion_spells(minion_id, spell_id) primarily
to enforce me not coding something stupid, but I noticed that a query
joining on spell_id won't use it, even with enable_seqscan off.  This
surprised me.  I added an index just on spell_id, and it used the
index right off.  Sybase, to pick the db I'm most familiar with,
would be perfectly happy to use "half" of a larger index.  Is this
not the case with PG?
Collapse
2: Response to How does postgresql handle indexes on multiple columns? (response to 1)
Posted by mark dalrymple on 01/23/02 02:49 PM
PG and Oracle will only use the leading half of the index (e.g. minion_id) in that case.  Under the hood, I believe that the spell_ids are too scattered around to be useful as an index in their own right.  If you change your unique index to (spell_id, minion_id), then you should be able to get rid of your (spell_id) index.
Collapse
3: Response to How does postgresql handle indexes on multiple columns? (response to 1)
Posted by Jonathan Ellis on 01/23/02 03:44 PM
Ah... that works, thanks!
Collapse
4: Response to How does postgresql handle indexes on multiple columns? (response to 1)
Posted by Jonathan Ellis on 01/23/02 04:43 PM
For the record, I was wrong and Sybase is the same way -- you have to include the leading index column in your query for the db to make use of it.  (Except for covered nonmatching index scans but that's not what I was talking about.)
Collapse
5: Response to How does postgresql handle indexes on multiple columns? (response to 1)
Posted by Don Baccus on 01/23/02 09:11 PM
The reason for this is that the btree that's built can be thought to be logically ordered by the concatenation of the keys.  It can only be traversed via the tree structure by comparing those keys left-to-right.

Think of a btree ordered by a string of characters.

If you have the strings "abc", "abd", "bed" etc you can use (<,=,>) to traverse the tree given a single-character key like "a".  But you can't do a simple top-down traversal of the tree against the trailing character.  The tree's not ordered correctly for such a traversal.

So you can do a sequential scan of the index or a sequential scan of the table.  Either way you get O(n) rather than O(log2(n)).  Index tables carry a lot of metadata, especially as they grow and many page-splits occur (i.e. as the tree deepens).  For tables with short columns they can easily be longer than the table itself.  PG never does a sequential scan on an index, always on the base table.  In the end you have to visit the table to retrieve the rows, after all ...