Индексы не являются чем-то, что волшебным образом ускоряет выполнение запроса, если используются, а сбор статистики может быть проведён весьма по-разному.

"Плясать" нужно от понимания физического устройства диска. Осознавания факта, что на нынешних дисках подвод головок очень медленный, передача данных очень быстрая. В результате одни и те же N блоков могут быть считаны одноблочными или многоблочными чтениями, (очень грубый) расчёт времени
1*OVERHEAD + N*TRANSFERRATE для многоблочного
N*OVERHEAD + N*TRANSFERRATE для одноблочного
и разница во скорости между ними гигантская. Где многоблочными чтениями получаете сотню мег в секунду, одноблочными получаете ~1-3 мега в секунду.

Далее, надо понимать, что табличное сканирование обычно выполняется многоблочными чтениями, поиск по индексу одноблочными (хотя есть многоблочный вариант, но это когда весь индекс сканируется целиком, без учёта порядка), так что весьма нередко проще просканировать таблицу целиком, даже очень большую.

Есть ещё такие факторы (в порядке вспоминания),
* версия СУБД
* использование RAID'а (плюс неудачное разбиение, неудачное выравнивание),
* величина буферного пула,
* величина памяти под сортировку и хешджойны
* как собрана статистика (собрано ли распределение, количество частот и квантилей, расширенная статистика индексов, многоколоночная статистика)
* разумное задание PAGESIZE, OVERHEAD, TRANSFERRATE, EXTENTSIZE, PREFETCHSIZE
* физическая упорядоченность данных в таблице
* фрагментация индексов
* наличие подходящих индексов

короче, надо просто и всего лишь представлять, как оно внутри работает. Что происходит, когда вы посылаете запрос СУБД. Почему выбран такой-то план и почему такие цифры в стоимости.

Без этого... ну... выполните
reorg table xxx (индексы тоже перестроятся), возможно, using какой-то-индекс (но надо понимать, какой)
runstats on table xxx with distribution and detailed indexes all
может, и поможет.