Adam Haines (1/8/2009)
...First there should be some sort of filter in the first CTE. This way you can reduce the amount of data searched through...
You are using CTE to build PagingCTE from which you then will extract the needed page. Hmm, on each request to the server you'll need to reconstruct the whole PagingCTE to retreive just a small fraction of it to the client.
For the particular case when FirstName and LastName are NOT supplied, that is, Contacts are not filtered, from what I know about the optimizer, you may wish not using CTE at all. As far as I understand, you are trying to position the first record of the current page just after the last record of the page that was previosly retreived.
Once you are using "ContactID INT IDENTITY(1,1) PRIMARY KEY CLUSTERED", why not make use of it?
CREATE PROCEDURE [dbo].[usp_ContactPaging]
SET ROWCOUNT @pageFirstRowIndex
SELECT @FirstContactID= ContactId FROM Contacts ORDER BY ContactId
At this point you have ContactId of the first row of the current page and can easily get next @pageRows rows.
The nice thing about this trick, as far as I know about the optimizer, is that you are getting @FirstContactID not in @pageFirstRowIndex steps, but due to the binary search in much less steps. For a million records it should be sort of 20.