Why am I seeing key lookups for all rows read, instead of all rows matching the where clause?

I have a table such as the following:

create table [Thing]
(
    [Id] int constraint [PK_Thing_Id] primary key,
    [Status] nvarchar(20),
    [Timestamp] datetime2,
    [Foo] nvarchar(100)
)

with a non-clustered, non-covering index on the Status and Timestamp fields:

create nonclustered index [IX_Status_Timestamp] on [Thing] ([Status], [Timestamp] desc)

If I query for a 'page' of these rows, using offset/fetch as follows,

select * from [Thing]
where Status = 'Pending'
order by [Timestamp] desc
offset 2000 rows
fetch next 1000 rows only

I understand that the query will need to read a total of 3000 rows to find the 1000 that I'm interested in. I would then expect it to perform key lookups for each of those 1000 rows to fetch the fields not included in the index.

However, the execution plan indicates that it is doing key lookups for all 3000 rows. I don't understand why, when the only criteria (filter by [Status] and order by [Timestamp]) are both in the index.

If I rephrase the query with a cte, as follows, I get more or less what I expected the first query to do:

with ids as
(
    select Id from [Thing]
    where Status = 'Pending'
    order by [Timestamp] desc
    offset 2000 rows
    fetch next 1000 rows only
)

select t.* from [Thing] t
join ids on ids.Id = t.Id
order by [Timestamp] desc

Some statistics from SSMS to compare the 2 queries:

Original
With CTE

Logical reads
12265
4140

Subtree cost
9.79
3.33

Memory grant
0
3584 KB

The CTE version seems 'better' at first glance, although I don't know how much weight to place on the fact that it incurs a memory grant for a worktable. (The messages from set statistics io on indicate that there were zero reads of any kind on the worktable)

Am I wrong in saying that the first query should be able to isolate the relevant 1000 rows first (even though that requires reading past 2000 other rows first), and then only do key lookups on those 1000? It seems a bit odd to ha

Fundamentally, it is a long-standing optimizer limitation.

SQL Server does not consider turning a Key Lookup into a Clustered Index Seek. A Key Lookup has to pretty much immediately follow the nonclustered index access it is associated with (there may be an intervening sort, for I/O reasons).

There are several ways to rewrite the query to operate just on the index keys for as long as possible, without introducing the sort seen in your example:

WITH IDs AS
(
    SELECT T.* 
    FROM dbo.Thing AS T
    WHERE T.[Status] = N'Pending'
    ORDER BY T.[Timestamp] DESC
    OFFSET 2000 ROWS
    FETCH NEXT 1000 ROWS ONLY
)
SELECT 
    T.* 
FROM IDs AS I
JOIN dbo.Thing AS T
    ON T.Id = I.Id
ORDER BY
    I.[Timestamp] DESC;

or

SELECT 
    T2.* 
FROM dbo.Thing AS T
JOIN dbo.Thing AS T2
    ON T2.Id = T.Id
WHERE 
    T.[Status] = N'Pending'
ORDER BY 
    T.[Timestamp] DESC
    OFFSET 2000 ROWS
    FETCH NEXT 1000 ROWS ONLY;

The need to sort is removed by helping the optimizer 'see' the sorted order is preserved.

Further reading:

• Lookups Are Just Joins With No Choices by Erik Darling

• Optimising Server-Side Paging by me

• Pagination with OFFSET / FETCH : A better way by Aaron Bertrand

• Advanced TSQL Tuning: Why Internals Knowledge Matters by me

StackExchange Database Administrators Q#307096, answer score: 16