laxikodeje

5 миллионов записей для современных СУБД - это ерунда.
Было бы 5 миллиардов - можно было бы так заморачиваться, как вы хотите.

Дело в том, что вы не правильно организовали хранение фильтров.
Это действительно простой метод, но SQL в нормализованной форме не подходит для фильтров товаров по категориям товаров и интернет-магазине.
Нужна или ДЕНОРМАЛИЗОВАННАЯ форма с дублированием.
Или вообще БД другого типа. Я лично под такую задачу фильтрации предпочитаю Tarantool, но, полагаю, годится и Solr

Или, все же самый правильный вариант - это добавить памяти гигабайт до 16 и наслаждаться результатом? :)

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

Проходитесь по специальной служебной таблице, называемой каталогом.
Извлекаете из нее названия всех ваших таблиц в вашей базе данных.

И делаете по каждой из них отдельный запрос. Объединить запросы можно через UNION

Только как вы себе это представляете в выводе?
В одной колонке у вас будут то числа, то слова, то даты????