>>Also make sure that you have a deleted() index.
>
>
http://support.microsoft.com/support/kb/articles/q248/6/08.aspIt is usually better for performance not to create a DELETED() tag, even though it causes the query to be only partially optimized if SET DELETED is ON. The reason for this behavior is that if you are operating over a network and few records are deleted, bringing the DELETED() tag over the wire can take a non-negligible amount of time for very little gain when compared to just testing the deleted status of the fewer records in the result set.