La tecnica row_number() dovrebbe essere veloce. Ho visto buoni risultati per 100.000 righe.
Stai usando row_number() simile al seguente:
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
...e hai un indice di copertura per column_list e/o un indice nella colonna 'OrderByColumnName'?
