>Any index on a binary value will generally not be very effective. I've heard some people say that an index on DELETED() is effective if you have a high number of deleted records, but never tested this myself.
>
>

It definitely does - I had to do this once and it made a big difference.