Walter,
>This just means that even if you reach full optimization it would run just as fast as the same query but without the index on DELETED()
>
>But for the record, i'll check this.
Well, what I'm trying to say is that most likely the entire query is not optimized at all. You could easily check this with that sys() function.
Markus