Extremely slow count (simple query, with index)

Hello!

Any help would be greatly appreciated.
I need to run these simple queries on a table with millions of rows:

```
SELECT COUNT(*) FROM "subscriptions" WHERE "subscriptions"."project_id" =
123;
```

```
SELECT COUNT(*) FROM "subscriptions" WHERE "subscriptions"."project_id" =
123 AND "subscriptions"."trashed_at" IS NULL;
```

The count result for both queries, for project 123, is about 5M.

I have an index in place on `project_id`, and also another index on
`(project_id, trashed_at)`:

```
"index_subscriptions_on_project_id_and_created_at" btree (project_id,
created_at DESC)
"index_subscriptions_on_project_id_and_trashed_at" btree (project_id,
trashed_at DESC)
```

The problem is that both queries are extremely slow and take about 17s each.

These are the results of `EXPLAIN ANALIZE`:

```
QUERY PLAN

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=2068127.29..2068127.30 rows=1 width=0) (actual
time=17342.420..17342.420 rows=1 loops=1)
-> Bitmap Heap Scan on subscriptions (cost=199573.94..2055635.23
rows=4996823 width=0) (actual time=1666.409..16855.610 rows=4994254 loops=1)
Recheck Cond: (project_id = 123)
Rows Removed by Index Recheck: 23746378
Heap Blocks: exact=131205 lossy=1480411
-> Bitmap Index Scan on
index_subscriptions_on_project_id_and_trashed_at (cost=0.00..198324.74
rows=4996823 width=0) (actual time=1582.717..1582.717 rows=4994877 loops=1)
Index Cond: (project_id = 123)
Planning time: 0.090 ms
Execution time: 17344.182 ms
(9 rows)
```

```
QUERY PLAN

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=2047881.69..2047881.70 rows=1 width=0) (actual
time=17557.218..17557.218 rows=1 loops=1)
-> Bitmap Heap Scan on subscriptions (cost=187953.70..2036810.19
rows=4428599 width=0) (actual time=1644.966..17078.378 rows=4994130 loops=1)
Recheck Cond: ((project_id = 123) AND (trashed_at IS NULL))
Rows Removed by Index Recheck: 23746273
Heap Blocks: exact=131144 lossy=1480409
-> Bitmap Index Scan on
index_subscriptions_on_project_id_and_trashed_at (cost=0.00..186846.55
rows=4428599 width=0) (actual time=1566.163..1566.163 rows=4994749 loops=1)
Index Cond: ((project_id = 123) AND (trashed_at IS NULL))
Planning time: 0.084 ms
Execution time: 17558.522 ms
(9 rows)
```

What is the problem?
What can I do to improve the performance (i.e. count in a few seconds)?

I have also tried to increase work_mem from 16MB to 128MB without any
improvement.
Even an approximate count would be enough.
Postgresql v9.5