When the first row of long running queries is returned after a long initial wait, check the fragmentation of the indexes.
On MSSQL execute this query in the database
USE MY_DATABASE
SELECT OBJECT_NAME(Index_Info.OBJECT_ID) AS TableName
,Index_Info.name AS IndexName
,Index_Stat.index_type_desc AS IndexType
,Index_Stat.avg_fragmentation_in_percent IndexFragmPercent
FROM sys.dm_db_index_physical_stats(DB_ID(), NULL, NULL, NULL, NULL) Index_Stat
INNER JOIN sys.indexes Index_Info ON Index_Info.object_id = Index_Stat.object_id
AND Index_Info.index_id = Index_Stat.index_id
ORDER BY IndexFragmPercent DESC