Ranking Function Optimizer Transformations

In my last post I showed how SQL Server 2005 and later can use a Segment Spool to efficiently implement aggregate window functions and the NTILE ranking function.

The query optimizer is also smart enough to recognise that some queries are logically equivalent to a window function, even if they are written using different syntax.  As a reminder, here's the sample data defining what the AdventureWorks report output should look like:

Here's a query written to meet the same requirements, but without the SUM...OVER construction used last time:

   1: SELECT  INV.Bin,

   2:         INV.Quantity,

   3:         INV.ProductID,

   4:         INV.Quantity,

   5:         SubAgg.total_in_bin

   6: FROM    Production.ProductInventory INV

   7: JOIN    (

   8:         -- Calculates the total quantity

   9:         -- in each bin

  10:         SELECT  INV2.Shelf,

  11:                 INV2.Bin,

  12:                 total_in_bin = SUM(INV2.Quantity)

  13:         FROM    Production.ProductInventory INV2

  14:         GROUP   BY

  15:                 INV2.Shelf,

  16:                 INV2.Bin

  17:         ) SubAgg

  18:         ON  SubAgg.Shelf = INV.Shelf

  19:         AND SubAgg.Bin = INV.Bin

  20: WHERE   INV.Shelf >= 'A' 

  21: AND     INV.Shelf <= 'C'

  22: ORDER   BY

  23:         INV.Shelf,

  24:         INV.Bin;

This query is simplified as if it had been written:

   1: SELECT  INV.Shelf,

   2:         INV.Bin,

   3:         INV.ProductID,

   4:         INV.Quantity,

   5:         total_in_bin = 

   6:             SUM(INV.Quantity) OVER (

   7:                 PARTITION BY INV.Shelf, INV.Bin)

   8: FROM    Production.ProductInventory INV

   9: WHERE   INV.Shelf BETWEEN 'A' AND 'C'

  10: ORDER   BY

  11:         INV.Shelf,

  12:         INV.Bin;

Both forms produce the same Segment Spool query plan:

There are a great many limitations on the query forms that can be simplified to the logically-equivalent window function representation.  For example, changing the predicates on INV.Shelf to IN (N'A', N'B', N'C') in the first query breaks the transformation, producing a quite different plan where the aggregation is pushed below a merge join:

This is still a good plan, but it has a somewhat higher estimated cost (0.013) compared to the Segment Spool plan (0.0074).  It's not a huge absolute difference of course, but it does show that optimiser support for this transformation is relatively shallow at present.

Another example of this lack of depth is that the transformation is not performed in reverse: a query written to use an aggregate window function (and therefore the Segment Spool) cannot be transformed to a join equivalent (as in the Merge Join plan shown above).  This is not a cost-based decision: there are examples where the Merge Join plan has a lower estimated cost, but the optimiser does not consider it.  In such cases, we would need to rewrite the original query to help the optimiser out.

In fact, if we disable the optimiser rule that transforms a partitioned windowed aggregate into a Segment Spool, the SUM…OVER form of the query shown above fails to compile at all:

Internal Query Processor Error: The query processor could not produce a query plan.
For more information, contact Customer Support Services.

More details on that sort of dangerous mucking about with optimiser internals in future posts.