index scan

Did you try DTA?

Hi Ashwin,
It is Database Tuning Advisor Refer www.microsoft.com/technet/prodtechnol/sql/2005/sql2005dta.mspx
Regards

What kind of data type is used on that primary key?
Also what kind of columns are involved in the index?
http://sqlserver-qa.net/blogs/perft...-optimizer-reuses-for-better-performance.aspx fyi.
if you are using SQL 2005 then take help of plan guides - Using a feature called plan guides, you can inject query hints into a stored procedure without modifying the code. You can also exploit a new query hint USE PLAN to specify a full XML query plan for a particular query. With these two options, you can tune an application even when you don't have access to its code base.

Further I would like to know whether this is a SQL 2005 or 2000 version including the service pack level.

Index scan touches every row in the table whether or not it qualifies, the cost is proportional to the total number of rows in the table. Thus, a scan is an efficient strategy if the table is small or if most of the rows qualify for the predicate.
http://blog.sqlauthority.com/2007/03/30/sql-server-index-seek-vs-index-scan-table-scan/