Доколкото мога да кажа, IN преминава през всички съвпадащи записи и ги сравнява със стойностите в клаузата, ред по ред.
Така че най-доброто, което можете да направите, е да използвате индекс на deleted и ще преминавате само през записите, където deleted = 0 .