Update con indices ?

Hola a todos,
Tengo el siguiente problema y quisiera saber si me pueden dar una ayuda.
En una tabla con aproximadamente un millon de registros necesito hacer una
actualizacion de un registro.
El problema es que con el update los tiempos de actualizacion son muy altos
ya que no me permite usar indices, o al menos no se como hacerlo, alguien me
podria aclarar esta duda ?

Muchas Gracias