>One more question to make problem clearer. If I don't have deleted records and SET DELETED ON, will it affect performance? TIA.
Yes, you'll have it. It if not related if you have deleted records or not or if you have a tag on DELETED() or not. It's when working with SET DELETE ON. This is where the performance issue is.