> Ну да. Начиная с COUNT(*) который полным сканированием определяется,

В 5.7, кстати select count(*) чуток ускорили.
InnoDB: SELECT COUNT(*) FROM t statements now invoke a single handler call to the storage
engine to scan the clustered index and return the row count to the Optimizer. Previously, a row count was typically performed by traversing a smaller secondary index and invoking a handler call for each record. A single handler call to the storage engine to count rows in the clustered index improves SELECT COUNT(*) FROM t performance in most cases. For more information, see Limits on InnoDB Tables.

Сделать без скана довольно сомнительно: каким образом правильное количество должно возвращаться для кучи параллельных транзакций?

> заканчивая явными глюками оптимизатора, которые может когда нибудь и починят.

большая часть проблем связана со статистикой. При неравномерном распределении значений статистика указывает оптимизатору пальцем в небо.

В 8.0 добавили гистограммы в статистику: https://dev.mysql.com/doc/refman/8.0/en/optimizer-statistics... так что надо смотреть как оно на реальных запросах и базах будет помогать.