Planner making poor choices?

Postgres (v7.3.1) doesn't seem to making use of indexes when it clearly
is the proper choice to make. I've ran in to this problem several times,
but "alter table statistics" has always solved the problem. However it
didn't seem to help in this case.

Any ideas why Postgres refuses to use the index?

Summary: (details follow)
=====================================================================

vacuum analyze verbose mail_aliases;

explain analyze select count(*) from mail_aliases where account_id =
13275;
Time: 90.21 ms

set enable_seqscan = off;

explain analyze select count(*) from mail_aliases where account_id =
13275;
Time: 6.16 ms

ALTER table mail_aliases alter account_id set statistics 25;

vacuum analyze verbose mail_aliases;

explain analyze select count(*) from mail_aliases where account_id =
13275;
Time: ~90 ms

ALTER table mail_aliases alter account_id set statistics 100;

vacuum analyze verbose mail_aliases;

explain analyze select count(*) from mail_aliases where account_id =
13275;
Time: ~90 ms

ALTER table mail_aliases alter account_id set statistics 1000;

vacuum analyze verbose mail_aliases;

explain analyze select count(*) from mail_aliases where account_id =
13275;
Time: ~90 ms

Details:
=====================================================================
version
---------------------------------------------------------------
PostgreSQL 7.3.1 on i386-pc-linux-gnu, compiled by GCC 2.95.4
(1 row)

userservices=# select count(*) from mail_aliases;
count
-------
49766
(1 row)

Time: 107.89 ms

userservices=# select count(*) from mail_aliases where account_id =
13275;
count
-------
624
(1 row)

Time: 90.26 ms

userservices=# vacuum analyze verbose mail_aliases;
INFO: --Relation public.mail_aliases--
INFO: Pages 789: Changed 0, Empty 0; Tup 49756: Vac 0, Keep 0, UnUsed
21811.
Total CPU 0.00s/0.02u sec elapsed 0.01 sec.
INFO: Analyzing public.mail_aliases
VACUUM
Time: 219.23 ms

userservices=# explain analyze select count(*) from mail_aliases where
account_id = 13275;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------
Aggregate (cost=1412.77..1412.77 rows=1 width=0) (actual
time=88.42..88.42 rows=1 loops=1)
-> Seq Scan on mail_aliases (cost=0.00..1410.95 rows=730 width=0)
(actual time=1.87..87.60 rows=624 loops=1)
Filter: (account_id = 13275)
Total runtime: 88.54 msec
(4 rows)

Time: 90.21 ms

userservices=# set enable_seqscan = off;
SET
Time: 1.03 ms

userservices=# explain analyze select count(*) from mail_aliases where
account_id = 13275;

QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=2012.53..2012.53 rows=1 width=0) (actual
time=4.19..4.19 rows=1 loops=1)
-> Index Scan using account_id_mail_aliases_key on mail_aliases
(cost=0.00..2010.70 rows=730 width=0) (actual time=0.08..3.24 rows=624
loops=1)
Index Cond: (account_id = 13275)
Total runtime: 4.28 msec
(4 rows)

Time: 6.16 ms

userservices=# ALTER table mail_aliases alter account_id set statistics
25;
ALTER TABLE
Time: 36.83 ms
userservices=# vacuum analyze verbose mail_aliases;
INFO: --Relation public.mail_aliases--
INFO: Pages 789: Changed 0, Empty 0; Tup 49756: Vac 0, Keep 0, UnUsed
21811.
Total CPU 0.00s/0.01u sec elapsed 0.01 sec.
INFO: Analyzing public.mail_aliases
VACUUM
Time: 495.19 ms

userservices=# set enable_seqscan = on;
SET
Time: 1.28 ms

userservices=# explain analyze select count(*) from mail_aliases where
account_id = 13275;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------
Aggregate (cost=1412.33..1412.33 rows=1 width=0) (actual
time=90.31..90.32 rows=1 loops=1)
-> Seq Scan on mail_aliases (cost=0.00..1410.95 rows=551 width=0)
(actual time=2.02..89.47 rows=624 loops=1)
Filter: (account_id = 13275)
Total runtime: 90.46 msec
(4 rows)

Time: 92.99 ms

userservices=# ALTER table mail_aliases alter account_id set statistics
100;
ALTER TABLE
Time: 22.61 ms

userservices=# vacuum analyze verbose mail_aliases;
INFO: --Relation public.mail_aliases--
INFO: Index mail_aliases_pkey: Pages 395; Tuples 49758: Deleted 2.
CPU 0.00s/0.02u sec elapsed 0.01 sec.
INFO: Index account_id_mail_aliases_key: Pages 334; Tuples 49758:
Deleted 2.
CPU 0.00s/0.01u sec elapsed 0.01 sec.
INFO: Index alias_mail_aliases_key: Pages 375; Tuples 49758: Deleted 2.
CPU 0.00s/0.02u sec elapsed 0.01 sec.
INFO: Removed 2 tuples in 1 pages.
CPU 0.00s/0.00u sec elapsed 0.00 sec.
INFO: Pages 789: Changed 0, Empty 0; Tup 49758: Vac 2, Keep 2, UnUsed
21807.
Total CPU 0.00s/0.07u sec elapsed 0.06 sec.
INFO: Analyzing public.mail_aliases
VACUUM
Time: 1915.31 ms

userservices=# explain analyze select count(*) from mail_aliases where
account_id = 13275;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------
Aggregate (cost=1412.53..1412.53 rows=1 width=0) (actual
time=87.98..87.98 rows=1 loops=1)
-> Seq Scan on mail_aliases (cost=0.00..1410.97 rows=622 width=0)
(actual time=1.85..87.17 rows=624 loops=1)
Filter: (account_id = 13275)
Total runtime: 88.09 msec
(4 rows)

Time: 90.68 ms

userservices=# ALTER table mail_aliases alter account_id set statistics
1000;
ALTER TABLE
Time: 1.53 ms
userservices=# vacuum analyze verbose mail_aliases;
INFO: --Relation public.mail_aliases--
INFO: Index mail_aliases_pkey: Pages 395; Tuples 49756: Deleted 4.
CPU 0.00s/0.02u sec elapsed 0.01 sec.
INFO: Index account_id_mail_aliases_key: Pages 334; Tuples 49756:
Deleted 4.
CPU 0.00s/0.01u sec elapsed 0.01 sec.
INFO: Index alias_mail_aliases_key: Pages 375; Tuples 49756: Deleted 4.
CPU 0.00s/0.02u sec elapsed 0.01 sec.
INFO: Removed 4 tuples in 1 pages.
CPU 0.00s/0.00u sec elapsed 0.00 sec.
INFO: Pages 789: Changed 0, Empty 0; Tup 49756: Vac 4, Keep 0, UnUsed
21807.
Total CPU 0.00s/0.07u sec elapsed 0.06 sec.
INFO: Analyzing public.mail_aliases
VACUUM
Time: 2935.78 ms

userservices=# explain analyze select count(*) from mail_aliases where
account_id = 13275;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------
Aggregate (cost=1412.51..1412.51 rows=1 width=0) (actual
time=88.00..88.00 rows=1 loops=1)
-> Seq Scan on mail_aliases (cost=0.00..1410.95 rows=624 width=0)
(actual time=1.87..87.20 rows=624 loops=1)
Filter: (account_id = 13275)
Total runtime: 88.11 msec
(4 rows)

Time: 92.31 ms