Ilia KAntorХочу первые 5 результатов:
SELECT * FROM table WHERE x BETWEEN -1000,1000 ORDER BY y

Всего результатов порядка 5 тысяч.
Размер таблицы порядка 500+ тысяч.
Т.е селективность условия - порядка 1/100

Два наиболее вероятных плана:
1) Создать индекс по (y,x), использовать его для выборки по ORDER BY и фильтровать BETWEEN
2) Создать индекс по (x,y), использовать его для выборки по BETWEEN, отсортировать по ORDER BY с хинтом FIRST_ROWS и получить первые 5 результатов

В первом случае фильтрация отбрасывает ~99 рядов из 100, во втором - совершенно не улыбает сортировка 5 тысяч, если нужно только 5.

Хотелось бы получить план, который выберет сразу то, что нужно.

P.S В реальном приложении аргументы BETWEEN сильно меняются. Кэширование не особо применимо, а запрос выполняется достаточно часто, чтобы оптимизация стала необходимой.

P.P.S Хотелось бы решение на уровне проектирования БД, а не "как настроить RDBMS". Может, GIST поможет ?
Как вариант:
Я бы посоветовал создать таблицу, напихать мусора и попробывать в реальной жизни, ибо:
.
Мне кажется, что нужно создать индекс по x, и по (x,y) (для запросов с узким диапазоном по х) и/или по (y) (для случая бездиапазонного запроса). СУБД может считать иначе.
На сколько я понял документацию, то GIST не поможет, если данные x и y - целые числа (integer). Для этих типов GIST создан для использования в многоколоночных индексах, а обычный btree быстрее.