InnoDB (the most common storage engine in MySQL) uses a clustered index. In other words, the "primary key index" IS the table. Also a COUNT(*) query has to acco

InnoDB (the most common storage engine in MySQL) uses a clustered index. In other words, the "primary key index" IS the table. Also a COUNT(*) query has to account for MVCC, ensuring that the count represents an accurate total for a specific isolated snapshot. So this is basically still true today, although MySQL 8 has started to add parallelized reads to improve performance for this situation.