ну смотри, они просто хотят все строки,
Не, если бы все так было просто. Я в курсе насчет необходимости существования всех ссылок на конкретные конечные страницы, но они дибилы, они мыслят успешными/неуспешными кейсами. У них конкретный тип ротинга навигации обычно разок стрельнет и вот они хотят его во всех остальных случаях - любое отклонение от заданного - говорят, ну это уже не наши проблемы, сами не сделали, значит не можем гарантировать результата (хотя какая гарантия результата в сео).
3. Если проблема в каунтах, их можно рассчитывать отдельно в асинхронном скрипте или повесить тригер и перещитывать при вставках для каждого набора фасетов.
Ну не в каунтах проблема, а именно в пагинации, ибо пагинация по умолчанию это перебор всех записей до нужных. Насчет пересчета по крону, если бы все было неизменным, то легко бы пересчитывал, только вот обновляется постоянно

Даже максимально быстрый вариант с сортедсетом редиса не подходит, т.к. количество комбинаций уже слишком велико.
Ну попробую постгре, хотя не думаю что там что-то по другому, т.к. принцип одинаковый с мускулем в этой части.
Задача очень мутная, зачем столько данных выплёвывать поисковику. Он всё равно их не переварит, не говоря уже о пользователе листающим сотню тысяч страниц.
А разве бывают в сео не мутные задачи? лично я считаю что 99% сеошников это лютые дибилы с короной на голове.
Юзеры на сайте пролистают максимум 10 страниц и может пару раз тыкнут на последние, больше поиском пользуются.
Пока единственное что приходит в голову генерить такой полный список только всего списка и пары самых важных фильтров (т.к. в сумме комбинаций не много и можно запихнуть в редис), а все остальное лимитировать по количеству страниц.