Bases de Datos - Problemas de rendimiento

Saludos...
Tengo un problema de rendimiento ejecutando un stored procedure, que me actualiza una tabla de millones de registros.
Que podría revisar en esta tabla que hace que se demore mucho la actualización.

Ya la tabla tiene algunos indices.

Que mas poría revisar?

Gracias y atento a sus comentarios

Existe un truco para la actualizacion masiva de registros, NUNCA debes hacer un simple UPDATE a una tabla que tienes MILLONES DE REGISTROS, es mejor que la metas en un ciclo, ejemplo

-- Actualiza de 100 mil, en 100 mil
SET ROWCOUNT 100000
WHILE EXISTS (SELECT * FROM CLIENTE WHERE SALDO < 5)
BEGIN
UPDATE CLIENTE SET SALDO = 10 WHERE SALDO < 5
CONTINUE
END

Con esto, podras interrumpir en cualquier momento y no hara mas que un ROLLBACK de 100 mil registros o menos.

Por otro lado, cuando termines de actualizar tus registros, debes hacer un respaldo de tu log.

En tu analizador de consultas, ejecuta:

CHECKPOINT
CHECKPOINT
CHECKPOINT
BACKUP LOG tubase WITH TRUNCATE_ONLY