Sie scheinen nicht an der tatsächlichen Anzahl interessiert zu sein, also versuchen Sie es hiermit:
SELECT 1 FROM table WHERE fk = 1 LIMIT 5000, 1
Wenn eine Zeile zurückgegeben wird, haben Sie 5000 und mehr Datensätze. Ich vermute das fk Spalte wird indiziert.
