Aqui está o que eu fiz (e é tão rápido, não importa quais registros eu retorne):
--Parameters include:
@pageNum int = 1,
@pageSize int = 0,
DECLARE
@pageStart int,
@pageEnd int
SELECT
@pageStart = @pageSize * @pageNum - (@pageSize - 1),
@pageEnd = @pageSize * @pageNum;
SET NOCOUNT ON;
WITH tempTable AS (
SELECT
ROW_NUMBER() OVER (ORDER BY FirstName ASC) AS RowNumber,
FirstName
, LastName
FROM People
WHERE Active = 1
)
SELECT
(SELECT COUNT(*) FROM tempTable) AS TotalRows,
*
FROM tempTable
WHERE @pageEnd = 0
OR RowNumber BETWEEN @pageStart AND @pageEnd
ORDER BY RowNumber