Индекс+кэширование запросов+"водопадный спуск" по сущностям с лимитированным количеством результатов+предварительная фильтрация объединяющих множеств (названий разделов, названий категорий и т.п.) на основе строки запроса (если это представляется возможным).