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%’