Unnecessary sorts in query plan

Kim Hansen 2015-10-03 14:57:23

Why does SQL Server do the two sorts in the attached query plan, I would have expected a Merge Join and a Stream Aggregate would have been enough and a lot faster.

The query is:

SELECT MIN(intfpostdate)
    SELECT job_unid, intfpostdate FROM revenue
    UNION ALL              
    SELECT job_unid, intfpostdate FROM jcrevenue
) AS _1
GROUP BY job_unid
ORDER BY job_unid

I have indexes on both the tables that are sorted by job_unid and includes intfpostdate.

Kim Hansen

Aaron Bertrand 2015-10-04 13:30:01
I couldn't reproduce your scenario where an additional SORT was required for job_unid on its own, since the index scans are already ordered (perhaps it would help in your case if intfpostdate were made the second column in the key list, but even that wasn't required for me). In my case I only had a single sort after the stream aggregate:

alt text

(Note that I had to append OPTION (MAXDOP 1) to get a plan similar to yours but without parallelism – do you have server-wide MAXDOP set to 1, or are achieving this through Resource Governor or a very high Cost Threshold for Parallelism setting? It's ok if you do, I am just curious why you're not getting a parallel plan in the first place.)

I tried I slightly more elaborate re-write of the query, attempting to get the grouping and aggregation done earlier:

  SELECT intfpostdate = MIN(intfpostdate), job_unid
    SELECT intfpostdate = MIN(intfpostdate), job_unid
    FROM dbo.revenue GROUP BY job_unid
    SELECT intfpostdate = MIN(intfpostdate), job_unid
    FROM dbo.jcrevenue GROUP BY job_unid
  ) AS y GROUP BY job_unid
SELECT intfpostdate FROM x
ORDER BY job_unid

This yielded a slightly simpler plan, most notably without a single Sort operator:

alt text

So, you could try that variation and see if it ends up any better on your system.

The major difference between our plans is that I built my sample data using AdventureWorks.Sales.SalesOrderHeader, which only has 31K distinct SalesOrderID values. In your case, you have close to 3 million unique job_unid values. So aside from me getting a much better representative data set to test with, I have to ask: does this query really need to return all 3 million rows? Whats most puzzling to me is you're returning 3 million dates, and they're sorted by job_unid, but job_unid isn't even in the output. Why? Is a user really going to consume 3 million rows for any purpose? What is the point of showing them a date without any clue about which job_unid it belongs to?

SQLkiwi 2015-10-04 14:37:30
To repro, you probably need a MERGE UNION hint to see the sorts. There are so many possible plans for this query though, it's hard to be certain.
Kim Hansen 2015-10-04 15:59:38
Just a quick note while I study these long answers.

We have a server wide MAXDOP of 1, I don't know why and haven't had time to find a reason or change it to something better.

We really do need 3 million rows, it is a report done daily in a BI application.

The reason the query returns only dates is that I have simplified it as much as possible, the real query is thousand lines long and returns hundreds of columns.

Kim Hansen 2015-10-07 21:06:24
I think this is the best way to avoid the sort, but I will probably live with the sort in order to avoid having to duplicate all the aggregations both inside and outside the sub-select.
SQLkiwi 2015-10-04 14:12:16
A simple Merge Concatenation and Stream Aggregate might execute faster on your system, but it is not the cheapest option according to the query optimizer's cost model. For example, simply using the table cardinalities from the submitted query plan, the 'simple' approach looks like this:

Simple plan

This has an estimated cost of 84.83 units on my test SQL Server 2014 instance. As the warning symbols on the scans above indicate, I do not have statistics on the tables, so your estimate will likely be different (also, we likely have different memory and CPU configurations). The estimated cost is mostly associated with the large number of rows passing through the Concatenation (21.7 million or so).

Note that the 'simple' plan above requires the index to have intfpostdate as a key column rather than an include.

The optimizer considers the option of pushing the aggregate below the Union All, performing a partial MIN(intfpostdate) aggregation, grouping on job_unid. The final aggregation (the global aggregate) remains above the Concatenation. Doing this on each input to the Concatenation produces:

Local/Global Agg Plan

Again the estimated row counts beyond the scans are likely incorrect due to the lack of statistics on my simulation, but the point is still evident: performing a partial aggregation early reduces the number of rows passing through the Concatenation significantly. On my system, this reduces the estimated cost from 84.83 to 37.15. On that basis, the optimizer chooses the plan shape you see.

Side note: The Sorts are required because merge requires inputs sorted on all joined (concatenated in this case) keys. Please see my article, "Avoiding Sorts with Merge Join Concatenation" for more details.

Strictly, the sorts are unnecessary, but the Concatenation implementation requires input sorts on e.g. (job_unid, partialaggresult) and the index can only provide order on (job_unid). Unfortunately, the optimizer is not able to reason in the way required to eliminate the sorts. You can get around this by writing the partial aggregates out manually (see Aaron's answer for an example of that).

Whether the optimizer's transformation pays off depends on a number of factors, not least of which how effective the partial aggregates are in reducing the row count, and whether the sorts are performed in memory or spill to disk. You did not provide a post-execution (actual) plan, so we can't know if the estimates were accurate at runtime or not.

There is no documented way to turn off this partial aggregate exploration option, but there are many ways to express the query differently, that may produce a different plan shape, again for example as shown in Aaron's answer (that he was writing concurrently, it seems).

I am using SQL Server 2014 SP1 CU 2 (build 12.00.4422) with the new CE model enabled. You are on build 12.00.2269, which is 2014 RTM (with an early security update). As a general observation, you should update to at least SP1, though this is unlikely to affect plan choice.


CREATE TABLE dbo.revenue
    job_unid integer NOT NULL, 
    intfpostdate datetime NOT NULL
CREATE TABLE dbo.jcrevenue
    job_unid integer NOT NULL, 
    intfpostdate datetime NOT NULL
CREATE INDEX i ON dbo.revenue (job_unid) INCLUDE (intfpostdate);
CREATE INDEX i ON dbo.jcrevenue (job_unid) INCLUDE (intfpostdate);
-- Pretend we have the right number of rows (but no stats and no idea of page count)
UPDATE STATISTICS dbo.jcrevenue WITH ROWCOUNT = 12925200;
Kim Hansen 2015-10-04 15:50:22
Thanks for the thorough answer. I think my problem is related the Concatenation implementation requiring that all columns are sorted. That is surprising to me, I thought that just having a limited set of columns sorted should be enough, is there a good reason for that limitation?
SQLkiwi 2015-10-05 03:43:58
AFAIK it's just a side-effect of the Merge Join operator being reused to implement Concatenation. The particular issue in this question is an unfortunate limitation in the way the optimizer reasons about ordering when a partial aggregate is introduced. I guess it's easy enough to workaround, but the reason for the sort is sneaky and hard to spot, I agree.
Kim Hansen 2015-10-07 21:04:24
Now I got time to read the article about avoiding sorts, good stuff. My guess is that the strange need for all columns being sorted is that they have reused code from "UNION" when implementing "UNION ALL". It would be nice if that was fixed some day…
SQLkiwi 2015-10-08 12:56:59
No, the fundamental code being reused is Merge Join, which requires inputs sorted on the join keys. For a union/union all, 'join keys' maps to 'all input columns'. Whether duplicates are removed or not is a smaller variation.