I would guess two issues:

1. In many cases, there is a ~30ms floor on operations if a server is non-local. That's true of virtually all services on AWS -- whether SQS, SNS, SES, RDS (MySQL/PostgreSQL), etc.

2. In many cases, rows are missing. A table has a million rows. Ten are deleted. It's not compacted. So it's not a simple size lookup. A lot of this depends on how the data is stored/indexed. That's something which is naively pretty slow, but easily optimized.

Postgres can require a full table scan in order to count the number of rows.

See: https://wiki.postgresql.org/wiki/Slow_Counting

In Postgres, because it uses MVCC, every count requires verifying the table row in the data segment. This means a sequential scan over the contents of the table to verify the rows exist and are visible to the current session.

Few operations have this particular limitation, and it's been a sticking point in the Postgres world for years. Unfortunately there's no easy way around it.