Optimize execution time of a php script

I have a php script that fetches large number of records from a mysql table, calls a web service and checks and updates each record based on the webservice response.
Script is executed by a cron job several times a day.
Execution time currently is more than 10 hours. I need to optimize the execution time/the script and the database.