Optimizing Pagination Query with Multiple User Filters on Large Table in SQL Server

I have a table with over 10 million rows tracking user activities. I created a nonclustered index on (UserID, DtModified DESC), which performs well for queries filtering a single user. However, when querying multiple users, SQL Server first joins on the UserActivities table, then sorts the results by last modified before selecting the rows. Since I’m using this query for pagination, if the combined users have 10,000 rows, SQL Server retrieves all of them, sorts them, and then selects only the first 50 rows. This approach becomes inefficient when searching for users with a large number of records. Is there a way to improve performance with better indexing? Any advice would be greatly appreciated. Thanks! **P.S.** Erik Darling previously suggested columnstore indexes in another post, but that isn’t an option for me right now. **Plan with single user:** https://www.brentozar.com/pastetheplan/?id=uvYVLDaq9D **Plan with multiple users:** https://www.brentozar.com/pastetheplan/?id=EmkR1GGa3p

-- Create a temporary table to demonstrate the issue
CREATE TABLE #UserActivities (
    ActivityID INT IDENTITY(1,1) PRIMARY KEY CLUSTERED,
    UserID INT NOT NULL,
    ActivityType VARCHAR(50) NOT NULL,
    DtModified DATETIME2 NOT NULL,
    Details NVARCHAR(MAX) NULL
);

-- Create the index we want to evaluate
CREATE NONCLUSTERED INDEX IX_UserID_DtModified 
ON #UserActivities(UserID, DtModified DESC);

-- Insert sample data (10,000 rows for demonstration)
INSERT INTO #UserActivities (UserID, ActivityType, DtModified, Details)
SELECT 
    ABS(CHECKSUM(NEWID())) % 1000 + 1 AS UserID,  -- 1,000 distinct users
    CASE WHEN n % 10 = 0 THEN 'Login' 
         WHEN n % 5 = 0 THEN 'Purchase'
         ELSE 'PageView' END AS ActivityType,
    DATEADD(MINUTE, -ABS(CHECKSUM(NEWID())) % 525600, GETDATE()) AS DtModified,
    'Sample activity details for user ' + CAST(ABS(CHECKSUM(NEWID())) % 1000 + 1 AS VARCHAR(10)) AS Details
FROM (
    SELECT TOP 10000 ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) AS n
    FROM sys.objects a
    CROSS JOIN sys.objects b  -- Cross join to get enough rows
) AS Numbers;

-- Demonstrate the index behavior
-- Good case: Single user (uses seek)
SELECT UserID, DtModified
FROM #UserActivities
WHERE UserID = 42
ORDER BY DtModified DESC;

-- Problem case: Multiple users (often uses scan)
SELECT UserID, DtModified
FROM #UserActivities
WHERE UserID IN (42, 100, 789, 1024)
ORDER BY DtModified DESC;

-- Clean up
DROP TABLE #UserActivities;