A segunda instrução leva muito tempo porque precisa varrer toda a tabela para contar as linhas.
Uma coisa que você pode fazer é usar um índice:
CREATE INDEX ON tbl_oplog (deleted) INCLUDE (id);
VACUUM tbl_oplog; -- so you get an index only scan
Supondo que
id é a chave primária, seria muito melhor usar count(*) e omita o INCLUDE cláusula do índice. Mas o melhor é provavelmente usar uma estimativa:
SELECT t.reltuples * freq.f AS estimated_rows
FROM pg_stats AS s
JOIN pg_namespace AS n
ON s.schemaname = n.nspname
JOIN pg_class AS t
ON s.tablename = t.relname
AND n.oid = t.relnamespace
CROSS JOIN LATERAL
unnest(s.most_common_vals::text::boolean[]) WITH ORDINALITY AS val(v,id)
JOIN LATERAL
unnest(s.most_common_freqs) WITH ORDINALITY AS freq(f,id)
USING (id)
WHERE s.tablename = 'tbl_oplog'
AND s.attname = 'deleted'
AND val.v = ?;
Isso usa as estatísticas de distribuição para estimar a contagem desejada.
Se for apenas sobre paginação, você não precisa de contagens exatas.
Leia meu blog para saber mais sobre o tópico de contagem no PostgreSQL.
