Useless index

HELP!!!

Okay, now that I have your attention :). I have a table with
about 560M rows in it. Performance is usually pretty good except when I
do a specific query:

SELECT fooid FROM foo
WHERE bazid = 123456
ORDER BY score DESC LIMIT 100 ;

My index looks like:

CREATE INDEX foo_index ON foo (bazid, score) ;

This query should return the 100 highest scores out a possible 1.1M rows
(for the query that got me attention). When I do an explain, I get:

# explain select fooid from foo where bazid = 123456 order by score desc
limit 100 ;
NOTICE: QUERY PLAN:

Limit (cost=1552.10..1552.10 rows=100 width=6)
-> Sort (cost=1552.10..1552.10 rows=382 width=6)
-> Index Scan using foo_index on foo (cost=0.00..1535.69
rows=382 width=6)

EXPLAIN

Doesn't look too bad, but I have a LOT of data where there is only a
single fooid for a bazid, which really skews the EXPLAIN results. On
mysql (and I believe Oracle, gotta find my other hat), I could create the
index as:

CREATE INDEX foo_index ON foo (bazid, score desc) ;

Which would be exactly what I want, and would complete in a split second.
Instead, this thing runs FOREVER (okay, it just seems that way to my
client :). Is there any way to get the equivalent index from PostgreSQL?
This is a major show stopper for me at this point. I have looked through
Chapter 7 of the 'idocs', but I didn't find anything that would help.

- brian

Wm. Brian McCane | Life is full of doors that won't open
Search http://recall.maxbaud.net/ | when you knock, equally spaced amid those
Usenet http://freenews.maxbaud.net/ | that open when you don't want them to.
Auction http://www.sellit-here.com/ | - Roger Zelazny "Blood of Amber"