SQL - Demora en consulta

Tengo una plataforma web que hace consultas en una Base de Datos en SQL Server y genera reportes a traves de esa plataforma Web

De un teimpo a esta parte la consulta a ciertas tablas ha generado demoras a veces mas de 15 minutos algo que no deberia tomar ni un minuto por lo general.

He tratado la indexación de la tabla pero no ha dado resultado.

Alguien me puede sugerir otra técnica.

PS. La tabla no supera el millón de datos

La adivinanza no nos ayuda para nada en este caso, se requiere conocer el tipo de query que estás efectuando para hacerle un explain plan y analizar donde está consumiendo más recursos.

Saber si hace join con otra u otras tablas, si estas tienen buenos indices, que tipo de datos estás cruzando, involucra fechas, varchar muy grandes, en fin son muchos los detalles a analizar, pero dar a conocer el query y la estructura de las tablas, como están confeccionados sus índices y constraints

Muchas gracia spor la respuesta, voy a a analizar todas esas preguntas y prepararé la información para que me colaboren