Otimização de algoritmo linear

Tenho uma dúvida com relação à execução de um script que tenho em meu projeto. Sei que muitos amigos aqui possuem anos de experiência, por isso posto essa pergunta. Nunca peguei um projeto grande para fazer, e por isso, simples laços com dados do MySQL eram suficientes, porém agora tenho uma quantidade MUITO grande de dados para tratar e todos eles precisam executar de tempos em tempos o mais rápido possível.

Dúvida - Tenho um algoritmo que faz a seguinte tarefa:

• Seleciono do banco de dados todos os registros ainda não pagos.
• Faço um foreach para cada um desses dados, comparando hash md5 do XML devolvido pelo web service de pagamento pelo hash que tenho previamente no banco de dados.
• Caso os hashs sejam diferentes, faço uma interação com o SimpleXML lendo alguns dados e salvando no banco.
• Envio um e-mail para o usuário mostrando que o pagamento foi alterado.
• Faço um hash md5 do xml atual e substituo do banco de dados o hash antigo.

Isso tudo é bem demorado, faço muito curl e interações, o script é lento para uma única consulta imagina para milhares! Alguém já passou por algo semelhante e sabe como otimizar esse processo, não usar um algoritmo linear como o meu, mas turbinar de alguma forma (que não conheço ainda) a resolução do problema?