SQL Server - consulta rápida

Hola amigos, tengo un formulario en visual foxpro con una tabla con + de 13 millones de registros, hago una busqueda con seek mientras el usuario presiona una tecla y la tabla se visualiza en un grid con el puntero justo en el registro; esto es rápido pero ahora debo hacerlo en SQL, pero cuando ejecuto una consulta es relativamente más lento. Quisiera saber si hay una forma de hacerlo mas rápido. Gracias a todos por sus respuestas

Un poco mas de informacion, nos ayudara a darte un comentario mas acertado.

¿Que version de SQL Server manejas?
¿Sobre que sistema operativo?

mira trabajo con SQL version 2005, el servidor debe ser windows server 2000.
No se que otra información necesitaras, bueno te agradesco la intención de ayuda, gracias

Bueno, ¿podrias decirme como es que estas haciendo esa busqueda en SQL Server?

Otra pregunta, ¿Tienes INDICES creados en tus tablas en cuestion?

Saludos

Mira este es el código;
set ANSI_NULLS ON
set QUOTED_IDENTIFIER ON
go

ALTER PROCEDURE [dbo].[P_ListaReniecPadron]
@ape_pat VARCHAR(30) = NULL,
@ape_mat VARCHAR(30) = NULL,
@nombre VARCHAR(30) = NULL,
@le VARCHAR(30) = NULL

AS

SELECT DISTINCT *
FROM
(SELECT ape_pat, ape_mat, nombre, le FROM dbo.ReniecPadron
WHERE (@ape_pat IS NULL OR ape_pat LIKE @ape_pat) AND
(@nombre IS NULL OR nombre LIKE @nombre) AND
(@ape_mat IS NULL OR ape_mat LIKE @ape_mat)
UNION
SELECT ape_pat, ape_mat, nombre, le FROM dbo.ReniecPadron
WHERE (@le IS NULL OR le LIKE @le)) Lista

no se si habran una forma mejor de hacerlo pues recien estoy viendo sql siempre trabaje con fox.

Gracias por tu respuesta y suerte

No se porque haces 2 selects, pudiendo hacerlo en uno solo, podrias decirme, ¿cuantas filas obtienes de esta consulta?

las variables que comparas con un LIKE, traen el signo de % al final.........