Look at the query plan, and see if it is scanning the clustered index or doing keyed lookups by joining to a table of constants. If it's a scan, let us know, and we can re-work the code to force lookups instead.