Первый вопрос который стоит задать - планы выполнения в "быстром" случае и в "медленном" одинаковые?
Удобнее всего смотреть это в ash ( v$active_session_history ).

Если да, то планы могут различаться по разным причинам, сравните два плана и посмотрите. Частая причина в партиционированных таблицах с локальными индексами - то, что какая-то из партиций индекса была инвалидна на момент выполнения запроса.
Если нет, то нужно анализировать что происходит в момент выполнения в долгом запросе - смотрите вэйты в ash, какие строки плана занимают время, какой компонент работает и т.п.