Paging in SQL Server

For Last 2 weeks, we were struggling with Server Side paging with a few queries. We found that some methods worked fine with most of the queries but in some queries, they will fail. So here are my observations:

We have 3 popular methods of paging:

1. SELECT TOP 10 * FROM [MyTable] WHERE [PrimaryKey] NOT IN (SELECT TOP 10 * FROM [MyTable] ORDER BY [Name]) ORDER BY [Name]
2. Insert in a temp table variable. That way, you can get the count as well as records in 1 go and complex where clause or Order By clause won't be executed twice unlike first query
3. SELECT TOP 10 * FROM (SELECT TOP 10 * FROM (SELECT TOP 20 * FROM [MyTable] ORDER BY [Name]) ORDER BY [Name] DESC) ORDER BY [Name]

I found that for the 1st one, many people also use INNER JOIN instead of NOT IN but INNER JOIN usually takes more time and becomes too complex if "FROM" clause or "WHERE" clause is complex too. Out of the above methods, I found that the 3rd method returns result in fastest time. However, like the first method, even for 3rd method, we need to execute another query to fetch the record count. So, in many cases, even 3rd method might prove to be slow. Second method has been a consistent performer so we chose the second method. So, here's my summary of observations:

• If you don't have too many joins with complex where conditions, use the 3rd or 1st method. They perform at par in most of the cases. I prefer the first method.
• If you have too many complex joins or conditions, use the 2nd method.

From my perspective, I plan to use 2nd method throughout my applications to be consistent.

Here is a nice article showing a comparison and methods for upto 10 different techniques:

http://www.aspfaq.com/show.asp?id=2120