EF Core SQL client timeout with sorting and pagination

Question

Query :

modelBuilder.Entity<Job>()
    .HasNoKey()
    .ToSqlQuery(
        "SELECT " +
        "    B.JobId, " +
        "    SUBSTRING(B.Name, 1, CHARINDEX(',', B.Name) - 1) AS Name, " +
        "    LastState, " +
        "    C.CreatedAt AT TIME ZONE 'UTC' AS LastStateCreatedAt, " +
        "    REPLACE(D.Value, '\"', '') AS RecurringJobName, " + 
        "    B.CreatedAt " +
        "FROM " +
        "( " +
        "    SELECT " +
        "        Id AS JobId, " +
        "        COALESCE( " +
        "            JSON_VALUE(InvocationData, '$.t'), " +
        "            JSON_VALUE(InvocationData, '$.Type') " +
        "        ) AS Name, " +
        "        StateId AS LastStateId, " +
        "        StateName AS LastState, " +
        "        CreatedAt AT TIME ZONE 'UTC' AS CreatedAt " +
        "    FROM " +
        "        Hangfire.Job " +
        "    WITH (NOLOCK) " +
        ") AS B " +
        "LEFT JOIN Hangfire.State AS C WITH (NOLOCK) ON Id = B.LastStateId " +
        "LEFT JOIN Hangfire.JobParameter AS D WITH (NOLOCK) ON (B.JobId = D.JobId AND D.Name = 'RecurringJobId')");

Using it:

_dbContext.Jobs
    .OrderByDescending(x => x.CreatedAt)
    .PaginatedListAsync(request.PageNumber, request.PageSize);

PaginatesListAsync takes the IQueryable and returns a paginated list:

public static async Task<PaginatedList<T>> CreateAsync(IQueryable<T> source, int pageNumber, int pageSize)
{
    var count = await source.CountAsync();
    var items = await source.Skip((pageNumber - 1) * pageSize).Take(pageSize).ToListAsync();

    return new PaginatedList<T>(items, count, pageNumber, pageSize);
}

I have 5000 job records, so 500 pages of 10 records. With each page, the query gets slower until I get a timeout at page 100 or so. When I remove OrderByDescending(x => x.CreatedAt) the pagination performs great again.

Here is the error I am getting:

Microsoft.EntityFrameworkCore.Query: Error: An exception occurred while iterating over the results of a query for context type 'MyDbContext'.

and

Microsoft.Data.SqlClient.SqlException (0x80131904): Execution Timeout Expired. The timeout period elapsed prior to completion of the operation or the server is not responding.

System.ComponentModel.Win32Exception (258): Unknown error 258

at Microsoft.Data.SqlClient.SqlCommand.<>c.b__188_0(Task1 result) at System.Threading.Tasks.ContinuationResultTaskFromResultTask2.InnerInvoke()
at System.Threading.ExecutionContext.RunInternal(ExecutionContext executionContext, ContextCallback callback, Object state)
--- End of stack trace from previous location ---
at System.Threading.Tasks.Task.ExecuteWithThreadLocal(Task& currentTaskSlot, Thread threadPoolThread)
--- End of stack trace from previous location ---
at Microsoft.EntityFrameworkCore.Storage.RelationalCommand.ExecuteReaderAsync(RelationalCommandParameterObject parameterObject, CancellationToken cancellationToken)
at Microsoft.EntityFrameworkCore.Storage.RelationalCommand.ExecuteReaderAsync(RelationalCommandParameterObject parameterObject, CancellationToken cancellationToken)
at Microsoft.EntityFrameworkCore.Query.Internal.SingleQueryingEnumerable1.AsyncEnumerator.InitializeReaderAsync(AsyncEnumerator enumerator, CancellationToken cancellationToken) at Microsoft.EntityFrameworkCore.SqlServer.Storage.Internal.SqlServerExecutionStrategy.ExecuteAsync[TState,TResult](TState state, Func4 operation, Func4 verifySucceeded, CancellationToken cancellationToken) at Microsoft.EntityFrameworkCore.Query.Internal.SingleQueryingEnumerable1.AsyncEnumerator.MoveNextAsync()

ClientConnectionId:133f133e-d96f-4409-a3b5-5825023ef092
Error Number:-2,State:0,Class:11

Exact query

SELECT [e].[CreatedAt], [e].[JobId], [e].[LastState], [e].[LastStateCreatedAt], [e].[Name], [e].[RecurringJobName]
FROM (
    SELECT  B.JobId, SUBSTRING(B.Name, 1, CHARINDEX(',', B.Name) - 1) AS Name, LastState, C.CreatedAt AT TIME ZONE 'UTC' AS LastStateCreatedAt, REPLACE(D.Value, '"', '') AS RecurringJobName, B.CreatedAt FROM (SELECT Id AS JobId, COALESCE(JSON_VALUE(InvocationData, '$.t'), JSON_VALUE(InvocationData, '$.Type')) AS Name, StateId AS LastStateId, StateName AS LastState, CreatedAt AT TIME ZONE 'UTC' AS CreatedAt FROM Hangfire.Job WITH (NOLOCK) ) AS B LEFT JOIN Hangfire.State AS C WITH (NOLOCK) ON Id = B.LastStateId LEFT JOIN Hangfire.JobParameter AS D WITH (NOLOCK) ON (B.JobId = D.JobId AND D.Name = 'RecurringJobId')
) AS [e]
ORDER BY [e].[CreatedAt] DESC
OFFSET 100 ROWS FETCH NEXT 10 ROWS ONLY

Execution plan https://www.brentozar.com/pastetheplan/?id=SJ3HEt-CF:

Execution plan without orderby https://www.brentozar.com/pastetheplan/?id=B1BnVt-0F:

When removing linq's orderby, the query no has ORDER BY (SELECT 1) instead of ORDER BY [e].[CreatedAt] DESC.

Tables:

-- Create job tables
CREATE TABLE [$(HangFireSchema)].[Job] (
    [Id] [int] IDENTITY(1,1) NOT NULL,
    [StateId] [int] NULL,
    [StateName] [nvarchar](20) NULL, -- To speed-up queries.
    [InvocationData] [nvarchar](max) NOT NULL,
    [Arguments] [nvarchar](max) NOT NULL,
    [CreatedAt] [datetime] NOT NULL,
    [ExpireAt] [datetime] NULL,

    CONSTRAINT [PK_HangFire_Job] PRIMARY KEY CLUSTERED ([Id] ASC)
);
PRINT 'Created table [$(HangFireSchema)].[Job]';

CREATE NONCLUSTERED INDEX [IX_HangFire_Job_StateName] ON [$(HangFireSchema)].[Job] ([StateName] ASC);
PRINT 'Created index [IX_HangFire_Job_StateName]';
    
-- Job history table
    
CREATE TABLE [$(HangFireSchema)].[State] (
    [Id] [int] IDENTITY(1,1) NOT NULL,
    [JobId] [int] NOT NULL,
    [Name] [nvarchar](20) NOT NULL,
    [Reason] [nvarchar](100) NULL,
    [CreatedAt] [datetime] NOT NULL,
    [Data] [nvarchar](max) NULL,
        
    CONSTRAINT [PK_HangFire_State] PRIMARY KEY CLUSTERED ([Id] ASC)
);
PRINT 'Created table [$(HangFireSchema)].[State]';

ALTER TABLE [$(HangFireSchema)].[State] ADD CONSTRAINT [FK_HangFire_State_Job] FOREIGN KEY([JobId])
    REFERENCES [$(HangFireSchema)].[Job] ([Id])
    ON UPDATE CASCADE
    ON DELETE CASCADE;
PRINT 'Created constraint [FK_HangFire_State_Job]';
    
CREATE NONCLUSTERED INDEX [IX_HangFire_State_JobId] ON [$(HangFireSchema)].[State] ([JobId] ASC);
PRINT 'Created index [IX_HangFire_State_JobId]';
    
-- Job parameters table
    
CREATE TABLE [$(HangFireSchema)].[JobParameter](
    [Id] [int] IDENTITY(1,1) NOT NULL,
    [JobId] [int] NOT NULL,
    [Name] [nvarchar](40) NOT NULL,
    [Value] [nvarchar](max) NULL,
        
    CONSTRAINT [PK_HangFire_JobParameter] PRIMARY KEY CLUSTERED ([Id] ASC)
);
PRINT 'Created table [$(HangFireSchema)].[JobParameter]';

ALTER TABLE [$(HangFireSchema)].[JobParameter] ADD CONSTRAINT [FK_HangFire_JobParameter_Job] FOREIGN KEY([JobId])
    REFERENCES [$(HangFireSchema)].[Job] ([Id])
    ON UPDATE CASCADE
    ON DELETE CASCADE;
PRINT 'Created constraint [FK_HangFire_JobParameter_Job]';
    
CREATE NONCLUSTERED INDEX [IX_HangFire_JobParameter_JobIdAndName] ON [$(HangFireSchema)].[JobParameter] (
    [JobId] ASC,
    [Name] ASC
);
PRINT 'Created index [IX_HangFire_JobParameter_JobIdAndName]';

From: https://github.com/HangfireIO/Hangfire/blob/c23b01061860b4f5b5692e23e8f8cbdbe4681a8b/src/Hangfire.SqlServer/Install.sql

Any ideas what's wrong? Not all fields I perform sorting on are indexed. Might that be the issue?