I got this tip from a developer at a client of mine a while back and I've been meaning to share it. They had created some custom aspx pages that lived inside the CRM sitemap that helped users search across CRM and other data. The CRM queries were using FetchXML just like a regular advanced find view, but they were performing really slowly. Sometimes they were taking as long as 16 seconds to return results. No way were the users going to live with that.
After some digging around, a DBA finally was consulted (maybe we should have asked him for his opinion earlier!). It didn't take him long to give us a helpful tip that led to fixing the query and getting it to return results in under 1 second.
It turns out that SQL will ignore indexes when a query is run against a table when the query has a LIKE clause that uses "CONTAINS" (basically where there's a % sign before and after the value), as in
SELECT * FROM contacts WHERE lastname LIKE '%Smith%'
The remedy? Form your queries so they use the equivalent of a "STARTS WITH" so SQL will use the index:
SELECT * FROM contacts WHERE lastname LIKE 'Smith%'