Cuando tienes muchos registros en la base de datos, hablando de millones lo mejor es agregar index a las tablas, estos index agilizaran los querys.
Para eso buscate informacion sobre eso en la base de datos que manejes.
Mirate este Artículo esta en ingles y habla de la buena practica de el uso de los index en Sql Server 2005:
http://sqlblogcasts.com/blogs/ssqane...practices.aspx
Saludos,