Bitmap Heap Scan takes a lot of time

Hello,

I have a big table (around 3 600 000 entries) which stores which user
has seen which subjects in a forum.
This query is executed every time a user connects to the forum:

SELECT flg_rid
FROM prj_frm_flg
WHERE flg_mid=3 AND NOT flg_fav AND NOT flg_notif AND NOT flg_post
ORDER BY flg_rid DESC
OFFSET 999

This query very often takes a lot of time to do its job (40-60s).

I have a primary key on flg_mid and flg_sid (simultaneously) and
indexes on flg_notif, flg_post and flg_fav.

This is the result of an EXPLAIN:

"Limit (cost=453.48..453.48 rows=1 width=4)"
" -> Sort (cost=453.25..453.48 rows=94 width=4)"
" Sort Key: flg_rid"
" -> Bitmap Heap Scan on prj_frm_flg (cost=5.55..450.17
rows=94 width=4)"
" Recheck Cond: (flg_mid = 3)"
" Filter: ((NOT flg_fav) AND (NOT flg_notif) AND (NOT
flg_post))"
" -> Bitmap Index Scan on prj_frm_flg_pkey
(cost=0.00..5.53 rows=117 width=0)"
" Index Cond: (flg_mid = 3)"

I suppose that the problem comes from the Bitmap Heap Scan which costs
a lot, but I can't be totally sure.

Any idea on where I should be investigating ?

Thanks a lot.
Mat.