Chaotically weird execution plan

When displaying information about information about an user in our
site, I noticed an unreasonable slowdown. The culprit turned out to be
a trivial select, which determines the number of comments left by an
user:

select count(*) from comments where created_by=80 and status=1;


The comments table structure is below, and contains ~2 million
records. I guess postgresql is unable to figure out exactly how to
make use of the index condition? As query plan shows, it got the
correct answer, 15888, very fast: the rest of the 13 seconds it's just
rechecking all the comments for some weird reasons. The weird thing
is, SOMETIMES, for other created_by values, it seems to work fine, as
shown below as well. Is this a bug, or I'm missing something here?

Thanks,
Einars Lielmanis



*** worse plan example:

etests=> explain analyze select count(*) from comments where
created_by=80 and status=1;

QUERY PLAN

----------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=50947.51..50947.52 rows=1 width=0) (actual
time=13134.360..13134.361 rows=1 loops=1)
   ->  Bitmap Heap Scan on comments  (cost=331.42..50898.41 rows=19639
width=0) (actual time=40.865..13124.116 rows=15888 loops=1)
         Recheck Cond: ((created_by = 80) AND (status = 1))
         ->  Bitmap Index Scan on comments_created_by
(cost=0.00..326.51 rows=19639 width=0) (actual time=33.547..33.547
rows=15888 loops=1)
               Index Cond: (created_by = 80)
 Total runtime: 13134.688 ms



*** better plan example:

etests=> explain analyze select count(*) from comments where
created_by=81 and status=1;
                                                               QUERY PLAN

----------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=854.10..854.11 rows=1 width=0) (actual
time=0.083..0.083 rows=1 loops=1)
   ->  Index Scan using comments_created_by on comments
(cost=0.00..853.44 rows=262 width=0) (actual time=0.057..0.076 rows=3
loops=1)
         Index Cond: (created_by = 81)
 Total runtime: 0.121 ms



*** structure

etests=> \d comments;
                                            Table "public.comments"
     Column      |            Type             |
    Modifiers
-----------------+-----------------------------+---------------------------------------------------------------
 comment_id      | integer                     | not null default
nextval('comments_comment_id_seq'::regclass)
 message_wiki    | text                        |
 message_html    | text                        |
 status          | integer                     |
 post_id         | integer                     |
 created         | timestamp without time zone |
 created_by      | integer                     |

Indexes:
    "comments_pkey" PRIMARY KEY, btree (comment_id)
    "comments_created_by" btree (created_by) WHERE status = 1
    "comments_for_post" btree (post_id, created) WHERE status = 1
Check constraints:
    "comments_status_check" CHECK (status = ANY (ARRAY[0, 1, 2]))
Foreign-key constraints:
    "comments_created_by_fkey" FOREIGN KEY (created_by) REFERENCES
members(member_id)
    "comments_thread_id_fkey" FOREIGN KEY (post_id) REFERENCES posts(post_id)

PostgreSQL 8.3.1 on i686-pc-linux-gnu, compiled by GCC gcc (GCC) 4.2.3
(Ubuntu 4.2.3-2ubuntu7)