SQL Server: Avoiding a Sort with Merge Join Concatenation

One of the advantages of B-tree-based indexes is that they organize the data ordered by some index key. SQL Server can then rely on index order to present or process data ordered (for operations such as ORDER BY, GROUP BY and JOIN), without the penalty of an actual sort operation. Pulling the data preordered from an index has linear scaling since the cost of an ordered scan is simply proportional to the number of rows involved. Puling the data unordered and then applying an actual sort operation scales in an extra-linear fashion--more specifically, in an n log n fashion. So, if you often need to rely on ordered data, it’s beneficial to have supporting indexes. However, there are cases when SQL Server doesn’t normally realize it can rely on index order, but you can make the platform realize it with some extra manipulation and creativity. This article is the first in a two-part series in which I describe such tasks and solutions. This month I’ll talk about avoiding a sort with the Merge Join (Concatenation) operator. Next month I’ll describe avoiding a sort when needing the data in descending order.

Order Data with NULLs Last

Our first example for specialized ordering needs is a classic. I’ll use the Sales.Orders table in the TSQLV4 database for this example. The task is to return orders (orderid and shippeddate columns) ordered by shippeddate ascending, orderid ascending, but with NULLs last. Normally, SQL Server orders NULLs first. A common way for people to handle the task is by using a CASE expression as the first ordering expression returning a flag with higher ordering value for NULLs, and then shippeddate and orderid, like so:

<span style="color: #0000ff;">USE TSQLV4;</span>

<span style="color: #0000ff;"> </span>

<span style="color: #0000ff;">SELECT orderid, shippeddate</span>

<span style="color: #0000ff;">FROM Sales.Orders</span>

<span style="color: #0000ff;">ORDER BY</span>

<span style="color: #0000ff;">  CASE WHEN shippeddate IS NOT NULL THEN 0 ELSE 1 END,</span>

<span style="color: #0000ff;">  shippeddate, orderid;</span>

This solution returns the desired output with NULLs ordered last, as the query output shows:

<span style="color: #0000ff;">orderid     shippeddate</span>

<span style="color: #0000ff;">----------- -----------</span>

<span style="color: #0000ff;">10249       2014-07-10</span>

<span style="color: #0000ff;">10252       2014-07-11</span>

<span style="color: #0000ff;">10250       2014-07-12</span>

<span style="color: #0000ff;">10251       2014-07-15</span>

<span style="color: #0000ff;">10255       2014-07-15</span>

<span style="color: #0000ff;">...</span>

<span style="color: #0000ff;">11073       NULL</span>

<span style="color: #0000ff;">11074       NULL</span>

<span style="color: #0000ff;">11075       NULL</span>

<span style="color: #0000ff;">11076       NULL</span>

<span style="color: #0000ff;">11077       NULL</span>

<span style="color: #0000ff;"> </span>

There is an index called idx_nc_shippeddate defined on shippeddate and orderid (implied due to the presence of a clustered index on orderid). The problem is that since the first ordering expression manipulates columns, similar to breaking sargability of filters, it prevents SQL Server from being able to rely on index order in this example. This results in explicit sorting in the plan for this query as shown Figure 1, and therefore n log n scaling. 

Figure 1 – Order data with NULLs last, with Sort

There is a trick that you can apply as a workaround. Write two queries—one returning rows where shippeddate is not NULL, with a flag sort column (call it sortcol) based on the constant 0, and another returning rows where shippeddate is NULL, with the flag sort column based on the constant 1. Apply a UNION ALL operator between them, and place the whole thing in a CTE. Have the outer query against the CTE return the desired columns only, ordering the rows by sortcol, shippeddate and orderid. Here’s the complete solution’s code:

<span style="color: #3366ff;">WITH C AS</span>

<span style="color: #3366ff;">(</span>

<span style="color: #3366ff;">  SELECT orderid, shippeddate, 0 AS sortcol</span>

<span style="color: #3366ff;">  FROM Sales.Orders</span>

<span style="color: #3366ff;">  WHERE shippeddate IS NOT NULL</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">  UNION ALL</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">  SELECT orderid, shippeddate, 1 AS sortcol</span>

<span style="color: #3366ff;">  FROM Sales.Orders</span>

<span style="color: #3366ff;">  WHERE shippeddate IS NULL</span>

<span style="color: #3366ff;">)</span>

<span style="color: #3366ff;">SELECT orderid, shippeddate</span>

<span style="color: #3366ff;">FROM C</span>

<span style="color: #3366ff;">ORDER BY sortcol, shippeddate, orderid;</span>

The plan for this query is shown in Figure 2.

Figure 2 –

Notice in the plan that there are two index seeks used to obtain the data—one for the rows where shippeddate is not NULL (emitted ordered by shippeddate and orderid) and another where shippeddate is NULL (also emitted ordered by shippeddate and orderid). The two Compute Scalar operators produce the flag based on the constant—0 for rows where shippeddate is not NULL and 1 for rows where shippeddate is NULL. The Merge Join (Concatenation) operator than merges the two ordered inputs based on the order of: flag column, shippeddate and orderid. This operator is similar to the Merge Join operator, only instead of joining, it unifies two sorted inputs. Figure 3 illustrates how this operator works with a simplified example of two sorted integer inputs.

Figure 3 - Illustration of Merge Join (Concatenation)

The algorithm is pretty simple:

·       Fetch the first row in each of the sorted inputs.

·       While not reached the end of any of the inputs:

o   If the left sort key is less than or equal to the right sort key, emit the left row and read the next row from the left input. Otherwise, emit the right row and read the next row from the right input.

·       If any rows are left in any of the inputs, emit those.

The beauty of this algorithm is that it can be applied to preordered inputs based on index order scans (or seeks and range scans), like in the plan shown in Figure 2, meaning that in such a case the plan scales linearly.

Window function with NULLs last

The Merge Join (Concatenation) operator can be used to produce ordered unified rows for any purpose—not just for presentation ordering purposes. For example, window functions, such as ROW_NUMBER, need the data sorted by the window partitioning and window ordering columns, or just by the window ordering columns if there’s no window partition clause. For example, suppose you wanted to compute rows numbers for orders based on shippeddate ascending, orderid ascending ordering, but again, with NULLs last. Just like with the previous example, here in the window order clause you can start with a CASE expression that produces a flag with a higher ordering value for NULLs than for non-NULL values, and then continue with shippeddate and orderid, like so: 

<span style="color: #3366ff;">SELECT orderid, shippeddate,</span>

<span style="color: #3366ff;">  ROW_NUMBER() OVER(ORDER BY</span>

<span style="color: #3366ff;">                     CASE WHEN shippeddate IS NOT NULL THEN 0 ELSE 1 END,</span>

<span style="color: #3366ff;">                     shippeddate, orderid) AS rownum</span>

<span style="color: #3366ff;">FROM Sales.Orders;</span>

You get the following output showing row numbers starting with 1 for the non-NULL shipped dates, and with the last range of row numbers assigned to rows with a NULL shipped date:

<span style="color: #3366ff;">orderid     shippeddate rownum</span>

<span style="color: #3366ff;">----------- ----------- --------------------</span>

<span style="color: #3366ff;">10249       2014-07-10  1</span>

<span style="color: #3366ff;">10252       2014-07-11  2</span>

<span style="color: #3366ff;">10250       2014-07-12  3</span>

<span style="color: #3366ff;">10251       2014-07-15  4</span>

<span style="color: #3366ff;">10255       2014-07-15  5</span>

<span style="color: #3366ff;">...</span>

<span style="color: #3366ff;">11073       NULL        826</span>

<span style="color: #3366ff;">11074       NULL        827</span>

<span style="color: #3366ff;">11075       NULL        828</span>

<span style="color: #3366ff;">11076       NULL        829</span>

<span style="color: #3366ff;">11077       NULL        830</span>

The plan for this query is shown in Figure 4.

Figure 4 – Window function with NULLs last, with Sort

As in Figure 1, due to the fact that the window order clause starts with an expression that manipulates columns, the optimizer doesn’t rely on index order and applies explicit sorting. Just like in the previous example, you can avoid explicit sorting by using unioned queries with a sort flag (sortcol), only here it’s the window order clause—not the presentation order clause—that is based on sortcol, shippeddate and orderid. Here’s the complete solution query:

<span style="color: #3366ff;">WITH C AS</span>

<span style="color: #3366ff;">(</span>

<span style="color: #3366ff;">  SELECT orderid, shippeddate, 0 AS sortcol</span>

<span style="color: #3366ff;">  FROM Sales.Orders</span>

<span style="color: #3366ff;">  WHERE shippeddate IS NOT NULL</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">  UNION ALL</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">  SELECT orderid, shippeddate, 1 AS sortcol</span>

<span style="color: #3366ff;">  FROM Sales.Orders</span>

<span style="color: #3366ff;">  WHERE shippeddate IS NULL</span>

<span style="color: #3366ff;">)</span>

<span style="color: #3366ff;">SELECT orderid, shippeddate,</span>

<span style="color: #3366ff;">  ROW_NUMBER() OVER(ORDER BY sortcol, shippeddate, orderid) AS rownum</span>

<span style="color: #3366ff;">FROM C;</span>

The plan for this query is shown in Figure 5. 

Figure 5 – Window function with NULLs last, with Merge Join (Concatenation)

 Observe the use of the Merge Join (Concatenation) applied to the two preordered inputs, emitting the unified rows sorted like the window function needs; hence, no explicit sorting is used.

In other articles I cover solutions to tasks involving intervals where I rely on this trick to avoid explicit sorting. You can find examples in a series I wrote about Calculating Concurrent Sessions (Part 1, Part 2, Part 3), and in an article on Packing Intervals. In those solutions I unify interval start times with interval end times to one chronologically ordered sequence of events, and, using the Merge Join (Concatenation) operator, avoid the need for explicit sorting.

Unpivoting

Another example where the Merge Join (Concatenation) operator can be used to avoid explicit sorting is in ordering of unpivoted data. To demonstrate the technique, I’ll use a table called CustSales, which you create and populate with 1,000,000 rows by running the following code:

<span style="color: #3366ff;">USE tempdb;</span>

<span style="color: #3366ff;">DROP TABLE IF EXISTS dbo.CustSales;</span>

<span style="color: #3366ff;">GO</span>

<span style="color: #3366ff;">CREATE TABLE dbo.CustSales</span>

<span style="color: #3366ff;">(</span>

<span style="color: #3366ff;">  custid INT NOT NULL</span>

<span style="color: #3366ff;">    CONSTRAINT PK_CustSales PRIMARY KEY,</span>

<span style="color: #3366ff;">  val2016 NUMERIC(12, 2) NULL,</span>

<span style="color: #3366ff;">  val2017 NUMERIC(12, 2) NULL,</span>

<span style="color: #3366ff;">  val2018 NUMERIC(12, 2) NULL,</span>

<span style="color: #3366ff;">);</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">INSERT INTO dbo.CustSales WITH (TABLOCK) (custid, val2016, val2017, val2018)</span>

<span style="color: #3366ff;">  SELECT custid,</span>

<span style="color: #3366ff;">    NULLIF(val2016, 0) AS val2016,</span>

<span style="color: #3366ff;">    NULLIF(val2017, 0) AS val2017,</span>

<span style="color: #3366ff;">    NULLIF(val2018, 0) AS val2018</span>

<span style="color: #3366ff;">  FROM ( SELECT N.n AS custid,</span>

<span style="color: #3366ff;">           ABS(CHECKSUM(NEWID())) % 1000 AS val2016,</span>

<span style="color: #3366ff;">           ABS(CHECKSUM(NEWID())) % 1000 AS val2017,</span>

<span style="color: #3366ff;">           ABS(CHECKSUM(NEWID())) % 1000 AS val2018</span>

<span style="color: #3366ff;">         FROM TSQLV4.dbo.GetNums(1, 1000000) AS N ) AS D;</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">CREATE INDEX idx_val2016 ON dbo.CustSales(val2016, custid);</span>

<span style="color: #3366ff;">CREATE INDEX idx_val2017 ON dbo.CustSales(val2017, custid);</span>

<span style="color: #3366ff;">CREATE INDEX idx_val2018 ON dbo.CustSales(val2018, custid);</span>

 The CustSales table has a row per customer (custid) and a column per order year (valyyyy), with the total order values for the current customer and year. Observe the code creates an index on (valyyyy, custid) for each of the three order years. The task is to unpivot the data so that you get a row per customer and year, with one result column holding the year (call it orderyear) and another holding the value (call it val). In addition, you want the result to be sorted by the val column, ascending.

There are two main techniques people use to handle such unpivoting tasks—one using the UNPIVOT operator and another using the APPLY operator. Here’s the classic solution using the UNPIVOT operator:

<span style="color: #3366ff;">SELECT custid, CAST(RIGHT(valyear, 4) AS INT) AS orderyear, val</span>

<span style="color: #3366ff;">FROM dbo.CustSales</span>

<span style="color: #3366ff;">  UNPIVOT(val FOR valyear IN (val2016, val2017, val2018)) AS U</span>

<span style="color: #3366ff;">ORDER BY val;</span>

 Observe the explicit Sort operator in the plan. With 1,000,000 rows in the source table, it took this query 4 seconds to complete on my machine (with results discarded to focus on processing time). Due to the need for explicit sorting, this plan scales in an n log n fashion.

Here’s the solution using the APPLY operator:

<span style="color: #3366ff;">SELECT custid, orderyear, val</span>

<span style="color: #3366ff;">FROM dbo.CustSales</span>

<span style="color: #3366ff;">  CROSS APPLY ( VALUES(2016, val2016),</span>

<span style="color: #3366ff;">                      (2017, val2017),</span>

<span style="color: #3366ff;">                      (2018, val2018) ) AS A(orderyear, val)</span>

<span style="color: #3366ff;">WHERE val IS NOT NULL</span>

<span style="color: #3366ff;">ORDER BY val;</span>

 As you can see, the plan is very similar to the one used for the solution with the UNPIVOT operator, and also here the plan applies explicit sorting. This query too took 4 seconds to complete on my machine, and has n log n scaling.

If you’re unhappy with the plans that we got for both the UNPIVOT- and the APPLY-based solutions, you’re in the same boat as me. Your intuition should tell you that there may be a way to leverage the indexes that we have on the (valyyyy, custid) combinations. Indeed, such a solution exists. You write a separate query for each of the years, returning custid, the applicable yyyy constant as orderyear, and the respective valyyyy column as val, for rows where valyyyy is not NULL. You apply UNION ALL operators between the queries, and order the result by the column val, like so:

<span style="color: #3366ff;">SELECT custid, 2016 AS orderyear, val2016 AS val</span>

<span style="color: #3366ff;">FROM dbo.CustSales</span>

<span style="color: #3366ff;">WHERE val2016 IS NOT NULL</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">UNION ALL</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">SELECT custid, 2017 AS orderyear, val2017 AS val</span>

<span style="color: #3366ff;">FROM dbo.CustSales</span>

<span style="color: #3366ff;">WHERE val2017 IS NOT NULL</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">UNION ALL</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">SELECT custid, 2018 AS orderyear, val2018 AS val</span>

<span style="color: #3366ff;">FROM dbo.CustSales</span>

<span style="color: #3366ff;">WHERE val2018 IS NOT NULL</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">ORDER BY val;</span>

This technique leverages the order-preserving Merge Join (Concatenation operator), which relies on index order, twice—once between the queries that handle the years 2016 and 2017, and another time between the result and the query that handles the year 2018. This query completed in 1 second on my machine and has linear scaling.

Finally, just for fun, suppose that you want to unpivot the data, sorting the rows by val ascending, only this time keeping rows with NULLs in the val column, and having NULLs sorted last! This can be achieved by mixing the two techniques I described in the article—the one that orders NULLs last without sorting, and the one that unpivots data without sorting. This means that you need to unify six queries—one for each of the three years times each of the two NULL | non-NULL cases producing the sort flag (sortcol), like so:

<span style="color: #3366ff;">WITH C AS</span>

<span style="color: #3366ff;">(</span>

<span style="color: #3366ff;">  SELECT custid, 2016 AS orderyear, val2016 AS val, 0 AS sortcol</span>

<span style="color: #3366ff;">  FROM dbo.CustSales</span>

<span style="color: #3366ff;">  WHERE val2016 IS NOT NULL</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">  UNION ALL</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">  SELECT custid, 2016 AS orderyear, val2016 AS val, 1 AS sortcol</span>

<span style="color: #3366ff;">  FROM dbo.CustSales</span>

<span style="color: #3366ff;">  WHERE val2016 IS NULL</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">  UNION ALL</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">  SELECT custid, 2017 AS orderyear, val2017 AS val, 0 AS sortcol</span>

<span style="color: #3366ff;">  FROM dbo.CustSales</span>

<span style="color: #3366ff;">  WHERE val2017 IS NOT NULL</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">  UNION ALL</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">  SELECT custid, 2017 AS orderyear, val2017 AS val, 1 AS sortcol</span>

<span style="color: #3366ff;">  FROM dbo.CustSales</span>

<span style="color: #3366ff;">  WHERE val2017 IS NULL</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">  UNION ALL</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">  SELECT custid, 2018 AS orderyear, val2018 AS val, 0 AS sortcol</span>

<span style="color: #3366ff;">  FROM dbo.CustSales</span>

<span style="color: #3366ff;">  WHERE val2018 IS NOT NULL</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">  UNION ALL</span>

<span style="color: #3366ff;"> </span>

<span style="color: #3366ff;">  SELECT custid, 2018 AS orderyear, val2018 AS val, 1 AS sortcol</span>

<span style="color: #3366ff;">  FROM dbo.CustSales</span>

<span style="color: #3366ff;">  WHERE val2018 IS NULL</span>

<span style="color: #3366ff;">)</span>

<span style="color: #3366ff;">SELECT custid, orderyear, val</span>

<span style="color: #3366ff;">FROM C</span>

<span style="color: #3366ff;">ORDER BY sortcol, val;</span>

The plan for this solution (using SentryOne’s Plan Explorer) is shown in Figure 9.

Figure 9 – Plan for UNION ALL query, keeping NULLs

Amazingly, five Merge Join (Concatenation) operators are used in this plan, without the need for explicit sorting, hence this plan scales linearly.

Summary

This article demonstrates the use of query rewrites to enable the use of optimal optimization capabilities. The focus of this article was avoiding explicit sorting by using techniques that can leverage the Merge Join (Concatenation) order-reliant and order-preserving operator. Next month I’ll continue the coverage of explicit-sort avoidance by discussing queries that need to handle data in descending order.