Why does my WHERE clause benefit from an "included" column?

Question

According to this answer, unless an index is built over the columns which are used to restrict, the query will not benefit from an index.

I have this definition:

CREATE TABLE [dbo].[JobItems] (
    [ItemId]             UNIQUEIDENTIFIER NOT NULL,
    [ItemState]          INT              NOT NULL,
    [ItemPriority]       INT NOT NULL,
    [CreationTime]       DATETIME         NULL DEFAULT GETUTCDATE(),
    [LastAccessTime]     DATETIME         NULL DEFAULT GETUTCDATE(),
     -- other columns
 );

 CREATE UNIQUE CLUSTERED INDEX [JobItemsIndex]
    ON [dbo].[JobItems]([ItemId] ASC);
 GO

CREATE INDEX [GetItemToProcessIndex]
    ON [dbo].[JobItems]([ItemState], [ItemPriority], [CreationTime])
    INCLUDE (LastAccessTime);
GO

and this query:

UPDATE TOP (150) JobItems 
SET ItemState = 17 
WHERE 
    ItemState IN (3, 9, 10)
    AND LastAccessTime < DATEADD (day, -2, GETUTCDATE()) 
    AND CreationTime < DATEADD (day, -2, GETUTCDATE());

I reviewed the actual plan, and there's just one index seek with the predicate exactly as in the WHERE - no additional "bookmark lookups" to retrieve LastAccessTime even though the latter is only "included" into the index, not part of the index.

It looks to me like this behavior contradicts the rule that the column must be part of the index, and not just "included".

Is the behavior I observe the right one? How can I know in advance if my WHERE benefits from an included column or needs the column to be part of the index?

Answer 1

Your Predicate is different to your Seek Predicate.

A Seek Predicate is used to search the ordered data in the index. In this case, it'll be doing three seeks, one for each ItemState that you're interested in. Beyond that, the data is in ItemPriority order, so no further "Seek" operation can be done.

But before the data is returned, it checks every row using the Predicate, which I refer to as the Residual Predicate. It's done on the results of the Seek Predicate.

Any included column is not part of the ordered data, but can be used to satisfy the Residual Predicate, without having to do the extra Lookup.

You can see material I've written on this around Sargability. Check for a session at SQLBits in particular, at http://bit.ly/Sargability

Edit: To show the impact of Residuals better, run the query using the undocumented OPTION (QUERYTRACEON 9130), which will separate out the Residual into a separate Filter operator (which is actually an earlier version of the plan before the residual gets moved into the Seek operator). It clearly shows the impact of an ineffective Seek, by the number of rows being passed left to the Filter.

It's also worth noting that because of the IN clause on ItemState, the data being passed left is actually in ItemState order, not in ItemPriority order. A composite index on ItemState followed by one of the dates (eg (ItemState, LastAccessTime)) could be used to have three Seeks (notice the Seek Predicate shows three seeks within the one Seek operator), each against two levels, producing data that is still in ItemState order (eg, ItemState=3 and LastAccessTime less than something, then ItemState=9 and LastAccessTime less than something, and then ItemState=10 and LastAccessTime less than something).

An index on (ItemState, LastAccesTime, CreationTime) would be no more useful than one on (ItemState, LastAccessTime) because the CreationTime level is only useful if your Seek is for a particular ItemState and LastAccessTime combination, not a range. Like how the phone book isn't in FirstName order if you are interested in Surnames beginning in F.

If you want a composite index but you are never going to be able to use the later columns in Seek Predicates because of the way you use the earlier columns, then you may as well have them as included columns, where they take less space in the index (because they're only stored at the leaf level of the index, not the higher levels) but can still avoid lookups and get used in Residual predicates.

As per the term Residual Predicate - that's my own term for this property of a Seek. A Merge Join explicitly calls it its equivalent a Residual Predicate, and the Hash Match calls its one a Probe Residual (which you might get from TSA if you match for hash). But in a Seek they just call it Predicate which makes it seem less bad than it is.

Answer 2

GetItemToProcessIndex is not fully seekable because your where clause is on ItemState + LastAccessTime + CreationTime. The indexed columns and the where clause are a not perfect match.

If you create a covering index on ItemState + LastAccessTime + CreationTime, for each match you get from GetItemToProcessIndex, you also get the value of your Primary Key (ItemId). It only has to make sure that the 2nd date is a match.

This is all you need to then jump to the location of the row on its page and update it.

With your current index, it may help the server to find rows with the ItemState you want but it then still have to read all of them from the index in order to find correct matches on LastAccessTime + CreationTime. Depending on the date predicates and the size of the matching set and what has to be excluded, it may result in a lot more IO than a perfectly covering index on the 3 columns only which would seek ItemState and the second column (1st indexed date). The second date in the indexed can be included though. Extra columns should not be indexed between these 3 although it could be ok as a 4th column (see rob's answer about extra columns).