SQL - Mantenimiento de una tabla de una BD de Sql Server

Que tal?
Mi consulta es acerca de un mantenimiento que estoy realizando a una tabla de Sql Server con Visual Basic, pasa lo siguiente, la conexión que tengo es ADO pero las consultas son extremadamente lentas, nunca he sabido cuanto duran exactamente ya que después de una hora las consultas no han termidado y mi paciencia también.
Necesito ayuda he probado con conecciones ODBC pero es igual.

Notas: La tabla posee cerca de un millón y medio de registros.
La red del edificio donde trabajo es completamente nueva.

Les agradesco infinitamente toda la ayuda que me puedan prestar. :)

Que tal alejandro. primero revisa la red que tenga los componentes hardware(Switchers, puentes, o routers) necesarios para un optimo desempeño en el trafico de red. Algunos tips para agilizar las consultas:

- Mantener las longitudes de las filas claves de las tablas compactas.

- Creacion de indices utilez para acelerar la recuperacion y seleccion de datos

- Evita los SELECT *, utiliza solo los campos que ocupes.

-Utiliza despues del SELECT xx FROM xx WHERE xx
OPTION (FAST x, FORCE ORDER, KEEP PLAN)

-Utiliza solo los protocolos de red que realmente necesites para la conexion al servidor si en tu edificio hay mas de 30 pc's utiliza solo TCP/IP

-En el servidor desactiva los servicios que no necesites.

-El Servidor donde este el Ms-SQL debera ser un MEMBER SERVER

Espero y te servian algunos de estos tips.
Saludos.
Omar.