Mysql count prestanda på mycket stora bord

Du verkar inte vara intresserad av den faktiska räkningen så prova detta:

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

Om en rad returneras har du 5000 och fler poster. Jag antar att fk är kolumnen indexeras.