Ускорить подсчет строк в Postgresql

Question

Я прочитал Как ускорить подсчет строк в таблице PostgreSQL? и https://wiki.postgresql.org/wiki/Slow_Counting, но я не приближаюсь к лучшему результату. Проблема с большинством ответов в другом вопросе не имеет никакой фильтрации и основывается на статистике всей таблицы.

У меня есть таблица из примерно 10 миллионов строк, в настоящее время данные извлекаются в страницах (я знаю, что эта стратегия разбивки на страницы не идеальна), и мне нужно отобразить общее количество обратно для пользователя (бизнес-требование). Запрос быстрый, обычно <200 мс и выглядит так: </p>

explain analyze
SELECT  DISTINCT ON (ID) table.*
FROM "table"
WHERE "table"."deleted_at" IS NULL
GROUP BY "table"."id"
ORDER BY "table"."id" DESC
LIMIT 25 OFFSET 200;


    QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=530.48..585.91 rows=25 width=252) (actual time=0.870..0.942 rows=25 loops=1)
   ->  Unique  (cost=87.00..19878232.36 rows=8964709 width=252) (actual time=0.328..0.899 rows=225 loops=1)
         ->  Group  (cost=87.00..15395877.86 rows=8964709 width=252) (actual time=0.327..0.747 rows=225 loops=1)
               Group Key: id
               ->  Index Scan Backward using table_pkey on table  (cost=87.00..10913523.36 rows=8964709 width=252) (actual time=0.324..0.535 rows=225 loops=1)
                     Filter: (deleted_at IS NULL)
                     Rows Removed by Filter: 397
 Planning time: 0.174 ms
 Execution time: 0.986 ms
(9 rows)

Time: 77.437 ms

Проблема в том, что когда я пытаюсь отобразить счет, через:

explain analyze
SELECT COUNT(*) AS count_all, "table"."id" AS id
FROM "table"
WHERE "table"."deleted_at" IS NULL
GROUP BY "table"."id";
                                                                      QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------
 GroupAggregate  (cost=87.00..21194868.36 rows=10282202 width=4) (actual time=0.016..16984.904 rows=10343557 loops=1)
   Group Key: id
   ->  Index Scan using table_pkey on table  (cost=87.00..5771565.36 rows=10282202 width=4) (actual time=0.012..11435.350 rows=10343557 loops=1)
         Filter: (deleted_at IS NULL)
         Rows Removed by Filter: 2170
 Planning time: 0.098 ms
 Execution time: 18638.381 ms
(7 rows)

Я не могу использовать вероятностные подсчеты прямо сейчас, но я также не могу жить с 10-50 секундами, чтобы вернуть отсчет. Есть ли другой способ ускорить это?