This can happen due to many factors like lack of indexes, out of dates statistics, if it returns a large number of records, etc.
I observed a similar behavior recently in a production environment. The stored procedure had the code similar to the following;
WHERE Col1 = @Col1
AND Col2 = @Col2
AND RTRIM(LTRIM(REPLACE(REPLACE(REPLACE(REPLACE(CAST(Comments AS VARCHAR(2000)),'<br />',''),CHAR(10),''),CHAR(13),''),' ',''))) <> ''
Let me give you some background information about this table.
- Col2 and Col3 are UNIQUEIDENTIFIER
- Comments column is ntext and does not have indexes
- All three columns Col1, Col2 and Col3 has indexes
- Col2 and the PK is the clustered index of the table
- Table has 825,452,256 records (825 million)