The “Segment Top” Query Optimisation

The Segment and Sequence Project Iterators

Page Free Space - Paul White — Tue, 27 Jul 2010 11:51:10 GMT

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

re: The “Segment Top” Query Optimisation

Uri Dimant — Tue, 27 Jul 2010 11:59:20 GMT

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

(

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

re: The “Segment Top” Query Optimisation

mjswart — Tue, 27 Jul 2010 12:19:10 GMT

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

re: The “Segment Top” Query Optimisation

Paul White — Tue, 27 Jul 2010 14:38:58 GMT

Thanks for the comments Uri and Michael.

Inside the Optimiser: Constructing a Plan

Page Free Space - Paul White — Wed, 28 Jul 2010 17:17:54 GMT

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

re: The “Segment Top” Query Optimisation

Ian Turner — Mon, 22 Apr 2013 21:23:40 GMT

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.

re: The “Segment Top” Query Optimisation

Paul White — Tue, 23 Apr 2013 01:46:05 GMT

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);

re: The “Segment Top” Query Optimisation

Ian Turner — Tue, 23 Apr 2013 16:11:24 GMT

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.

re: The “Segment Top” Query Optimisation

Paul White — Wed, 24 Apr 2013 00:08:43 GMT

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.

re: The “Segment Top” Query Optimisation

Ian Turner — Wed, 24 Apr 2013 14:30:07 GMT

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.

re: The “Segment Top” Query Optimisation

Paul White — Fri, 26 Apr 2013 01:38:39 GMT

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;

re: The “Segment Top” Query Optimisation

Ian Turner — Wed, 08 May 2013 17:50:44 GMT

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.