>Could you please elaborate more? In orher words, say, you have all indexes (except for deleted) and amount of records to retrieve is small. Does it help to have index in place or not?
It helps to have MOST indices used in the condition. However, if you have a field that takes only a few values - like a logical field "ActiveClient", or an "AgeRange" field that stores only the tens (to discriminate 0-9, 10-19, etc.), then, with an index on that field, too many index keys will have to be retrieved, from the index, for the "optimization" process. That is exactly the problem with an index on deleted() - almost all index keys are retrieved from the index, and only then does the "optimization" process start.
Perhaps you can post your query command, and especially the WHERE clause?
Difference in opinions hath cost many millions of lives: for instance, whether flesh be bread, or bread be flesh; whether whistling be a vice or a virtue; whether it be better to kiss a post, or throw it into the fire... (from Gulliver's Travels)
