Pessoal, tenho um procedure que é bem extensa, para rodá-la em um primeiro momento ela leva cerca de 40s, porém na segunda, terceiras e outras vezes seguintes ela demora menos de 2s.
Luan, isso acontece porque na primeira vez o SQL cria o plano de execução e armazena em memória. Nas próximas execuções ele já tem o plano definido. Agora é interessante você analisar o plano de execução e ver se está bom, se está utilzando os índices corretamente, etc. Veja também como está a fragmentação da tabela.
O Ivan esta certo, uma possibilidade seria se necessário recompilar a stored procedure para fazer a atualização do plano de execução.Pedro Antonio Galvão Junior - MVP - Windows Server System - SQL Server/Coordenador de Projetos/DBA