Bitmap Heap Scan performance

Question

I have a big report table. Bitmap Heap Scan step take more than 5 sec.

Is there something that I can do? I add columns to the table, does reindex the index that it use will help?

I do union and sum on the data, so I don't return 500K records to the client.
I use postgres 9.1.
Here the explain:

 Bitmap Heap Scan on foo_table  (cost=24747.45..1339408.81 rows=473986 width=116) (actual time=422.210..5918.037 rows=495747 loops=1)
   Recheck Cond: ((foo_id = 72) AND (date >= '2013-04-04 00:00:00'::timestamp without time zone) AND (date <= '2013-05-05 00:00:00'::timestamp without time zone))
   Filter: ((foo)::text = 'foooooo'::text)
   ->  Bitmap Index Scan on foo_table_idx  (cost=0.00..24628.96 rows=573023 width=0) (actual time=341.269..341.269 rows=723918 loops=1)

Query:

explain analyze
SELECT CAST(date as date) AS date, foo_id, ....
from foo_table
where foo_id = 72
and date >= '2013-04-04'
and date <= '2013-05-05'
and foo = 'foooooo'

Index def:
Index "public.foo_table_idx"
   Column    |            Type
-------------+-----------------------------
 foo_id      | bigint
 date        | timestamp without time zone

 btree, for table "public.external_channel_report"

Table:
foo is text field with 4 different values.
foo_id is bigint with currently 10K distinct values.

Answer 1

Create a composite index on (foo_id, foo, date) (in this order).

Note that if you select 500k records (and return them all to the client), this may take long.

Are you sure you need all 500k records on the client (rather than some kind of an aggregate or a LIMIT)?