SQL - Consulta rapida en ASP

Tengo una tabla en sql server con 600 000 registros, en la cual realizo consultas, pero es una sola tabla y utilizo procedimientos almacenados para realizar consultas y visualizarlas en una pagina asp ,pero tarda mas de 100 segundos en visualizar.
Me recomiendan usar joins pero solo es una tabla,
Como le puedo hacer realizar para agilizar el tiempo de la consulta ? y no tarde mucho en visualizarla en la pagina asp

¿Tiene INDICES?, deberias considerar como columnas candidatas a indice las que estan despues del WHERE.