Unexpected sequential scan on an indexed column

Hi, everyone.

Between postres docs, forum posts, previous similar questions answered and
random blogs, I've read as much as I could about why others have had similar
problems in the past before turning to you guys for help, so I really hope
this is not some completely obvious oversight on my part (I am fairly new to
DB programming after all).

So, my postgres version is: PostgreSQL 8.4.1, compiled by Visual C++ build
1400, 32-bit

The table used in this query is called "users", and it has columns "userid"
(primary key) and "location".
The "location" column is indexed.
The users table has 1 million rows, and all rows have integer typed value
'-1' for "location" column, except for 2 rows that have the integer value
'76543'.

I've attached a file with SQL commands that will setup this condition.

Then I run statement A
SELECT userid FROM users, (VALUES (76543)) val (id) WHERE location = val.id;

and the correct 2 results are returned, but after much more time than I
would expect, since the location column is indexed.
I know that if all I wanted was the results from this specific query I could
simply do statement B

SELECT userid FROM users WHERE location = 76543;

and that works 100% of the time, at the speed that I would expect it to.
However, the example I'm giving here is a simplification of significantly
more complex statements that involve more joins and such, where I'm trying
to minimize round trips to database, and I've narrowed things down to the
point where I think that if I can figure out how to make something like
statement A perform well, then the overall performance problem will be
pretty easy to fix.

So, when I run explain analyze for statement A I get the following:

Nested Loop (cost=0.00..27906.01 rows=1000000 width=8) (actual
time=15.670..5411.503 rows=2 loops=1)
Join Filter: (users.location = "*VALUES*".column1)
-> Values Scan on "*VALUES*" (cost=0.00..0.01 rows=1 width=4) (actual
time=0.005..0.007 rows=1 loops=1)
-> Seq Scan on users (cost=0.00..15406.00 rows=1000000 width=12)
(actual time=0.028..2903.398 rows=1000000 loops=1)
Total runtime: 5411.620 ms
(5 rows)

Note that I did run VACUUM ANALYZE before running EXPLAIN ANALYZE.

I was curious about why the index wasn't being used so I forced it to be
used through "SET enable_seqscan TO off", and then saw the following EXPLAIN
ANALYZE output:

Nested Loop (cost=0.00..43889.37 rows=1000000 width=8) (actual
time=5813.875..5813.897 rows=2 loops=1)
Join Filter: (users.location = "*VALUES*".column1)
-> Values Scan on "*VALUES*" (cost=0.00..0.01 rows=1 width=4) (actual
time=0.004..0.006 rows=1 loops=1)
-> Index Scan using idx_users_location on users (cost=0.00..31389.36
rows=1000000 width=12) (actual time=0.375..2967.249 rows=1000000 loops=1)
Total runtime: 5814.029 ms

So, even when we use the index, the planner seems to force the query to scan
through all rows, rather than stopping the scan once it can knows that there
will be no more rows returned (given the presence of the index).

If I use a ORDER BY clause to force the table scan to happen in descending
order by location, then the SQL statement C performs wonderfully:

postgres=# explain analyze SELECT userid FROM users2, (VALUES (76543)) val
(id) WHERE location = val.id ORDER BY location DESC;

But that's only due to the specific values used in this example and wouldn't
work in general. If we ORDER_BY ascendingly, then the performance is still
really slow. So, basically the planner seems to always want to do a
sequential scan of the entire index, without placing any restriction on the
index, and it may abort the full index scan early under ordered conditions,
if the scan gets lucky.

Do you guys have any idea why this is not working as I expect? What I hope
to accomplish is to have a construct such as the table I labeled "val"
obtained from a sub-select. Given the size of the pool from which I'm
selecting these values, I very rarely expect the number of values in the
sub-select results to exceed 10, so I was hoping that the database would try
to do something like a bitmapped scan after restricting the user table to
the values in the small value table. Maybe it's not doing so given the
lopsided distribution of location values in the users table, but I'm just
not sure.

Any help is appreciated.

Thanks!
Eddy