Se till att du rensar exekvering + datacache mellan varje testkörning.
t.ex.
DBCC FREEPROCCACHE
DBCC DROPCLEANBUFFERS
Om du kör med UNION ALL först och sedan kör de 2 valen separat efteråt, kommer data redan att cachelagras i minnet vilket gör prestandan mycket bättre (det ger därför det felaktiga intrycket att det efterföljande tillvägagångssättet är snabbare när det kanske inte är det).
Om du använde en UNION kan det mycket väl vara långsammare eftersom den måste tillämpa en DISTINCT, men UNION ALL behöver inte göra det så det borde inte vara annorlunda.
Uppdatering:
Ta en titt på genomförandeplanerna och jämför dem – se om det är någon skillnad. Du kan se exekveringsplanen genom att klicka på knappen "Inkludera faktisk exekveringsplan" i SSMS innan du kör frågan
Uppdatering 2:
Baserat på fullständiga CTE:er, tror jag att jag skulle titta på att optimera dem - jag tror inte att UNION ALL faktiskt är problemet.
IMHO, det bästa du kan prova är att gå igenom CTE:erna en efter en och försöka optimera var och en individuellt så att när du sedan kombinerar dem alla i huvudfrågan, presterar de bättre.
t.ex. för tDictionaryStreets, vad sägs om att prova detta:
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 på varje tabell bör åtminstone ha ett index på. Försök att omarbeta tDictionarySubCities på samma sätt med joins också.