I just completed running a test using the Deleted()
Index tag. I created 2 Identical Tables of about
1.7 Million records, one with the deleted() Tag and
one without.

I ran a series of identical queries and below are the results:

With Deleted() Tag Avg of 24.4152 Seconds
Without Deleted() Tag Avg of 16.5155 Seconds

And yes set deleted is ON.

Note: SYS(3054) Returns Full optimization on "With Deleted Tag"
and Partial Optimization on "Without Deleted Tag".

Go Figure!