O problema é que você está especificando duas condições com OR que se aplicam a tabelas separadas em sua consulta. Por causa disso, a busca de índice não clusterizado deve retornar a maioria ou todas as linhas em sua tabela grande porque a lógica OR significa que elas também podem corresponder à cláusula de condição na segunda tabela.

Observe o plano de execução SQL em todos os três exemplos acima e observe o número de linhas que saem da busca de índice não clusterizado da tabela grande. O resultado final pode retornar apenas 1.000 ou menos das 800.000 linhas da tabela, mas a cláusula OR significa que o conteúdo dessa tabela deve ser cruzado com a condicional na segunda tabela, pois OR significa que eles podem ser necessários para o resultado final saída da consulta.

Dependendo do seu plano de execução, a busca de índice pode extrair todas as 800.000 linhas na tabela grande porque elas também podem corresponder às condições da cláusula OR na segunda tabela. O UNION ALL é duas consultas separadas em uma tabela cada, portanto, a busca de índice só precisa gerar o conjunto de resultados menor que pode corresponder à condição dessa consulta.

Espero que isto faça sentido. Eu me deparei com a mesma situação ao refatorar instruções SQL de execução lenta.

Saúde,

André Ranieri