Well, your suggestion made me quickly realize that I was missing two indexes. The field "CloseDate" was used often in queries, and was already indexed. The other two fields were not indexed.

Despite adding these two indexes, I am still having problems. I ran the SELECT query during peak hours, and it took 8 minutes. The execution plan was real simple. It spent 0% on the Select, 6% on Parallelism, and 94% on a clustered index scan. The clustered index is an artificial key (an identity field, because the true primary key is actually a 5-field complex key of all VARCHARs) that isn't used in the query at all. So it seems like this clustered index scan is the equivalent of a full table scan. The query selected 27,000 rows out of 55 million. Obviously a full table scan of 55 million rows to find 27,000 would be monstrously inefficient.

So it appears that I have some structural issues. I don't when the table reached 55 million rows, I don't remember it being that large. I think the table is growing faster than I expected it would, and I'm having scaling issues. I could use a few suggestions.

I don't think a composite index would help much. I think the greater than comparisons and the OR would get in the way of it using the index efficiently. (It's worth mentioning that the date fields are actually integers, packed in YYYYMMDD format.) Obviously it's decided not to use the individual indexes for some reason.

I'm not 100% sure where to go from there. I could possibly remove the CreateDate filter (which is principally there to prevent updating really old, open orders which are most likely erroneous). The principal things I'm looking for are open orders and orders closed since a specific date. Removing that part of the WHERE statement, however, had no noticeable impact on the query. It still continues to use the clustered index scan.

The clustered key is based on the WorkOrderID, which largely puts the rows in order by CreateDate. Since the clustered key is never directly used in queries, perhaps I could make it a non-clustered primary key and use CloseDate as the clustered key? It might speed up some queries, too, since CloseDate is used often in queries. I won't be able to do make this kind of change until after hours, however.

Thanks for the help and suggestion. Do you have any further ideas or thoughts?