Query de 40 horas?

buenos dias:

Mi problema es el siguiente: Tengo una tabla TABLA_BASE de
aproximadamente 42 millones de registros con una clave unica y otra
tabla TABLAAUX con aproximadamente 21 millones de registros con datos
que tengo que actualizar en la primera tabla.

En la primera tabla utilizo el siguiente query para crear los campos.

BEGIN TRAN
ALTER TABLE [TABLA_BASE] ADD [CAMPO_FLAG] [smallint] DEFAULT (0) NOT
NULL
ALTER TABLE [TABLA_BASE] ADD [RGS_FLAG] [smallint] DEFAULT (0) NOT
NULL
ALTER TABLE [TABLA_BASE] ADD [OTRO_FLAG] [smallint] DEFAULT (0) NOT
NULL
ALTER TABLE [TABLA_BASE] ADD [ESTADO] [smallint] DEFAULT (0) NOT NULL

ALTER TABLE [TABLA_BASE] ADD [FECHA] [datetime] DEFAULT ('2002-01-12
00:00:00.000') NOT NULL
ALTER TABLE [TABLA_BASE] ADD [CONTADOR] [smallint] DEFAULT (0) NOT
NULL
COMMIT
GO
Cuando ejecuto el query en pruebas, se demora aproximadamente 40 Horas.
como este procedimiento se ejecutara solo UNA VEZ en produccion, se
puede manejar. pero el inconveniente es en los procesos mensuales en
los cuales actualizo estos campos. El query a utilizar sera este:

BEGIN TRAN
UPDATE TABLA_BASE
SET FECHA = '2005-02-01 00:00:00.000',
CONTADOR = CONTADOR + 1,
CAMPO_FLAG = CASE WHEN P.CAMPO_FLAG < C.VALOR THEN C.VALOR ELSE
P.CAMPO_FLAG END
FROM TABLA_BASE P INNER JOIN TABLAAUX C ON (C.CLAVE = P.CLAVE)
COMMIT
GO

El query anterior en pruebas lleva 60 horas y no ha terminado. Ekl
tiempo maximo permitido en produccion para este procedimiento seria de
20 horas. ya he probado enviandolo desde un procedimiento almacenado
pero el tiempo se reduce muy poco.

Pregunta: esto es normal por la cantidad de registros ha actualizar (21
millones) ó es un problemas al crear los campos con valores por
defecto?.

El problema es que con estos tiempos cada prueba completa se me demora
casi una semana

gracias por cualquier ayuda a disminuir estos tiempos.