Thank you for your reply Jeff ,

# Yes, We do weekly Index- Maintenance and stats

# Yes the query takes the parameters

# Sorry, Cannot share the query plan because of the work restrictions.

But i can explain,Only one Non-clustered index cost was high which was 95% during the slow performance.

Right now i'm simply dropping that Non-clustered index and recreating (Rebuild,Re-org was not fixing the issue) if the issue heads up.

By doing that, index scan cost reduced from 95% to 35%

I don't know what makes performance improvement to the query while dropping & Re-creating the index even Re-Build & Re-org was not working.