I wonder if this could be solved with partitioning on the deleted_at column; you’d only need two partitions: one for live data (deleted_at is null) and one for deleted data. Then, in Postgres at least, you could just query the live partition directly when you want to skip deleted records.