Как сделать удобный поиск с умным фильтром в интернет-магазине?
Я бы сделал так — EAV для хранения информации, Sphinx для поиска.

Тогда эти ваши 300+ запросов будут делаться не к базе, а к сфинксу, а если это реализовать как мульти-запросы к сфинксу то работать будет очень быстро.

Ну и заранее делать можно не все запросы, а только основные, а по мере выбора подгружать аяксом
Судя по скорости, там что-то вроде OLAP. То есть все предварительно посчитано; при добавлении нового товара соответствующие сводные цифры обновляются.