>>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.

Make sure that you use a binary index on deleted(), a binary index is much smaller and more efficient.