Why would a scan take so long?

EXPLAIN SELECT count(DISTINCT catalog.id) FROM catalog WHERE flag=false;
                                       QUERY PLAN
-----------------------------------------------------------------------------------------
 Aggregate  (cost=1615927.27..1615927.28 rows=1 width=8)
   ->  Seq Scan on catalog  (cost=0.00..1603214.56 rows=5085084 width=8)
         Filter: (NOT flag)

SELECT pg_size_pretty(pg_relation_size('catalog'));
 pg_size_pretty
----------------
 9380 MB

Nothing else is going on the system, during the query disk reads rise from
around 0 to > 100MB/s, so I would assume it should take a couple minutes
and it takes ten times longer:
Time: 1495549.716 ms

What am I missing?

--
Michal Politowski