Depends on the storage engine afair, but both innodb an myisam have either index or global metadata based solution for this. I think in myisam its an estimste if you use count(*) so you need to use count(id) to get an exact value. This is all well documented

count(*) doesn't do full table scan as it's not tied to specific data. It has special handling logic. The only case where it might have to do a full table scan is if you try to count() on a specific (nullable?) column without an index.

I've always had select count(*) do a full table scan (or at least take considerable time) in innodb... Did something change?

Without a WHERE clause, select count(*) still does a full table scan (or full index scan) in InnoDB, and probably always will.

It is optimized in MyISAM via table-level metadata, which is only possible because MyISAM doesn't use MVCC or support transactions.

In InnoDB, you can get an estimated row count from SHOW TABLE STATUS, but the estimate is based on table stats and can be wildly inaccurate.