Сортировка данных должна происходить после изменения ключевых свойств товара.
Если свойства товара изменяются часто — можно выделить в отдельный «демон».
Несколько десятков тысяч — не столь много для кеширования результатов сортировки.
Допустим PRIMARY KEY является INT, тогда при трех методах сортировки получится ~10000*3*INT, что совсем не много.
Хм,
— отличная архитектура из всех в мире PHP (собраны все лучшие идеи и паттерны отовсюду);
— большое профессиональное коммьюнити (top repos, geocoder, buzz, gaufrette).
Если свойства товара изменяются часто — можно выделить в отдельный «демон».