Pagination performance, with subquery, inner join and where

I am trying to optimize following query (this is most simplified version I could came up with):

SELECT tr.Id, StatusDate
FROM (
    SELECT tr.Id, tr.StatusDate
    FROM mon.ArchivedTaskResults_201504 as tr WITH (NOLOCK)
    INNER JOIN mon.ViewDevicesWithGroups dev WITH (NOLOCK) ON tr.DeviceId = dev.Id
    WHERE tr.ClientId = 4 AND dev.Deleted = 0
) AS tr        
ORDER BY StatusDate DESC
OFFSET 1000000 rows
FETCH NEXT 25 ROWS ONLY

The problem is, query performance is directly proportional to OFFSET - for offset=0 query executes in 0.0s, but for offset=1000000 execution time is about 23s (and with even greater offset, it can take up to few minutes).

I'm almost sure that my problem could be solved with appropriate clustered index on ArchivedTaskResults table, but after trying for few hours I still haven't found good index yet.

ArchivedTaskResults tables are really big, having about 50000000 rows (50 M)

Additional information:

I would be extremally happy if someone could solve problem I described above, but to be honest, my REAL query is even more bizarre (disclaimer: I am not the one that designed this database):

```
SELECT tr.Id, StatusDate
FROM (
(
SELECT tr.Id, StatusDate
FROM mon.TaskResults as tr WITH (NOLOCK)
INNER JOIN mon.ViewDevicesWithGroups dev WITH (NOLOCK) ON tr.DeviceId = dev.Id
WHERE tr.ClientId = 4 AND dev.Deleted = 0
) UNION ALL (
SELECT tr.Id, tr.StatusDate
FROM mon.ArchivedTaskResults_201504 as tr WITH (NOLOCK)
INNER JOIN mon.ViewDevicesWithGroups dev WITH (NOLOCK) ON tr.DeviceId = dev.Id
WHERE tr.ClientId = 4 AND dev.Deleted = 0
) UNION ALL (
SELECT tr.Id, tr.StatusDate
FROM mon.ArchivedTaskResults_201505 as tr WITH (NOLOCK)
INNER JOIN mon.ViewDevicesWithGroups dev WITH (NOLOCK) ON tr.DeviceId = dev.Id
WHERE tr.ClientId = 4 AND dev.Deleted = 0
)
) AS tr
ORDER BY StatusDate DESC
OFFSET 1000000 ROWS
FETCH NEXT 25 ROWS

I don't think you'll be able to get good performance while using OFFSET. The database must search through 1,000,025 rows of output from the inner query; even if you have a good clustered index on TaskResults the system doesn't know for certain that it can skip ahead to date X.

But you do! Assuming this is for some kind of GUI, make a note of the earliest StatusDate from the previous query, then use it to fitler next page:

SELECT
    tr.Id, StatusDate
FROM
    (
    SELECT tr.Id, tr.StatusDate
    FROM mon.ArchivedTaskResults_201504 as tr WITH (NOLOCK)
        INNER JOIN mon.ViewDevicesWithGroups dev WITH (NOLOCK) ON tr.DeviceId = dev.Id
    WHERE tr.ClientId = 4 AND dev.Deleted = 0
        AND
            (
            -- Retrieve only records from before the previous page
            tr.StatusDate < @PrevStatusDate
            OR (tr.StatusDate = @PrevStatusDate AND tr.Id < @PrevID) 
            )
    ) AS tr        
ORDER BY StatusDate, Id DESC
FETCH NEXT 25 ROWS ONLY

So if page #123 ends with 2015/05/01, record #234, you want to consider all records that are from 2015/04/30 or earlier, or which are also from 2015/05/01 but are for records #1 .. #233.

This should work well with your more complex UNION query, but "real" partitioning would probably be easier than this roll-yer-own partitioning..

If StatusDate is unique, or it's acceptable to occasionally show the same record on two adjacent pages, you can drop the @PrevID and ORDER BY Id bits. If Id is always-increasing, you can filter off of it and skip StatusDate.

Keep in mind that retrieving pages like this can easily skip a record or include the same record twice if records are being adding, removed, or reordered in the underlying data. But that's another topic.

StackExchange Database Administrators Q#101183, answer score: 4