Tem certeza de que seus índices estão sendo usados? O que o EXPLAIN PLAN informa sobre a consulta com os índices em vigor? Só porque existe um índice não significa que o Oracle irá usá-lo. Se as estatísticas não forem criadas / atualizadas, o índice provavelmente não será usado.
Veja o pacote DBMS_STATS , em particular GATHER_TABLE_STATS para mais informações.
Algo tão simples quanto
BEGIN
dbms_stats.gather_table_stats('<schema_owner>', 'TEST');
END;
/
Poderia resolver seu problema.
Observe que '<schema_owner>'
faz distinção entre maiúsculas e minúsculas. A menos que você tenha feito o contrário, será maiúsculo.