非常に大きなテーブルでのMysqlカウントのパフォーマンス

実際の数には興味がないようですので、これを試してみてください：

SELECT 1 FROM table WHERE fk = 1 LIMIT 5000, 1

行が返される場合、5000以上のレコードがあります。 fkだと思います 列にインデックスが付けられます。