в интербэйсе - фуллскан
я не специалист по бд честно говоря

, но решал бы так, в порядке получилось/не получилось:
1. попробовал бы избавиться от подзапросов в принципе через джоин
2. попробовал бы решить задачу не на скл а алгоритмически, скажем на аксапта
3. грохнул бы индексы по полю 1 и 2 и замерял бы
4. попробовал бы подсунуть план от 1 запросу 2
5. спросил совета у спецов