Rachel Byford (4/22/2009)
My belief was that as a consequence of the union removing duplicates, the output always came out ordered. Possibly not if you end up with several worker processes doing the work, but in this case that won't happen.
Several workers processing the output is extremely unlikely, given the small amount of data. But the method of removing duplicates can affect the results. SQL Server has different strategies for removing duplicates. The one you are thinking of uses a Sort step to bring duplicates together, followed by a Stream Aggregate step to remove them. This one is not used by this query (at least not on my machine; as I already indicated, this depends on a lot of factors and results may vary based on different versions of SQL Server, different hardware, and different workload).
The technique ussed on my computer (I checked by running the query with the "include actual execution plan" option activated) is to use a merge join between three one-row "tables". Due to how merge works, this will also cause the result set to be sorted.
A third technique for removing duplicates is a hash union. You can force SQL Server to use this technique by adding "OPTION (HASH UNION)" at the end of the query. On my machine, this changed the order of the output rows (though it might not have this effect on all machines, as the order now depends on the actual hashing function used, which is as far as I know not documented and might change between versions or even between service packs).
These are the three techniques for union that I am aware of. There may be more. And if there are no more now, they might be introduced at a later time, if someone in the SQL Server optimizer team comes up with a bright idea.
I can only repeat what I already said a million times: order of rows is never guaranteed, unless an explicit ORDER BY is present on the outermost query!