THE SQL Server Blog Spot on the Web

Welcome to SQLblog.com - The SQL Server blog spot on the web Sign in | |
in Search

Paul White: Page Free Space

A technical SQL Server blog from New Zealand. See also my articles on SQLperformance.com

The “Segment Top” Query Optimisation

A question that often comes up on the forums is how to get the first or last row from each group of records in a table.  This post describes a clever query plan optimisation that SQL Server can use for these types of query.

As a simple example, based on the AdventureWorks sample database, say we need to find the minimum product quantity stored in each bin in the warehouse. Using the Production.ProductInventory table, we can write a simple aggregate query:

SELECT  
    INV.Shelf,
    INV.Bin,
    min_qty = MIN(INV.Quantity)
FROM
    Production.ProductInventory AS INV
GROUP BY
    INV.Shelf, 
    INV.Bin
ORDER BY
    INV.Shelf, INV.Bin;

Let’s create a covering index too:

CREATE NONCLUSTERED INDEX nc1
ON Production.ProductInventory (Shelf, Bin, Quantity);

As you might expect, that produces a nice simple query plan:

Original Query

It also produces the results we were after (just a small sample is shown):

Sample Data

Great - but what if we would like some additional information in the output?  You might reasonably want to see some details about the product which has the minimum quantity found - maybe the ProductID and LocationID. We can't just add the extra columns into the query; if we did, SQL Server would complain with an error like:

Column 'Production.ProductInventory.ProductID' is invalid in the select list because it is not contained in either an aggregate function or the GROUP BY clause.

If we try to work around that by adding the extra columns to the GROUP BY clause, the query runs, but produces the wrong results.

Perhaps we can take the query results and JOIN them back to the source table? We do not need to use a temporary table here, we can use a Common Table Expression (CTE):

WITH OriginalQuery AS
(
SELECT  
    INV.Shelf,
    INV.Bin,
    min_qty = MIN(INV.Quantity)
FROM
    Production.ProductInventory AS INV
GROUP BY
    INV.Shelf, 
    INV.Bin
)
SELECT
    INV.ProductID,
    INV.LocationID,
    INV.Shelf,
    INV.Bin,
    INV.Quantity
FROM OriginalQuery AS OQ
INNER JOIN Production.ProductInventory AS INV ON
    INV.Shelf = OQ.Shelf
    AND INV.Bin = OQ.Bin
    AND INV.Quantity = OQ.min_qty
ORDER BY
    INV.Shelf,
    INV.Bin;

That's quite a lot more T-SQL code, so we might be expecting a complex query plan, and probably not a very efficient one either. After all, we introduced a JOIN to a subquery containing an aggregate. This is the entire query plan:

Segment Top Query Plan

Somehow, the Query Optimiser converted all that code to just three query plan iterators: an Index Scan, Segment, and a Top. How does that work?

T-SQL is, for the most part, a declarative language. It provides a way for the query writer to logically describe the results required; it is up to the optimiser to produce an efficient physical plan that the Query Processor can execute. The optimiser is smart enough, on this occasion, to work out what we are logically trying to achieve with all that code: We want to split the table into groups, and return some information from the first row in every group.

The Index Scan produces rows in sorted order (by shelf and then by bin). The Segment iterator (covered in depth in my next post) detects when the beginning of a new group arrives from the index scan, and passes that information on to the Top iterator. The Top iterator then just returns the required columns from the first row in each group - easy!

I refer to this optimiser simplification as “Segment Top”, because of the way those two iterators co-operate to get the work done. The proper name for the transformation is “Generate Group By Apply – Simple”, but I know which one I prefer.

Impressively, the estimated execution cost for the original query was about 0.007; for the “Segment Top” plan, the estimated cost is about 0.006 - slightly less! We added a heap of T-SQL, and ended up with a ‘better’ plan.  I’m comparing estimated costs here because those are calculated based on the information available to the optimiser. All things being equal, a plan with a lower estimated cost will be preferred.

There is more than one way to write this query to produce the exact same “Segment Top” plan. This may not surprise you, since it is frequently possible to express the same logical requirement with quite different T-SQL syntax. The following code illustrates this point:

SELECT
    INV1.ProductID,
    INV1.LocationID,
    INV1.Shelf,
    INV1.Bin,
    INV1.Quantity
FROM Production.ProductInventory AS INV1
WHERE
    INV1.Quantity = 
    (
        -- Correlated to the outer
        -- query on Shelf and Bin
        SELECT
            min_qty = MIN(INV2.Quantity)
        FROM Production.ProductInventory AS INV2
        WHERE
            INV2.Shelf = INV1.Shelf
            AND INV2.Bin = INV1.Bin
    )
ORDER BY
    INV1.Shelf,
    INV1.Bin,
    INV1.Quantity;

Astute readers might have noticed a potential problem: what if there is more than one product in a particular bin which has the minimum quantity? Say if a particular bin contains two spanners, two screwdrivers, and four hammers. Surely the Top iterator in the Segment Top plan will only produce one row per bin, where it should return both spanners and screwdrivers?

The answer is that the Top iterator runs in WITH TIES mode. If you hover the mouse over the Top iterator in the graphical query plan, you will see that it has a 'Tie Columns' argument, over the Shelf and Bin columns. In this mode, if the Segment iterator indicates that more than one row ties for first place, the Top will return all of them - so both spanners and screwdrivers would be returned.

Some query designers might prefer to write a query using a ranking function like ROW_NUMBER; however, because we should return all rows that tie for first place, we have to be careful to use DENSE_RANK instead:

WITH Ranked AS
(
    -- Add the ranking column
    SELECT
        *,
        rn = DENSE_RANK() OVER (
            PARTITION BY Shelf, Bin 
            ORDER BY Quantity)
    FROM Production.ProductInventory AS INV
)
SELECT
    RK.ProductID,
    RK.LocationID,
    RK.Shelf,
    RK.Bin,
    RK.Quantity
FROM Ranked AS RK
--      We want the first row(s)
--      in every group
WHERE
    RK.rn = 1
ORDER BY
    RK.Shelf,
    RK.Bin,
    RK.Quantity;
 

That produces the following query plan, with an estimated cost of 0.0065 - slightly more than the “Segment Top”, but still less than the original query that did not produce the extra columns we need.

DENSE_RANK Query Plan

There are two Segment iterators in that plan, and I will explain why in my next post.

One final alternative solution uses the APPLY operator (see my article on SQL Server Central). The idea here is to explicitly find the first row(s) for each unique combination of Shelf and Bin:

WITH Groups AS
(
-- Find the distinct combinations of
-- Shelf and Bin in the table
SELECT DISTINCT
    INV1.Shelf,
    INV1.Bin
FROM Production.ProductInventory AS INV1
)
SELECT
    iTVF.ProductID,
    iTVF.LocationID,
    iTVF.Shelf,
    iTVF.Bin,
    iTVF.Quantity
FROM Groups
CROSS APPLY
(
    -- Find the first row(s)
    -- for each group
    SELECT TOP (1) WITH TIES
        *
    FROM Production.ProductInventory AS INV2
    WHERE
        INV2.Shelf = Groups.Shelf
        AND INV2.Bin = Groups.Bin
    ORDER BY
        INV2.Quantity ASC
) AS iTVF
ORDER BY
    iTVF.Shelf,
    iTVF.Bin,
    iTVF.Quantity;

This is the query plan:

Apply Query Plan

The estimated cost for this plan is 0.084 - much worse than the other methods, primarily because the JOIN cannot be eliminated in this case.  Nevertheless, the APPLY plan might be the optimal choice if a list of distinct bins and shelves is available from another table (eliminating the DISTINCT) and if there are relatively few shelf and bin combinations (so limiting the number of index seeks).

The transformation to “Segment Top” is not always the optimal strategy, and there’s currently no way to directly request it in a T-SQL query. Nevertheless, it is a useful, interesting, and efficient optimiser simplification.

© Paul White
email: SQLkiwi@gmail.com
twitter: @SQL_Kiwi

Published Wednesday, July 28, 2010 12:57 AM by Paul White

Comment Notification

If you would like to receive an email when updates are made to this post, please register here

Subscribe to this post's comments using RSS

Comments

 

Page Free Space - Paul White said:

In my last post I promised to cover the Segment iterator in more detail, so here we go. Segment The Segment

July 27, 2010 7:51 AM
 

Uri Dimant said:

Hi Paul

Well as you said every approach should be tested. Cross apply operastor resturns  (SQL Server 2005 sp3)

Table 'Worktable'. Scan count 441, logical reads 3055, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table 'ProductInventory'. Scan count 2, logical reads 18, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

But using ROW_NUMBER() function

WITH cte

AS

(

SELECT  ProductID,INV.Shelf,

        INV.Bin,

        Quantity,

  min_qty= ROW_NUMBER() OVER (PARTITION

BY INV.Shelf,INV.Bin ORDER BY  INV.Quantity )  

FROM    Production.ProductInventory INV  

) SELECT * FROM cte WHERE min_qty=1

ORDER   By       Shelf,Bin

Table 'ProductInventory'. Scan

count 1, logical reads 9, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

I agree with you that the both query produced different results.but testing is always goos way to choose right query.

Thanks.

I agree with

July 27, 2010 7:59 AM
 

mjswart said:

Awesome Post. Looking forward to the next one about the segment operator.

July 27, 2010 8:19 AM
 

Paul White said:

Thanks for the comments Uri and Michael.

July 27, 2010 10:38 AM
 

Page Free Space - Paul White said:

For today’s entry, I thought we might take a look at how the optimiser builds an executable plan using

July 28, 2010 1:17 PM
 

Ian Turner said:

Hi Paul,

It looks like the optimizer will not apply the segment top (Generate Group By Apply) optimization where one of the inputs is itself subject to the optimization. Any idea why? Unfortunately, the unoptimized query plan is much worse than the ROW_NUMBER() alternative.

This query should demonstrate the problem. It takes your query and then finds the lowest-numbered location for the affected products.

WITH InnerQuery1 AS

(

SELECT  

   INV.Shelf,

   min_qty = MIN(INV.Quantity)

FROM

   Production.ProductInventory AS INV

GROUP BY

   INV.Shelf

), OuterQuery1 AS

(

SELECT

   INV2.ProductID,

   INV2.LocationID,

   INV2.Shelf,

   INV2.Bin,

   INV2.Quantity

FROM InnerQuery1 AS IQ

INNER JOIN Production.ProductInventory AS INV1 ON

   INV1.Shelf = IQ.Shelf

   AND INV1.Quantity = IQ.min_qty

INNER JOIN Production.ProductInventory AS INV2 ON

INV1.ProductID = INV2.ProductID

), InnerQuery2 AS

(

SELECT

OQ.ProductID,

min_loc = MIN(LocationId)

FROM

OuterQuery1 AS OQ

GROUP BY

OQ.ProductID

), OuterQuery2 AS

(

SELECT

   INV.ProductID,

   INV.LocationID,

   INV.Shelf,

   INV.Bin,

   INV.Quantity

FROM OuterQuery1 AS INV

INNER JOIN InnerQuery2 AS IQ ON

INV.ProductID = IQ.ProductID

AND INV.LocationID = IQ.min_loc

)

SELECT * FROM OuterQuery2

What I would expect to get would be the query plan for InnerQuery2 with a segment top attached. But instead, OuterQuery1 is optimized as expected but OuterQuery2 is not, resulting in not one but two executions of InnerQuery2.

April 22, 2013 5:23 PM
 

Paul White said:

Hi Ian,

The fundamental issue is not specific to GenGbApplySimple, it is a limitation in the way the optimizer reasons about table expressions.

Where the input table expressions are base tables, there is no issue because GenGbApplySimple is written to work with two references to the same object.

When a CTE (or, equivalently, a view) is used to provide the references, the CTE (or view) is expanded into the query tree before optimization starts and the connection to the original reference is lost.

This general feature of query processing can cause unexpectedly poor performance in a number of scenarios where query writers expect the CTE to be evaluated just once (see http://connect.microsoft.com/SQLServer/feedback/details/218968/ and the linked duplicates of that item for more background).

One workaround is to materialize the CTE manually:

-- Lowest quantity per shelf and bin

SELECT

   inv.ProductID,

   inv.LocationID,

   inv.Shelf,

   inv.Bin,

   inv.Quantity

INTO #temp

FROM Production.ProductInventory AS inv

WHERE

   inv.Quantity =

   (

       SELECT  

           MinQty = MIN(inv2.Quantity)

       FROM

           Production.ProductInventory AS inv2

       WHERE

           inv2.Shelf = inv.Shelf

           AND inv2.Bin = inv.Bin

   );

-- Lowest location ID per product

SELECT

   t.ProductID,

   t.LocationID,

   t.Shelf,

   t.Bin,

   t.Quantity

FROM #temp AS t

WHERE

   t.LocationID = (SELECT MIN(t2.LocationID) FROM #temp AS t2 WHERE t2.ProductID = t.ProductID);

April 22, 2013 9:46 PM
 

Ian Turner said:

Hi Paul,

Thanks for your thoughts and detailed response.

It does appear that GenGbApplySimple can be applied to subqueries more complicated than a table expression. For example, it seems to work with a CTE which is just a join of two tables. Consider the following, which takes your original query from the blog post but adds a join with Production.Product in order to filter products by price. It is optimized with Segment Top:

WITH InnerQuery1 AS

(

SELECT INV.ProductID,

INV.LocationID,

INV.Shelf,

INV.Bin,

INV.Quantity

FROM

   Production.ProductInventory AS INV

INNER JOIN Production.Product AS P ON

INV.ProductID = P.ProductID

WHERE P.ListPrice > 10

), InnerQuery2 AS

(

SELECT  

   IQ.Shelf,

   IQ.Bin,

   min_qty = MIN(IQ.Quantity)

FROM InnerQuery1 IQ

GROUP BY

   IQ.Shelf,

   IQ.Bin

)

SELECT

   IQ1.ProductID,

   IQ1.LocationID,

   IQ1.Shelf,

   IQ1.Bin,

   IQ1.Quantity

FROM InnerQuery2 AS IQ2

INNER JOIN InnerQuery1 AS IQ1 ON

   IQ1.Shelf = IQ2.Shelf

   AND IQ1.Bin = IQ2.Bin

   AND IQ1.Quantity = IQ2.min_qty

ORDER BY

   IQ1.Shelf,

   IQ1.Bin;

However, it also seems that there are certain features in the innermost query which block even one application of GenGbApplySimple, however. For example, adding a windowing function such as COUNT(*) OVER () to InnerQuery1 and the outer query seems to block the use of GenGbApplySimple.

So, is this an issue where the optimizer can detect subexpressions but only below a certain level of complexity? Perhaps it only works where the subexpression can be executed with a trivial plan.

April 23, 2013 12:11 PM
 

Paul White said:

Ian,

Yes GenGbApplySimple can operate on subtrees more complex than a single table expression - my point was that multiple references to a CTE or view will often result in subtrees where the original reference is lost.

GenGbApplySimple looks to transform Join(x, GbAgg(x)) -> GbApply(x) so it is obviously essential that the 'x' in that formulation is the same 'x' everywhere. Simple join trees are modelled as an n-ary join inside the optimizer, which helps preserves the 'x' identity in your example.

Introducing extra query features (like a windowing function) may mean the subtree identity is lost before GenGbApplySimple rewrite gets a look in.As a rule of thumb, anything beyond the complexity of a simple n-ary join is quite likely to prevent the match. Even then, there are additional complexities because not every transform will be explored, and not necessarily in the same order, but you get the general idea I hope.

April 23, 2013 8:08 PM
 

Ian Turner said:

Yup, thanks for your comments. It appears that an additional requirement is that segment top's subtree expression must have a unique key which is covered by the join condition in the outer query.

April 24, 2013 10:30 AM
 

Paul White said:

I'm not sure what you mean by 'a unique key which is covered by the join condition in the outer query'. Certainly, the logic of the thing is that we are looking for rows matching a single value (with ties) from a segment of the same table expression, but that doesn't really mean the same thing.

Perhaps a simpler example will make it clearer:

-- Create a heap copy

SELECT * INTO #p FROM Production.Product AS p

-- Segment Apply

SELECT p.*, x.mlp FROM #p AS p

JOIN (SELECT p.Color, MIN(p.ListPrice) AS mlp FROM #p AS p GROUP BY p.Color) AS x

ON p.Color = x.Color;

-- Same Segment Apply using different syntax

SELECT *, MIN(p.ListPrice) OVER (PARTITION BY p.Color)

FROM #p AS p

WHERE p.Color IS NOT NULL;

-- Top 1 with ties per segment

SELECT p.*, x.mlp FROM #p AS p

JOIN (SELECT p.Color, MIN(p.ListPrice) AS mlp FROM #p AS p GROUP BY p.Color) AS x

ON p.Color = x.Color AND p.ListPrice = x.mlp;

April 25, 2013 9:38 PM
 

Ian Turner said:

Hi Paul, what I meant by this is that it seems like the optimizer cannot use GenGbApplySimple unless it knows that the join condition between the two table expressions is unique. If you drop the unique key on the AdventureWorks tables, you may see that Segment Top no longer applies.

May 8, 2013 1:50 PM

Leave a Comment

(required) 
(required) 
Submit
Powered by Community Server (Commercial Edition), by Telligent Systems
  Privacy Statement