Eu tive a mesma exigência. Os índices não podem ser adicionados a um CTE. No entanto, no CTE, selecione adicionar um ORDER BY cláusula nos campos unidos reduziu o tempo de execução de 20 minutos ou mais para menos de 10 segundos.

(Você também precisa ADD SELECT TOP 100 PERCENT para permitir um ORDER BY em um CTE select.)

[editar para adicionar citação parafraseada de um comentário abaixo]:
Se você tem DISTINCT no CTE então TOP 100 PERCENT não funciona. Este método trapaceiro está sempre disponível:sem precisar de TOP no select, altere a instrução ORDER BY para ler:
ORDER BY [Blah] OFFSET 0 ROWS