OFFSET ... FETCH is slow on high paging value

Question

This is my scenario:

CREATE TABLE [dbo].[tblSMSSendQueueMain](
    [ID] [int] IDENTITY(1,1) NOT NULL,
    [SendMethod] [int] NOT NULL
 CONSTRAINT [PK_tblSMSSendQueueLog] PRIMARY KEY CLUSTERED 
(
    [ID] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY] TEXTIMAGE_ON [PRIMARY]
GO

CREATE TABLE [dbo].[tblSMSSendQueueMainSendStatus](
    [ID] [bigint] IDENTITY(1,1) NOT NULL,
    [QueueID] [int] NULL,
    [SendStatus] [int] NULL,
    [StatusDate] [datetime] NULL,
    [UserID] [int] NULL,
 CONSTRAINT [PK_tblSMSSendQueueMainSendStatus] PRIMARY KEY CLUSTERED 
(
    [ID] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]
GO

and some indexes:

CREATE NONCLUSTERED INDEX [IX_tblSMSSendQueueMainSendStatus_SendStatus_Single] ON [dbo].[tblSMSSendQueueMainSendStatus]
(
    [SendStatus] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
GO

CREATE NONCLUSTERED INDEX [IX_tblSMSSendQueueMain_SendMethod] ON [dbo].[tblSMSSendQueueMain]
(
    [SendMethod] ASC,
    [ID] DESC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
GO

each table have about 13m rows QueueID column of tblSMSSendQueueMainSendStatus is foreign key of ID column in tblSMSSendQueueMain.

The server has an 8 cores Xeon CPU and 8GB RAM.

I use offset and fetch for my paging plan, its perfect and OK for offset under 100k but when the offset going up (more than 100k), the query response is slow, and takes about 5 or 6 seconds to run.

This is my query:

SELECT q.ID  
FROM tblSMSSendQueueMain q  
INNER JOIN tblSMSSendQueueMainSendStatus qs  
ON q.ID = qs.QueueID  
WHERE 1 = 1  
AND qs.SendStatus = 5  
AND [SendMethod] = 19  
ORDER BY q.ID desc OFFSET 10 * (1000000 - 1) ROWS  
FETCH NEXT 10 ROWS ONLY 

Does anyone have any idea where I am going wrong?

Answer 1

The reason this is so slow is that the only way for the server to get the correct starting row is by reading every single row before it.

You are much better off using Keyset Pagination. Instead of paging by starting row-number, pass in a parameter of the starting key.

For this to work, you must return a unique column or columns, and for this to be performant they should be indexed well.

Pass in @startingRow as the previous batch's highest ID, you can get this any way you like. E.g. I have used an ORDER BY so it will be the last row, or your client app will be able to retrieve it from a variable.

SELECT TOP (10)
    q.ID  
FROM tblSMSSendQueueMain q  
INNER JOIN tblSMSSendQueueMainSendStatus qs  
ON q.ID = qs.QueueID  
WHERE 1 = 1  
   AND qs.SendStatus = 5  
   AND q.[SendMethod] = 19
   AND qs.ID > @startingRow    -- drop this line for the first query
ORDER BY qs.ID;

---

I must say, your query is somewhat strange. If the foreign key is q.ID = qs.QueueID, then you will get multiple identical results if you are just querying q.ID. I suspect you actually only want q.ID, in which case that is your unique key:

SELECT TOP (10) DISTINCT
    q.ID  
FROM tblSMSSendQueueMain q  
INNER JOIN tblSMSSendQueueMainSendStatus qs  
ON q.ID = qs.QueueID  
WHERE 1 = 1  
   AND qs.SendStatus = 5  
   AND q.[SendMethod] = 19
   AND q.ID > @startingRow    -- drop this line for the first query
ORDER BY q.ID;

Alternatively, I would prefer an EXISTS/IN as it more clearly states the requirement:

SELECT TOP (10)
    q.ID  
FROM tblSMSSendQueueMain q  
WHERE 1 = 1  
   AND q.[SendMethod] = 19
   AND q.ID IN (
      SELECT qs.QueueID
      FROM tblSMSSendQueueMainSendStatus qs
      WHERE qs.SendStatus = 5
   )
   AND q.ID > @startingRow    -- drop this line for the first query
ORDER BY q.ID;