Bitmap Heap Scan slowdown - Mailing list pgsql-general

I have a query that results in the folowing EXPLAIN ANALYZE:
---------------------
  Limit  (cost=0.00..537.96 rows=1 width=46) (actual time=53.869..53.871 rows=1 loops=1)
    ->  Index Scan using addr_order_idx on addr  (cost=0.00..234014.08 rows=435 width=46) (actual time=53.862..53.862
rows=1loops=1) 
          Index Cond: ((_order >= (-13499803183)::bigint) AND (_order <= 1000000::bigint))
          Filter: (...)
  Total runtime: 54.139 ms
---------------------
If, however, I change the limit (rows) from 1 to 20, the search results in a 1000x slowdown.
To focus attention, I do not provide the Filter, since the query is a bit sophisticated but always the same:
---------------------
Limit  (cost=3784.83..3784.88 rows=20 width=46) (actual time=44678.130..44678.136 rows=20 loops=1)
    ->  Sort  (cost=3784.83..3785.92 rows=435 width=46) (actual time=44678.126..44678.128 rows=20 loops=1)
          Sort Key: _order
          Sort Method:  top-N heapsort  Memory: 27kB
          ->  Bitmap Heap Scan on addr  (cost=830.40..3773.26 rows=435 width=46) (actual time=19.378..44663.303
rows=7188loops=1) 
                Recheck Cond: (((l12 = 37) OR (l12 = 65) OR (l12 = 69)) AND (woj = 18))
                Filter: (...)
                ->  BitmapAnd  (cost=830.40..830.40 rows=751 width=0) (actual time=17.643..17.643 rows=0 loops=1)
                      ->  BitmapOr  (cost=366.26..366.26 rows=19330 width=0) (actual time=5.478..5.478 rows=0 loops=1)
                            ->  Bitmap Index Scan on addrl12_idx  (cost=0.00..114.02 rows=6093 width=0) (actual
time=2.016..2.016rows=6736 loops=1) 
                                  Index Cond: (l12 = 37)
                            ->  Bitmap Index Scan on addrl12_idx  (cost=0.00..72.00 rows=3690 width=0) (actual
time=1.107..1.107rows=4170 loops=1) 
                                  Index Cond: (l12 = 65)
                            ->  Bitmap Index Scan on addrl12_idx  (cost=0.00..179.92 rows=9547 width=0) (actual
time=2.350..2.350rows=8768 loops=1) 
                                  Index Cond: (l12 = 69)
                      ->  Bitmap Index Scan on addrwoj_idx  (cost=0.00..463.78 rows=24994 width=0) (actual
time=10.969..10.969rows=25141 loops=1) 
                            Index Cond: (woj = 18)
  Total runtime: 44678.462 ms
---------------------
The obvious cause is a bad plan, possibly the application of the Bitmap Heap Scan.
If, however, I physically remove the addrwoj_idx, I get pretty good results from Index Scan.
---------------------
  Limit  (cost=0.00..10759.27 rows=20 width=46) (actual time=44.064..613.733 rows=20 loops=1)
    ->  Index Scan using addr_order_idx on addr  (cost=0.00..234014.08 rows=435 width=46) (actual time=44.056..613.696
rows=20loops=1) 
          Index Cond: ((_order >= (-13499803183)::bigint) AND (_order <= 1000000::bigint))
          Filter: (...)
  Total runtime: 614.009 ms
---------------------
In the following last example, I bring back the addrwoj_idx and slightly modify the query.
The results are acceptable again, now utilizing the Bitmap Heap Scan:
---------------------
  Limit  (cost=3732.26..3732.31 rows=20 width=46) (actual time=928.991..928.999 rows=20 loops=1)
    ->  Sort  (cost=3732.26..3733.35 rows=435 width=46) (actual time=928.987..928.992 rows=20 loops=1)
          Sort Key: _order
          Sort Method:  top-N heapsort  Memory: 27kB
          ->  Bitmap Heap Scan on addr  (cost=830.40..3720.69 rows=435 width=46) (actual time=13.595..922.792 rows=7187
loops=1)
                Recheck Cond: (((l12 = 37) OR (l12 = 65) OR (l12 = 69)) AND (woj = 18))
                Filter: (...) slightly modified
                ->  BitmapAnd  (cost=830.40..830.40 rows=751 width=0) (actual time=12.341..12.341 rows=0 loops=1)
                      ->  BitmapOr  (cost=366.26..366.26 rows=19330 width=0) (actual time=5.224..5.224 rows=0 loops=1)
                            ->  Bitmap Index Scan on addrl12_idx  (cost=0.00..114.02 rows=6093 width=0) (actual
time=1.777..1.777rows=6736 loops=1) 
                                  Index Cond: (l12 = 37)
                            ->  Bitmap Index Scan on addrl12_idx  (cost=0.00..72.00 rows=3690 width=0) (actual
time=1.090..1.090rows=4170 loops=1) 
                                  Index Cond: (l12 = 65)
                            ->  Bitmap Index Scan on addrl12_idx  (cost=0.00..179.92 rows=9547 width=0) (actual
time=2.352..2.352rows=8768 loops=1) 
                                  Index Cond: (l12 = 69)
                      ->  Bitmap Index Scan on addrwoj_idx  (cost=0.00..463.78 rows=24994 width=0) (actual
time=6.412..6.412rows=25141 loops=1) 
                            Index Cond: (woj = 18)
  Total runtime: 929.254 ms
---------------------
Obviously, the Bitmap Heap Scan is not a cause of slowdown as such. One may notice that the
plans and cost estimates for the 2nd and 4th query are the same, but the resulting actual times differ substantially.

The search is done on a relavely small database (500k records, 2.1GB w/indexes). I've tried to tune the
postgres.conf options, including work_mem, effective_cache_size, etc., but it doesn't help. Setting
enable_bitmapscan = off does improve, but at the price of a slowdown of the other searches that normally
benefit from this flag set on.

Does anybody have any idea?
I have PG 8.4.16 running on a Linux VPS.
Wojtek