Кластеризацию сделал. Первые запросы (не по кэшу) могут занимать больше положенных 20-30мс (до десяти секунд). Но в целом прогресс есть. Сейчас пробую скопировать таблицу и тестировать на копии, чтобы не останавливать приложение. Что еще попробовать для мгновенного доступа к произвольным данным?