Make sure that the preceding columns of index are available in search criteria.
Make sure the Statistics are up-to-date: – Run update statistics on the tables in question if the DATA in these tables is changed drastically.
Check Search Arguments: – If possible avoid inequality operator. Avoid operations on columns and constant expressions that can not be evaluated at query COMPILE time.
If possible, use index covering.
If stored procedure accepts parameters, it is BETTER to recompile it at every execution.
Check the indexes are on proper columns.
Describe the tables in from clause so as the smaller table occurs FIRST and then the larger tables