Technika row_number() powinna być szybka. Widziałem dobre wyniki dla 100 000 wierszy.
Czy używasz row_number() podobnie do następującego:
SELECT column_list
FROM
(SELECT column_list
ROW_NUMBER() OVER(ORDER BY OrderByColumnName) as RowNum
FROM MyTable m
) as DerivedTableName
WHERE RowNum BETWEEN @startRowIndex AND (@startRowIndex + @maximumRows) - 1
... i czy masz indeks pokrywający dla column_list i/lub indeks w kolumnie 'OrderByColumnName'?