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