>>>>>That cracked it. It in fact did make the query faster, there were more deleted records in the table than I realised.
>>>>
>>>>Be careful. It is my experience that an index on deleted() can make local queries (not over a network), and with few records, faster; but the same query over a network, and with many more records, might actually get slower. Before deciding to keep the index on deleted(), you should test under real-life circumstances, for instance, over a network and with the number of records you expect to have in the near future.
>>>
>>>Really? I haven't encountered this -- under what circumstances is this the case?
>>
>>The circumstances where it appears I already explained: many records, and network seem to be the worst-case scenario.
>
>
>Well, I have an app with a query joining 3 tables -- one of about 500,000 records, another of about 1.5 million, and another of about 2000; and, running across a network. Adding a deleted() tag sped it up considerably. Do you mean more records than that? Or is there a particular network topology to be wary of?

I have actually seen cases where the index on deleted() speeded things up, and others, where it made things slower. I am not sure about the exact circumstances, but half a million records does seem like a lot to me.