Qual è il modo migliore per ottenere il numero totale di record in una tabella MySQL con php?

Ti è stato detto correttamente. mysql può fare questo conteggio per te, il che è molto più efficiente.

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