index choosing problem - Mailing list pgsql-performance

I have a table with serveral million records. they are divided into
about one hundred catagory(column cid). I created index includes the cid
as the first column. I had a problem with some cids they only have few
records comparing with other cids. Some of them only have serveral
thousand rows. Some queries are not using index on the cids. I got the
explain for the queries.
Note:
article_others_cid_time_style_idx is the index contains cid as the first
column
article_others_pkey is the primary key on an auto incremented column aid.

# select count(*) from article_others;
   count
---------
  6888459
(1 row)

# select count(*) from article_others where cid=74;
  count
-------
   4199
(1 row)

1. # explain select count(*) from article_others where cid=74;
                                                       QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
  Aggregate  (cost=32941.95..32941.96 rows=1 width=0)
    ->  Index Scan using article_others_cid_time_style_idx on
article_others  (cost=0.00..32909.34 rows=13047 width=0)
          Index Cond: (cid = 74)
(3 rows)

2. # explain select aid from article_others where cid=74 limit 10;
                                                       QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
  Limit  (cost=0.00..25.22 rows=10 width=8)
    ->  Index Scan using article_others_cid_time_style_idx on
article_others  (cost=0.00..32909.34 rows=13047 width=8)
          Index Cond: (cid = 74)
(3 rows)

3. # explain select aid from article_others where cid=74 order by aid
desc limit 10;
                                                     QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
  Limit  (cost=0.00..1034.00 rows=10 width=8)
    ->  Index Scan Backward using article_others_pkey on article_others
(cost=0.00..1349056.65 rows=13047 width=8)
          Filter: (cid = 74)
(3 rows)

4. # explain select aid from article_others where cid=74 order by aid
desc limit 1;
                                                     QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
  Limit  (cost=0.00..103.40 rows=1 width=8)
    ->  Index Scan Backward using article_others_pkey on article_others
(cost=0.00..1349060.65 rows=13047 width=8)
          Filter: (cid = 74)
(3 rows)

5. # explain select max(aid) from article_others where cid=74;
                                                         QUERY PLAN

---------------------------------------------------------------------------------------------------------------------------
  Result  (cost=104.70..104.71 rows=1 width=0)
    InitPlan 1 (returns $0)
      ->  Limit  (cost=0.00..104.70 rows=1 width=8)
            ->  Index Scan Backward using article_others_pkey on
article_others  (cost=0.00..1365988.55 rows=13047 width=8)
                  Index Cond: (aid IS NOT NULL)
                  Filter: (cid = 74)
(6 rows)

Now the query 3-5 using article_others_pkey are quite slow. The rows for
cid 74 are very old and seldom get updated. I think pg needs to scan
quite a lot on article_others_pkey before it gets the rows for cid 74.
The same query for other cids with new and majority of rows runs very
fast. for example:
# explain select max(aid) from article_others where cid=258;
                                                          QUERY PLAN

----------------------------------------------------------------------------------------------------------------------------
  Result  (cost=1.54..1.55 rows=1 width=0)
    InitPlan 1 (returns $0)
      ->  Limit  (cost=0.00..1.54 rows=1 width=8)
            ->  Index Scan Backward using article_others_pkey on
article_others  (cost=0.00..1366260.55 rows=889520 width=8)
                  Index Cond: (aid IS NOT NULL)
                  Filter: (cid = 258)

So I think if pg chooses to use index article_others_cid_time_style_idx
the performance would be much better. or any other solution I can take
to improve the query performance for those cids like 74?
Another question, why the plan shows rows=13047 for cid=74 while
actually it only has 4199 rows? There is almost no data changes for cid
74 and I just vacuum/analyzed the table this morning.