Все плохо
Если сделать не последовательный перебор индекса а случайный, то частота долгих обращений возрастает. Примерно каждоей четвертое обращение длится 15 миллисекунд.
т.е. в среднем на таком объеме будет 4,5 миллисекунды.
Все.
На таким объемах кеширование не спасет.