Уверете се, че сте изчистили кешовете за изпълнение + данни между всяко тестово изпълнение.
напр.
DBCC FREEPROCCACHE
DBCC DROPCLEANBUFFERS
Ако стартирате първо с UNION ALL и след това изпълните 2 селекта поотделно след това, данните вече ще бъдат кеширани в паметта, което прави производителността много по-добра (поради което създавате погрешно впечатление, че последващият подход е по-бърз, когато може да не е).
Ако сте използвали UNION, това може да е по-бавно, тъй като трябва да приложи DISTINCT, но UNION ALL не трябва да прави това, така че не трябва да е по-различно.
Актуализация:
Разгледайте плановете за изпълнение и ги сравнете - вижте дали има разлика. Можете да видите плана за изпълнение, като щракнете върху бутона „Включване на действителен план за изпълнение“ в SSMS, преди да изпълните заявката
Актуализация 2:
Въз основа на дадените пълни CTE, мисля, че ще се опитам да ги оптимизирам - не мисля, че UNION ALL всъщност е проблемът.
IMHO, най-доброто нещо, което да опитате, е да работите през CTE един по един и да се опитате да оптимизирате всеки един поотделно, така че когато след това ги комбинирате всички в основната заявка, те да се представят по-добре.
напр. за tDictionaryStreets, какво ще кажете да опитате това:
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 на всяка таблица трябва да има поне индекс на. Опитайте да преработите tDictionarySubCities по същия начин с обединения.