The Curious Case of the Optimizer that doesn’t

The Curious Case of the Optimizer that doesn’t

The optimizer is the part of SQL Server that takes your query and reorders and rearranges your query to find the optimal execution plan. In theory.

In practice, that doesn’t always work out well. Often, the optimizer manages to come up with brilliant ways to execute a complex query very efficiently – but sometimes, it misses an option that appears to be so simple that you can only stare in utter amazement at the execution plan before going to the Connect site.

Here is an example I recently ran into. I tested it on SQL Server 2012 and on SQL Server 2008 R2, and it reproduces on both. Execute the query below in the AdventureWorks sample database, with the option to Include Actual Execution Plan enabled (Ctrl+M), or request an Estimated Execution Plan (Ctrl-L).

SELECT   TerritoryID,
Name,
SalesLastYear,
SalesYTD,
RANK() OVER (ORDER BY SalesLastYear) AS Rank1,
RANK() OVER (ORDER BY SalesYTD) AS Rank2
FROM     Sales.SalesTerritory
ORDER BY SalesLastYear;

When following the flow of data (by reading the execution plan from right to left), we see that the data is first read (with an unordered clustered index scan, since there is no better index available), then sorted by SalesLastYear, so that Rank1 can be computed (using two Segment operators and a Sequence Project operator – don’t ask). After that, the rows are sorted again, now by SalesYTD, and we see another combination of two Segment and one Sequence Project, for the calculation of Rank2. And then, finally, the rows are re-sorted by SalesLastYear so that they can be returned in the requested order.

Now the big question is: why does the plan include two sort operators that both sort the data in the same (SalesLastYear) order? If the task of the optimizer is to find smart ways to rearrange computation order for better performance, why doesn’t it simply compute Rank2 first and Rank1 after that? In that case, the rows are already in the SalesLastYear order after the last Sequence Project, so no extra sort is needed. The execution plan of the query below confirms this suspicion:

SELECT   TerritoryID,
Name,
SalesLastYear,
SalesYTD,
RANK() OVER (ORDER BY SalesYTD) AS Rank2,
RANK() OVER (ORDER BY SalesLastYear) AS Rank1
FROM     Sales.SalesTerritory
ORDER BY SalesLastYear;

Indeed, the execution plan of this query includes only two Sort operators instead of the three we had in the first execution plan. If you include both queries in a single batch, you’ll see an estimated cost of 59% for the first query, and 41% for the second. (Some people think that the percentages shown in an Actual Execution Plan are an indication of the actual cost; that is not the case – the percentages are computed from the Estimated Subtree Cost property of the left-most SELECT operator). The SalesTerritory table is too small to measure any actual performance differences, but I tried queries with a similar pattern on the SalesOrderDetail table (121,317 rows), and on FactProductInventory in AdventureWorksDW (776,286 rows) and I did see an actual difference in execution time. No surprise, but now I know for sure!

So, we have seen that simply reordering the two columns that use an OVER clause reduces the query cost by about 30%. How is it possible that such a simple, basic reordering strategy is not considered by the optimizer? Surely, this can only be a bug?

That’s what Fabiano Neves Amorim thought when he filed this bug on Connect. But, as you can see, the bug has been closed as “By design”. That probably doesn’t mean that someone wrote a design document telling the optimizer team to make sure that OVER clauses must always be evaluated in the order in which they appear in the query, even if a different order would be cheaper. I rather think of it as “missing an optimization opportunity is not a bug; the results are still correct, just a bit slower – so we’re going to close this “bug” report”. In this case, maybe the optimization opportunity was not identified during the design phase, or it was just too hard to implement. The latter statement may sound ridiculous at first (how can such a basic rewrite be too hard?), but you have to be aware that the optimizer does not operate on the original query text, but on an internal representation that is based on mathematics and set theory. Rewrites that may be complex in the query text may be obvious in this representation, but the reverse can also be true – so I’m prepared to accept the comment that Andrew Richardson made on behalf of Microsoft to the above Connect item: that it would be fairly complicated for the Query Optimizer.

That does not mean I agree with the rest of Andrew’s comment. He suggests that this is a case where we should not rely on the optimizer, but rewrite our queries ourselves, especially since it’s such an easy rewrite in this case. Well, I would agree with that, except that: (a) this missed optimization opportunity is not documented, so how are developers supposed to know that they may need to reorder columns in a SELECT clause for optimal performance? (that is one of the reasons for this blog post); and (b) the behavior of the optimizer in this situation is not documented, so it can change at any time; I’d hate to rewrite all my queries and then find that the sysadmin just installed a patch and now the optimizer always starts with the last instead of the first OVER clause (or, worse, I don’t find it and just get all the bad performance right back).

However, Andrew is right in so far that, at this time, rewriting queries does consistently improve performance in all my tests. So at this time, rewriting does seem to be the right thing to do. Just keep in mind that you have to test all your queries, not only on your test server but also on your production hardware, and that you’ll have to repeat these tests on a regular basis (at least after each patch, CU, service pack, or other change).

The basic rewrite pattern is simple – for each query that uses OVER clauses with different ORDER BY subclauses as well as an ORDER BY clause on the query that matches one of the ORDER BY subclauses, make sure that the OVER clause that uses the matching ORDER BY comes last in the SELECT list. If you have a client that expects the columns in a particular order, the rewrite becomes a bit more complex – in that case, you have to use a CTE that includes the OVER clauses in the optimized order, and then you can reorder the columns in the query that references the CTE – as shown in this example:

WITH MyCTE
AS (SELECT   TerritoryID,
Name,
SalesLastYear,
SalesYTD,
RANK() OVER (ORDER BY SalesYTD) AS Rank2,
RANK() OVER (ORDER BY SalesLastYear) AS Rank1
FROM     Sales.SalesTerritory)
SELECT   TerritoryID,
Name,
SalesLastYear,
SalesYTD,
Rank1,
Rank2
FROM     MyCTE
ORDER BY SalesLastYear;

These rewrites are indeed the best option for the time being – but I still think that the optimizer should be improved to do these rewrites internally. So I decided to file a new item on Connect, this time labeling it as a suggestion instead of a bug. If you agree with me that this would be a great investment of Microsoft’s engineering time, then please add your vote to this item. (Or vote it down if you think I’m just being ridiculous). But don’t stop there! Microsoft knows me; they know I’m a geek who plays around with options like this and then runs into this issue. No real production databases were hurt during the production of this blog. And if I am the only one, then, frankly, I myself will say that they have better things to do with their engineering time. However, if I know that this affects real people, I can make a much stronger case to Microsoft for getting this fixed.

So – go out to your production servers and find if you use queries with this pattern (two OVER clauses with different ORDER BY and an ORDER BY on the final query), then check to see if you should rewrite them. And then report back – add a comment here or on the Connect item; share if this affected you, and how much performance you were able to gain as a result of the rewrite.

If Microsoft knows that their customers would actually benefit, they’ll be much more inclined to add this improvement to the optimizer then if it’s just about me, a geek moaning about an edge case that no one in the real world would ever run into.

Slides and demo code for Columnstore Index session
Principles of Modeling: Avoid Redundancy

Related Posts

No results found.

7 Comments. Leave new

  • Paul White
    May 4, 2012 02:18

    Hi Hugo,

    The same considerations apply to the extensions in 2012 (e.g. SUM OVER ORDER BY) that use a Window Spool operator.

    Almost all the optimizer’s current exploration rules are based in relational theory and the algebraic equivalences derived from that theory (extended a bit to work with SQL’s multi-sets, rather than strict sets), as you mention.  These rules don’t work directly with sequences, which were a new concept for the engine added in SQL Server 2005 (hence the ‘Sequence Project’ operator).  Sequences have a order to them that sets (and multi-sets) do not have.

    The optimizer reasons about sort orders for operations like Merge Join and Stream Aggregate, but this reasoning is based on multi-sets, and does not apply to sequences.  Nevertheless, I had hoped for optimizer support for sequences to deepen more than it has since SQL Server 2005.

    For example, the optimizer still cannot push a predicate past a sequence operation unless the sequence has the predicated column in its PARTITION BY clause, and the predicate evaluates against a runtime constant value.  See the unpushed Filter in this query plan:

    WITH MyCTE AS

    (

       SELECT

           TerritoryID,

           SalesLastYear,

           Rank1 = RANK() OVER (ORDER BY SalesLastYear),

           Rank2 = RANK() OVER (ORDER BY SalesYTD)

       FROM Sales.SalesTerritory

    )

    SELECT

       TerritoryID,

       Rank1,

       Rank2

    FROM MyCTE

    WHERE

       MyCTE.TerritoryID < 5

    ORDER BY

       MyCTE.SalesLastYear;

    You have my vote.

    Paul

    Reply
  • SomewhereSomehow
    May 4, 2012 08:30

    Hugo Kornelis,

    Very interesting nuance, I’ll add it to my KB.

    Paul White,

    How could we use predicate pushdown, to early filtering before ranking, in your example? If we do so, we may expect different logical sense, and different ranking numbers…

    Reply
  • Paul White
    May 4, 2012 09:27

    @SomewhereSomehow TerritoryID would need to be part of the RANK’s PARTITION BY clause.  Point is, it only works with constants.

    Paul

    Reply
  • SomewhereSomehow
    May 4, 2012 10:47

    I talked about your example. You said still can not push if there is no partition by, and I thought how could it be ever possible to push without partition by in such queries.

    Interesting note about a run-time constant, seems to be so indeed.

    Reply
  • Paul White
    May 4, 2012 11:13

    That’s right, the PARTITION BY requirement is logical.  In 2005, the optimizer couldn’t do the push even with a constant.  2008 on, it can, but not, in general, with a variable reference (without OPTION RECOMPILE or something else that causes a statement-level recompilation.)

    Reply
  • SomewhereSomehow
    May 4, 2012 12:35

    Maybe it is worth saying, I did some experiments and couldn’t find any other ways (for now) except option(recomple) to force predicate push down with variable after recompilation.

    Altering schema, using temp tables, changing set options, auto update stats – all these stuff produce StmtRecompile event, but we see no pushdown. Even creating proc with recompile keyword isn’t helpful. It seems to act like "is null or value" problem for some reasons.

    Reply
  • Paul White
    May 4, 2012 13:32

    Of course – RECOMPILE is required for the parameter embedding optimization.  I must have been thinking of table variable cardinality estimation, which is affected by a statement-level recompile.  Thanks.

    Reply

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

By continuing to use the site, you agree to the use of cookies. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close