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