Оптимизация SQL-запросов с миллионом записей

В настоящее время я использую запрос ниже, чтобы получить запись на основе senderid. У меня есть 2 миллиона записей в таблице сообщений, а также записи параллельны в этой таблице. Но для возврата результата требуется более 5 секунд. Эта таблица имеет только один некластеризованный индекс, созданный на Providerid (включая приоритет столбца, senderid, maskid) Может ли кто-нибудь из экспертов по sql помочь мне в этом.

ALTER PROCEDURE [dbo].[GetNextSmsQueue] @NoOfRow int,
                                        @GatewayId int
AS
    BEGIN TRY
        BEGIN TRAN;
        CREATE TABLE #SmsIn ([Id] [bigint] NOT NULL,
                             [UserId] [bigint] NOT NULL,
                             [MaskId] [varchar](50) NOT NULL,
                             [Number] [varchar](20) NOT NULL,
                             [Message] [nvarchar](1300) NOT NULL,
                             [SenderId] [varchar](20) NOT NULL,
                             [UDH] [nvarchar](50) NULL,
                             [Credit] [int] NOT NULL,
                             [CurrentStatus] [int] NOT NULL,
                             [CheckDND] [bit] NULL,
                             [CheckFail] [bit] NULL,
                             [CheckBlackList] [bit] NULL,
                             [ProviderId] [int] NULL,
                             [PriorityId] [int] NULL,
                             [ScheduleDate] [datetime] NOT NULL,
                             [CreatedDate] [datetime] NOT NULL,
                             [EsmClass] [nvarchar](10) NOT NULL,
                             [DataCoding] [int] NOT NULL,
                             [Priority] [int] NOT NULL,
                             [Interface] [int] NOT NULL);
        DECLARE @PriorityIn table ([PriorityId] [int] NOT NULL);
        DECLARE @COUNT bigint;

        INSERT INTO @PriorityIn
        SELECT PriorityId
        FROM PriorityProviders
        WHERE ProviderId = @GatewayId
          AND Type = 0;

        SELECT @COUNT = COUNT(*)
        FROM MessageIn m
             LEFT JOIN @PriorityIn o ON m.PriorityId = o.PriorityId
        WHERE ((ProviderId IS NULL
            AND o.PriorityId IS NOT NULL)
            OR ProviderId = @GatewayId);

        IF @COUNT > 0
        BEGIN
            INSERT INTO #SmsIn ([Id],
                                [UserId],
                                [MaskId],
                                [Number],
                                [Message],
                                [SenderId],
                                [UDH],
                                [Credit],
                                [CurrentStatus],
                                [CheckDND],
                                [CheckFail],
                                [CheckBlackList],
                                [ProviderId],
                                [PriorityId],
                                [ScheduleDate],
                                [CreatedDate],
                                [EsmClass],
                                [DataCoding],
                                [Priority],
                                [Interface])
            (SELECT [Id],
                    [UserId],
                    [MaskId],
                    [Number],
                    [Message],
                    [SenderId],
                    [UDH],
                    [Credit],
                    [CurrentStatus],
                    [CheckDND],
                    [CheckFail],
                    [CheckBlackList],
                    [ProviderId],
                    [PriorityId],
                    [ScheduleDate],
                    [CreatedDate],
                    [EsmClass],
                    [DataCoding],
                    [Priority],
                    [Interface]
             FROM MessageIn
             WHERE MaskId IN (SELECT MaskId
                              FROM (SELECT ROW_NUMBER() OVER (PARTITION BY SenderId ORDER BY ScheduleDate) AS RowNo,
                                           MaskId
                                    FROM MessageIn msg
                                         LEFT JOIN @PriorityIn o ON msg.PriorityId = o.PriorityId
                                    WHERE ((msg.ProviderId IS NULL
                                        AND o.PriorityId IS NOT NULL)
                                        OR msg.ProviderId = @GatewayId)) res
                              WHERE res.RowNo <= @NoOfRow));

            DELETE msgin
            FROM MessageIn msgin
                 INNER JOIN #SmsIn temp ON msgin.MaskId = temp.MaskId;
        END;
        SELECT *
        FROM #SmsIn;
        DROP TABLE #SmsIn;
        COMMIT;
    END TRY
    BEGIN CATCH
        IF @@TRANCOUNT > 0
        BEGIN
            ROLLBACK TRANSACTION;
        END;
    END CATCH;

План выполнения доступен здесь: План выполнения

Обновленный запрос:

BEGIN TRY
begin tran;
CREATE TABLE #tmpMaskId (MaskId varchar(25) PRIMARY KEY)

INSERT INTO #tmpMaskId(MaskId)
SELECT DISTINCT MaskId From 
(SELECT  ROW_NUMBER() OVER ( PARTITION BY SenderId ORDER BY scheduledate ) AS RowNo, MaskId FROM MessageIn msg 
LEFT JOIN PriorityProviders o on o.ProviderId = @GatewayId AND o.Type = 0 and msg.PriorityId = o.PriorityId
WHERE  
((msg.ProviderId is null AND o.PriorityId is not null) OR msg.ProviderId = @GatewayId)
)as res WHERE res.RowNo <= @NoOfRow

Select [Id],[UserId],m.[MaskId],[Number],[Message],[SenderId],[UDH],[Credit],[CurrentStatus],[CheckDND],[CheckFail],[CheckBlackList],[ProviderId]
      ,[PriorityId],[ScheduleDate],[CreatedDate],[EsmClass],[DataCoding],[Priority],[Interface]
From MessageIn m inner join #tmpMaskId msk on m.MaskId = msk.MaskId

DELETE msgin
FROM MessageIn msgin
INNER JOIN #tmpMaskId temp ON msgin.MaskId=temp.MaskId

DROP TABLE #tmpMaskId
Commit;
END TRY
BEGIN CATCH
     IF @@TRANCOUNT > 0
     BEGIN
        ROLLBACK TRANSACTION;
     END
END CATCH;