Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

In standard SQL, the result of a union all is not guaranteed to be in any order. So, something like:

select 'A' as c union all select 'B'

Could return two rows in any order (although, in practice on any database I know of, 'A' will come before 'B').

In SQL Server, this turns into an execution plan using a "concatenation" physical operation.

I could easily imagine that the concatenation operation would scan its inputs, returning whatever input has records available. However, I found the following statement on the web (here):

The Query Processor will execute this plan in the order that the operators appear in the plan, the first is the top one and the last is the end one.

Question: Is this true in practice? Is this guaranteed to be true?

I haven't found any reference in Microsoft documentation that the inputs are scanned in order, from the first to the last. On the other hand, whenever I try running it, the results suggest that the inputs are, indeed, processed in order.

Is there a way to have the engine process more than one input at a time? My tests (using much more complicated expressions than constants) are on a parallel-enabled 8-core machine, and most queries do take advantage of the parallelism.

share|improve this question
    
This is all academic, correct? Do you care about the order the rows are returned or the order the queries are processed? I don't know if you can prove that any observed behavior is always guaranteed, one way or the other, unless you can manufacture a counter-example. In the absence of that, the way to fix the order that results are returned, of course, is to add an ORDER BY. I don't know if there is a "fix", or that there exists a need for a fix, if you can demonstrate that in some scenarios the queries are processed in a different order. –  Aaron Bertrand Apr 3 '13 at 0:48
    
PS the lack of any explicit, official documentation suggests to me that you should not depend on this "guarantee"... this is exactly the kind of thing that got people into trouble with ORDER BY in a view, and GROUP BY without ORDER BY, 8 years ago when SQL Server 2005's optimizer was released. With all of the new features coming in the next version of SQL Server, even if you think you can guarantee a specific behavior today, I wouldn't expect it to hold true (until it is documented to do so). –  Aaron Bertrand Apr 3 '13 at 0:50
    
@AaronBertrand . . . I think you are misinterpreting my question. I'm not depending on this behavior. I just haven't found where the documentation says that you can't depend on the ordering, which is why I asked the question. The reference on the web suggests that you can -- 1 for, 0 against. As for the practicality, I am starting to think that the use of union all unnecessarily serializes queries by waiting for the first input to complete before moving to the next input (this is perhaps a minor optimization because the inputs may run in parallel in a multi-threaded environment). –  Gordon Linoff Apr 3 '13 at 1:02
1  
I don't think I misinterpreted the question. What are you going to do with the results? Anyway I wouldn't necessarily call what you've discovered 1-0. How do you deem a simple-talk article by an outsider as official? For all we know this is just a guess based on observation. Microsoft is never going to publish official documentation saying x is not guaranteed to do y. This is one of the reasons we still, almost a decade later, have trouble convincing people that they can't rely on observed ordering without ORDER BY - there is no documentation that states "it's not guaranteed." –  Aaron Bertrand Apr 3 '13 at 1:23
    
The results in the test here indicate that it might run in parallel. It would be possible to trace page locks taken to test this hypothesis but I haven't got the time to do that myself. –  Martin Smith Apr 3 '13 at 9:13

2 Answers 2

up vote 7 down vote accepted

No, there is no documentation from Microsoft guaranteeing the behavior, therefore it is not guaranteed.

Additionally, assuming that the Simple Talk article is correct, and that the concatenation physical operator always processes inputs in the order shown in the plan (very likely to be true), then without a guarantee that SQL will always generate plans that keep the same the order of between the query and the query plan, you're only slightly better off.

We can investigate this further though. If the query optimizer was able to re-order the concatenation operator input, then there should exist rows in the undocumentated DMV, sys.dm_exec_query_transformation_stats corresponding to that optimization.

SELECT * FROM sys.dm_exec_query_transformation_stats 
    WHERE name LIKE '%CON%' OR name LIKE '%UNIA%'

On Sql 2012 Enterprise Edition, this produces 24 rows. Ignoring the false matches for transformations related to constants, there is one transformation related to the CONCATENATION Physical Operator UNIAtoCON (Union All to Concatenation). So, at the physical operator level, it appears that once a concatenation operator is selected, it will be processed in the order of the logical Union ALL operator it was derived from.

But about the Logical Union All operator (UNIA)? There is a UNIAReorderInputs transformation, which sounds like it will switch the order of the inputs. There also appear to be two physical operators that can be used to implement a logical Union All, UNIAtoCON and UNIAtoMERGE (Union All to Merge Join). Therefore it appears that the query optimizer can reorder the inputs for a UNION ALL, however, it doesn't appear to be a common transformation (zero uses of UNIAReorderInputs on the Sql Servers I have readily accessible.) Also we don't know the circumstances that would make the optimizer use UNIAReorderInputs; it may only be applicable to a Union All implemented with a MERGE JOIN.

Regarding your second question, "Is there a way to have the engine process more than one input at a time?" The concatenation physical operator can exist within a parallel section of a plan. With some difficulty, I was able to produce a plan with parallel concatenations using the following query:

SELECT userid, regdate  FROM (  --Users table is around 3mil rows
    SELECT  userid, RegDate FROM users WHERE userid > 1000000
    UNION 
    SELECT  userid, RegDate FROM users WHERE userid < 1000000
    UNION all
    SELECT userid, RegDate FROM users WHERE userid < 2000000
    ) d ORDER BY RegDate OPTION (RECOMPILE)

So, in the strictest sense, the physical concatenation operator does seem to always process inputs in a consistent fashion (top one first, bottom second), however, the optimizer could switch the order of the inputs before choosing the physical operator, or use a MERGE join instead of a concatentation.

This is all speculation.

share|improve this answer
    
Speculation it may be but it's good stuff! –  Mark Storey-Smith Apr 8 '13 at 17:19
    
SELECT 1 WHERE EXISTS(SELECT COUNT(*) FROM master..spt_values HAVING COUNT(*)= 1 UNION ALL SELECT COUNT(*) FROM master..spt_monitor HAVING COUNT(*)<>1) does process the inputs in opposite order from written (presumably cheapest one first?) but does not seem to use UNIAReorderInputs –  Martin Smith Apr 9 '13 at 13:06
    
Which version are you seeing that behavior, I'm seeing it keep the the order of the inputs. Microsoft SQL Server 2012 - 11.0.2383.0 (X64) Oct 5 2012 19:35:54 Copyright (c) Microsoft Corporation Enterprise Edition (64-bit) on Windows NT 6.1 <X64> (Build 7601: Service Pack 1) –  StrayCatDBA Apr 11 '13 at 3:01
1  
I was on 2008, Just tested on 2012 and see same as you. On 2008 SELECT 1 WHERE EXISTS(SELECT COUNT(*) FROM master..spt_monitor HAVING COUNT(*)<> 1 UNION ALL SELECT COUNT(*) FROM master..spt_values HAVING COUNT(*)= 1) gives the same plan as the original query despite the order of the conditions being reversed –  Martin Smith Apr 11 '13 at 7:01

According to Craig Freedman the order of execution for the concatenation operator is guaranteed.

From his blog post Viewing Query Plans on MSDN Blogs:

Note that when an operator has more than one child, the order of the children matters. The topmost child is the first child while the bottommost child is the second. The concatenation operator processes the children in this order.

And from books online Showplan Logical and Physical Operators Reference

The Concatenation physical operator has two or more inputs and one output. Concatenation copies rows from the first input stream to the output stream, then repeats this operation for each additional input stream.

share|improve this answer
    
This is an interesting point. I am looking for documentation that guarantees the ordering (at least in specific versions). –  Gordon Linoff Jun 22 at 15:51
    
@GordonLinoff added a quote from documentation for SQL Server 2014. It does not of course guarantee the order of rows in the result. Only the order of execution between child operators. –  Mikael Eriksson Jun 22 at 17:27
    
That quote is pretty close to what I was looking for. I am willing to take the leap from being executed in that order to being returned in that order -- although it is disappointing that the documentation precludes parallel processing in this case. –  Gordon Linoff Jun 23 at 6:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.