Still seems too long for only 76K rows.
1) Check fragmentation on the clus index. If it's bad, the index may need reorganized or rebuilt.
2) Compress the table if you can (if your version / edition of SQL supports it).
I have a table with like 115+ columns and it got the data around 76000 records
I ran the query ,
[ Select * from table where lastname like 'S%' ]
Its taking 15 seconds or more sometime.
There is clustered index on Lastname.
The auto statistics are on .
The query was executed on the server, (using the RDC, directly on the server) [from my local machine it takes around 1 min)
Any idea why ?
It is the time taken to display the data. From your local machine it also has to move over the network.