SQL Server has two types of execution plan iterators: Blocking and Non-Blocking.

A non-blocking iterator gets rows in and sends rows out at the same time. For instance, the Nested Loops iterator gets rows from its outer input and sends the matching rows on to the next iterator without having to wait for all of the input rows.

A blocking iterator, on the other hand, has to consume all of the input rows before it can send rows out to the next iterator.

The classic blocking iterator is Sort. It has to consume all of the input rows and sort them before it can send them on.

Or at least that’s what I thought for years…

In one of our company meetings, Eyal Golombek, one of our consultants, presented a session about sys.dm_exec_query_profiles. In one of his demos, Eyal used the following query (on Adam Machanic’s bigAdventureWorks database):

SELECT
      YEAR(transactiondate) AS YEAR_TRAN, 
      MONTH(transactiondate) AS MONTH_TRAN,
      FIRST_VALUE(p.productnumber) 
OVER (
PARTITION BY YEAR(transactiondate), MONTH(transactiondate) 
ORDER BY transactiondate) 
  AS first_product_nb,
      LAST_VALUE(p.productnumber) 
OVER (
PARTITION BY YEAR(transactiondate), MONTH(transactiondate) 
ORDER BY transactiondate) 
AS last_product_nb
FROM 
dbo.bigtransactionhistory AS A
    JOIN dbo.bigproduct AS P
    ON a.productid = p.productid

The right side of the execution plan looks like this:

Monitoring the query progress using sys.dm_exec_query_profiles showed that the Sort iterator doesn’t act quite like described above. It seemed to produce output rows while it’s still sorting. How’s that possible? How can it send output rows before it finishes the sort?

Let’s take a closer look:

While the iterators to the right of the Sort work, the number of rows processed by the Sort iterator stays zero:

It’s only after all of the rows are consumed by the Sort iterator that its number of rows starts to climb:

This starts to make sense, since as we said, a blocking iterator has to consume all of the input rows before sending them on.

After all of the rows are consumed, we see that the number of rows starts to go up for the Sort iterator and for the iterators to its left. After a lot of observations, it seemed to me that the sorting algorithm SQL Server used allowed it to sort a chunk, send it on, sort another chunk and send it on, and so on. Now, all I needed was someone who could approve that it does work that way, and there’s no better man to do it than Paul White (blog | @SQL_Kiwi).

I sent Paul an email explaining what I saw, and indeed, Paul said that in most cases, SQL Server uses a variety of the Merge Sort algorithm, which starts producing sorted outputs as soon as all final runs start to be merged.

So there you have it. The Sort iterator is indeed a blocking iterator as it has to consume all of the input rows before it can start sorting. However, it doesn’t have to finish the sort before it can start sending the output rows on to the next iterator.

Image “Sorted van!” courtesy of net_efekt

The post Sort – Is it Really a Blocking Iterator? appeared first on .