>>If you didn't need the deleted() tag before you might check that creating it for that particular query doesn't slow down other queries. No really *good* choices here, but still you can try to find the lesser evil.
>
>The result is significant when having it. It is really slow without it so I guess I will have to request the addition of that tag on the production table.

You can not compare the local access against the remote access. I just ran a COUNT on a 5 million record table and it was instant. No index on deleted() and SET DELETED is ON.