Here's a trick I read about some years ago, I've only just had a chance to use to full, brutal effect.
Did you know: If you use "like" in an SQL statement and put '%' on the left side of your search term, you no longer use indexes?
Your SQL Server then has to examine every single row of the table you are searching. If you have more than a few thousand rows, this is painful.
The reason is that the wildcard on the left hand side of your search term stops your term fitting nicely against the left hand edge of the index. Think of it like looking up "John%" in the phone book - you can jump straight to the "J"s, then "Jo", and so on. Once you've found John, you only have to scan a few pages to find all the "John%" - the names starting with "John". Nice and fast. As soon as you search instead for "%John", you no longer have any insight in to where to look: you have to look at every page of the phone book. .
This is pretty slow.
If you are willing and able to sacrifice some disk and memory space, here's how you fix it and get to always do lightning fast index-based searches:
Duplicate your search column and place in it the same data, but backwards. Add an Index for both searchCol and searchColReverse.
Then to search, INNER join your search table twice, searching tab1.searchCol with John%, and tab2.searchColReverse with nhoJ%.
inner join names as tab1 on tab1.fooId = foo.Id
inner join names as tab2 on tab2.fooId = foo.Id
tab1.searchCol like 'John%'
and tab2.searchColReverse like 'nhoJ%';
Each of these joins will use appropriate indexes, and the small results sets will be merged, removing results which do not appear in both sets.