Very slow left outer join

Hi All,

I have a very slow left outer join that speeds up by more then 1000
times when I turn set enable_seqscan=off.  This is not the query I
actually do in my application, but is a simplified one that singles out
the part that is really slow.  All of the columns involved in the query
have indexes on them, but unless I set enable_seqscan=off the planner is
doing a sequential scan instead of using the indexes.  I'm hoping there
is something simple I am doing wrong that someone can point out to me.
I am using version 8.1.5.

So here is the explain analyze output first with enable_seqscan=on, and
the second with enable_seqscan=off:

mdsdb=# explain analyze select backupobjects.record_id from
backupobjects left outer join backup_location using(record_id) where
backup_id = 1071;

QUERY PLAN

------------------------------------------------------------------------
------------------------------------------------------------------------
-----
 Hash Join  (cost=361299.50..1054312.92 rows=34805 width=8) (actual
time=1446.861..368723.597 rows=2789 loops=1)
   Hash Cond: ("outer".record_id = "inner".record_id)
   ->  Seq Scan on backupobjects  (cost=0.00..429929.79 rows=13136779
width=8) (actual time=5.165..359168.216 rows=13136779 loops=1)
   ->  Hash  (cost=360207.21..360207.21 rows=436915 width=8) (actual
time=820.979..820.979 rows=2789 loops=1)
         ->  Bitmap Heap Scan on backup_location
(cost=3831.20..360207.21 rows=436915 width=8) (actual
time=797.463..818.269 rows=2789 loops=1)
               Recheck Cond: (backup_id = 1071)
               ->  Bitmap Index Scan on backup_location_bid
(cost=0.00..3831.20 rows=436915 width=0) (actual time=59.592..59.592
rows=2789 loops=1)
                     Index Cond: (backup_id = 1071)
 Total runtime: 368725.122 ms
(9 rows)

mdsdb=# explain analyze select backupobjects.record_id from
backupobjects left outer join backup_location using(record_id) where
backup_id = 1071;
                                                                  QUERY
PLAN

------------------------------------------------------------------------
-----------------------------------------------------------------------
 Nested Loop  (cost=3833.21..1682311.27 rows=34805 width=8) (actual
time=103.132..201.808 rows=2789 loops=1)
   ->  Bitmap Heap Scan on backup_location  (cost=3831.20..360207.21
rows=436915 width=8) (actual time=94.375..97.688 rows=2789 loops=1)
         Recheck Cond: (backup_id = 1071)
         ->  Bitmap Index Scan on backup_location_bid
(cost=0.00..3831.20 rows=436915 width=0) (actual time=84.239..84.239
rows=2789 loops=1)
               Index Cond: (backup_id = 1071)
   ->  Bitmap Heap Scan on backupobjects  (cost=2.00..3.01 rows=1
width=8) (actual time=0.033..0.034 rows=1 loops=2789)
         Recheck Cond: (backupobjects.record_id = "outer".record_id)
         ->  Bitmap Index Scan on backupobjects_pkey  (cost=0.00..2.00
rows=1 width=0) (actual time=0.021..0.021 rows=1 loops=2789)
               Index Cond: (backupobjects.record_id = "outer".record_id)
 Total runtime: 203.378 ms
(10 rows)

Here are the two tables in the query:

mdsdb=# \d backup_location
 Table "public.backup_location"
  Column   |  Type   | Modifiers
-----------+---------+-----------
 record_id | bigint  | not null
 backup_id | integer | not null
Indexes:
    "backup_location_pkey" PRIMARY KEY, btree (record_id, backup_id)
    "backup_location_bid" btree (backup_id)
    "backup_location_rid" btree (record_id)
Foreign-key constraints:
    "backup_location_bfk" FOREIGN KEY (backup_id) REFERENCES
backups(backup_id) ON DELETE CASCADE

mdsdb=# \d backupobjects
               Table "public.backupobjects"
     Column     |            Type             | Modifiers
----------------+-----------------------------+-----------
 record_id      | bigint                      | not null
 dir_record_id  | integer                     |
 name           | text                        |
 extension      | character varying(64)       |
 hash           | character(40)               |
 mtime          | timestamp without time zone |
 size           | bigint                      |
 user_id        | integer                     |
 group_id       | integer                     |
 meta_data_hash | character(40)               |
Indexes:
    "backupobjects_pkey" PRIMARY KEY, btree (record_id)
    "backupobjects_meta_data_hash_key" UNIQUE, btree (meta_data_hash)
    "backupobjects_extension" btree (extension)
    "backupobjects_hash" btree (hash)
    "backupobjects_mtime" btree (mtime)
    "backupobjects_size" btree (size)

Thanks,
Ed