Nen Count() sollte doch recht schnell gehen. Insbesondere, wenn du da nur eine Tabelle im Spiel hast. MySQL speichert die Anzahl der Zeilen in einer Tabelle ja irgendwo und muss dann nicht über die ganze Tabelle laufen, wie das in dem Fall PostgreSQL machen würde.
Also einfach nen , das ist doch, was du brauchst oder?