Mysql počítá výkon na velmi velkých stolech

Zdá se, že vás skutečný počet nezajímá, tak to zkuste:

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

Pokud je vrácen řádek, máte 5000 a více záznamů. Předpokládám, že fk sloupec je indexován.