DMFilter consultas sobre sql

Hola amigos,
Antes de dar a conocer la causa de mi problema, permitamne explicar el
escenario donde surge mi peticion de ayuda.
Existe un sistema de adquisicion de datos llamado IBA-PDA de iba-ag, el
cual recopila los datos de algun proceso donde este tenga aplicacion.
Este sistema almacena la informacion en una base de datos SQL y desde
hace tres años esta recopilando la informacion a cada minuto. La
informacion se almacena en una tabla que a su vez tiene ya mas de
1,000,000 de registros y 258 columnas.

Realize una aplicacion en VB .Net 2003 que consiste en hacer consultas a
tablas de sql, con el fin de realizar filtros en la base de datos que
genera IBA-PDA.

El problema es que:
Los usuarios hacen sus consultas, pero decean tener la mayor informacion
posible en el menor tiempo.

en algunas ocaciones sus filtros generan mas de 100,000 registros y la
aplicacion se vuelve lenta.

¿existe alguna forma de darle velocidad a la peticion de los usuarios?