kegebinem

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

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

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

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

Создайте армию ботов и поставьте 500 5звездочных оценок
Вот они, войны клонов ботов будущего!)

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

П.с. и это скорее всего хороший знак, значит ваше приложение кого-то задело и по крайней мере конкурентоспособно.