Melhor forma de fazer essa consulta

Possuo a consulta abaixo e gostaria de melhorar, ela esta demorando 4 segundos para ser feita.

Qual a opinião de vocês?

Já possuo index nas consultas.

SELECT nome, clientesid, dataentrada, datasaida, aluguelID, datacontrato
 FROM contratos
 WHERE contratos.datacontrato > '2013-05-01' AND contratos.status != '1' AND clientesid NOT IN
 (
 SELECT contratosid FROM pagamentos WHERE pagamentos.cliente = '1'
 UNION ALL
 SELECT contratosid FROM pagcielo WHERE pagcielo.confirmado = '1'
 UNION ALL
 SELECT contratosid FROM pagboleto WHERE pagboleto.status = '1'
 )
 ORDER BY contratos.datacontrato ASC;