Stored procedure taking long time to execute

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;

    SELECT Col3   
    FROM dbo.Tab1  
    WHERE  Col1 = @Col1 
    AND Col2 = @Col2  
    AND RTRIM(LTRIM(REPLACE(REPLACE(REPLACE(REPLACE(CAST(Comments AS VARCHAR(2000)),'<br />',''),CHAR(10),''),CHAR(13),''),'&nbsp;',''))) <> ''  

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)