Certifique-se de limpar os caches de execução + dados entre cada execução de teste.
por exemplo.
DBCC FREEPROCCACHE
DBCC DROPCLEANBUFFERS
Se você executar primeiro com o UNION ALL e depois executar os 2 selects separadamente, os dados já estarão armazenados em cache na memória, tornando o desempenho muito melhor (dando a falsa impressão de que a abordagem subsequente é mais rápida quando pode não ser).
Se você usou um UNION, isso pode ser mais lento, pois precisa aplicar um DISTINCT, mas UNION ALL não precisa fazer isso, então não deve ser diferente.
Atualização:
Dê uma olhada nos planos de execução e compare-os - veja se há alguma diferença. Você pode visualizar o plano de execução clicando no botão "Incluir Plano de Execução Real" no SSMS antes de executar a consulta
Atualização 2:
Com base nos CTEs completos fornecidos, acho que procuraria otimizar esses - não acho que o UNION ALL seja realmente o problema.
IMHO, a melhor coisa a tentar é trabalhar com os CTEs um por um e tentar otimizar cada um individualmente para que, quando você combinar todos na consulta principal, eles tenham um desempenho melhor.
por exemplo. para tDictionaryStreets, que tal tentar isso:
SELECT DISTINCT
r.KladrItemName AS RegionName,
a.KladrItemName AS AreaName,
c.KladrItemName AS CityName,
sc.KladrItemName AS SubCityName,
s.StreetName
FROM StreetNames s
JOIN tFoundStreets fs ON s.StreetName = fs.KladrItemName
LEFT JOIN tFoundRegions r ON s.RegionName = r.KladrItemName
LEFT JOIN tFoundAreas a ON s.AreaName = a.KladrItemName
LEFT JOIN tFoundCities c ON s.CityName = c.KladrItemName
LEFT JOIN tFoundSubCities sc ON s.SubCityName = scc.KladrItemName
KladrItemName em cada tabela deve ter pelo menos um índice on. Tente retrabalhar tDictionarySubCities da mesma forma com junções também.
