Walter,

You are mistaken. The deleted status of the records has no influence on the optimization using a deleted() index tag. It is the SET DELETED setting that influences the benefit or nonbenefit of that tag. If SET DELETED is ON then every record must be checked to see if ti is deleted regardless to whether or not it is actually deleted. The number of deleted records is irrelevant.

You are correct that indexes are a double edged sword, one the one hand they can act to optimize queries and on the other they must be updated with all data changes. The cdx can become bloated and should be maintained occasionally to keep its size in check.

You are also correct that the phrasing of a query can have as much and more impact on performance than the optimization level.