>First read Edward's reply to you, he has some very good points. Beyond that I have two suggestions, 1) make sure every table has an index on DELETED(), and 2) check SYS(3054,11) (note 11 and not 1 as the second argument). The 11 argument will cause SYS(3054) to report on the optimization of the join conditions as well as the where conditions.

Here what I got with SYS(3054, 11):

Joining table A and table B using index tag X
Joining table C and table D using index tag Y
Joining intermediate result and intermediate result using temp index

It seem that the last join is the evil one since it's creating a temporary index.
I will think about Edward's suggestions.

Thanks for your help