Technika row_number() by měla být rychlá. Viděl jsem dobré výsledky u 100 000 řádků.
Používáte row_number() podobné následujícímu:
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
...a máte krycí index pro column_list a/nebo index ve sloupci 'OrderByColumnName'?