Efficient way to determine whether query will return "too many records" in SQL Server

I've got a search form that could potentially return thousands of records; I'd like to show a message if the query returns more than 500 or so and make the user refine the search to get fewer results.

Am I stuck with doing a Select Count before running the actual query? What's the best practice here?

From stackoverflow

• Would you also like to show your user the first n results? This can be achieved by writing "Select top n" (n being the maximum number of rows you want to get) instead of "Select". See this link for more details.

• SELECT COUNT(*)
  FROM   (
         SELECT TOP 500 *
         FROM   mytable
         )
  

  This is more efficient than just SELECT COUNT(*)

• Select the first 501 records. You can then display them and tell the user that they should refine their search.

  Here's how

• You could consider using paging with ROW_NUMBER() OVER in T-SQL. So your user would get the first 500 and with some minor code cleverness you could requery the database to get the next set and so on. This link gives an example (the first T-SQL statement). I've found it very effective in the past.