Ajuda com o Plano de Execução

Tenho o seguinte script:

DELETE FROM Clientes_Avisos
WHERE EXISTS (
SELECT * FROM #TMP_Clientes B
WHERE Clientes_Avisos.Cod_Empresa = B.Cod_Empresa
AND Clientes_Avisos.Cod_Cliente = B.Cod_Cliente )
AND Clientes_Avisos.Cod_Empresa = 3

A tabela Clientes_Avisos possui somente 67904 registros e a tabela
temporária TMP_Clientes possui aproximadamente 15000 registros.

Simplês, mas quando executo o script acima, ele leva mais de 24 minutos para terminar.

Analisando o Plano de Execução, encontrei um Table Spool/Lazy Spool com as seguintes informações:

Physical operation: Table Spool
Logical operation: Lazy Spool
Row count: 491.125.546
Estimated row size: 15
I/O cost: 1,00
CPU cost: 3,00
Numbers of executes: 33254
Cost: 3,0000000(0¬)
Subtree cost: 6,0
Estimated row count: 1

Alguém tem alguma sugestão para melhorar isso?

Att
Roberto