You can improve the performace by creating multiple index with different combinations of columns as per the need. The other option is if you want to fetch the columns let's say colB, colC, colD only based on colA index then you can use include while creating the index as shown in the example.
CREATE NONCLUSTERED INDEX IX_INDEX1 ON Foo (colA)
INCLUDE (colB, colC, colD);
And also look at the execution plan to identify the bottelnecks. For more details about creating index try this link
http://msdn.microsoft.com/en-us/library/ms188783.aspx[
^]
Hope this is useful.