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