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:
1: SELECT INV.Shelf,
2: INV.Bin,
3: min_qty = MIN(INV.Quantity)
4: FROM Production.ProductInventory INV
5: GROUP BY
6: INV.Shelf, INV.Bin
7: ORDER BY
8: INV.Shelf, INV.Bin;
Let’s create a covering index too:
1: CREATE NONCLUSTERED INDEX nc1
2: ON Production.ProductInventory
3: (Shelf, Bin, Quantity);
As you might expect, that produces a nice simple query plan:
It also produces the results we were after (just a small sample is shown):
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):
1: WITH OriginalQuery
2: AS (
3: SELECT Shelf,
4: Bin,
5: min_qty = MIN(Quantity)
6: FROM Production.ProductInventory
7: GROUP BY
8: Shelf, Bin
9: )
10: SELECT INV.ProductID,
11: INV.LocationID,
12: INV.Shelf,
13: INV.Bin,
14: INV.Quantity
15: FROM OriginalQuery Q
16: JOIN Production.ProductInventory INV
17: ON INV.Shelf = Q.Shelf
18: AND INV.Bin = Q.Bin
19: AND INV.Quantity = Q.min_qty
20: ORDER BY
21: INV.Shelf,
22: 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:
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:
1: SELECT INV1.ProductID,
2: INV1.LocationID,
3: INV1.Shelf,
4: INV1.Bin,
5: INV1.Quantity
6: FROM Production.ProductInventory INV1
7: WHERE INV1.Quantity =
8: (
9: -- Correlated subquery
10: SELECT MIN(INV2.Quantity)
11: FROM Production.ProductInventory INV2
12: -- Correlated to the outer
13: -- query on Shelf and Bin
14: WHERE INV2.Shelf = INV1.Shelf
15: AND INV2.Bin = INV1.Bin
16: )
17: ORDER BY
18: INV1.Shelf,
19: INV1.Bin,
20: 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:
1: WITH Ranked
2: AS (
3: -- Add the ranking column
4: SELECT *,
5: rn = DENSE_RANK() OVER (PARTITION BY Shelf, Bin ORDER BY Quantity)
6: FROM Production.ProductInventory INV
7: )
8: SELECT RK.ProductID,
9: RK.LocationID,
10: RK.Shelf,
11: RK.Bin,
12: RK.Quantity
13: FROM Ranked RK
14: -- We want the first row(s)
15: -- in every group
16: WHERE RK.rn = 1
17: ORDER BY
18: RK.Shelf,
19: RK.Bin,
20: 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.
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:
1: WITH Groups
2: AS (
3: -- Find the distinct combinations of
4: -- Shelf and Bin in the table
5: SELECT DISTINCT
6: INV1.Shelf,
7: INV1.Bin
8: FROM Production.ProductInventory INV1
9: )
10: SELECT iTVF.ProductID,
11: iTVF.LocationID,
12: iTVF.Shelf,
13: iTVF.Bin,
14: iTVF.Quantity
15: FROM Groups
16: CROSS
17: APPLY (
18: -- Find the first row(s)
19: -- for each group
20: SELECT TOP (1)
21: WITH TIES
22: *
23: FROM Production.ProductInventory INV2
24: WHERE INV2.Shelf = Groups.Shelf
25: AND INV2.Bin = Groups.Bin
26: ORDER BY
27: INV2.Quantity ASC
28: ) iTVF
29: ORDER BY
30: iTVF.Shelf,
31: iTVF.Bin,
32: iTVF.Quantity;
This is the 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.