Андрей

Может быть вам достаточно будет примерной сортировки.
Рассчитайте некий упрощенный ценовой индекс для каждого объекта и сортируйте по нему.
Можно усложнить и ценовой индекс сделать также зависимым от срока аренды и недели-месяца в году.

Задача во многом аналогична тому что делают многочисленные поисковики билетов, интересно как это делают они.

Не очень понятно как и для чего вы используете сфинкс
но я бы решал это с помощью Redis, остальное уже по задаче

похоже что проблема в банальной нехватке памяти
Сервер 16Gb памяти
redis 7 Gb
php-fpm 5-8 Gb

Думаю малейшие перегрузки по памяти приводили к свопу или отказам. Подтверждений правда пока не увидел. Расгрузил сервер, убрал часть нагрузки на запасной, посмотрим как сегодня на пике нагрузки будет.

P.S. Спасибо за наводку на newrelic - штука офигенная, но и дорогая собака