Кой е най-добрият начин да получите общ брой записи в mysql таблица с php?

Правилно ти казаха. mysql може да направи това преброяване вместо вас, което е много по-ефективно.

$result = mysql_query( "select count(id) as num_rows from table" );
$row = mysql_fetch_object( $result );
$total = $row->num_rows;