wawa

Всем спасибо. Мне уже помогли.
Проблема в том, что дефолтное default_statistics_target=100 маловат для гистограмм по моей таблице с 4 млн строк. Поставил на 1000, пересчитал стату, и теперь pg строит планы разумнее.

Имела место ошибка.
Изначально в целях оптимизаций я решил ограничить максимальный offset, ибо юзеру не нужно глубоко листать и куда разумнее поиграть с фильтром поиска. По-моему нередкий приём (хабр например).
Так как джанго пагинатор не имеет возможность ограничить offset, сделано следующее:

qs = MyModel.objects.filter(...)
objects = qs[:MAX_PAGE * PER_PAGE]  #2
paginator = Paginator(objects, PER_PAGE)
page = paginator.page(...)

Да, такой подход всегда дёргает из БД больше записей чем нужно, но (MAX_PAGE * PER_PAGE) - не большой (~500) и оверхед незаметен. Хотя может позже и напишу свой пагинатор.
Как ожидалось в строке 2 происходит запрос к БД и возвращает список объектов, который ниже передаётся пагинатору. Далее пагинатору нужно знать сколько вообще есть объектов, и он сначала, рассчитывая на QuerySet, пробует вызвать .count() и в случае неудачи вызывает .__len__(). Я полагался на второй случай и ошибся.
Оказывается в строке 2 возвращается не список, а всё еще QuerySet. Нет, я в курсе, что он ленивый, но на слайсинге "ленивость" не применима. Верно?
Так или иначе, то что получено в строке, 2 имеет метод count(), и в пагинаторе он благополучно вызывается и инициирует запрос к БД. При этом запрос какой-то чудовищный (GROUP BY зачем-то юзается).
Именно это и тормозило работу. А решение таково:

qs = MyModel.objects.filter(...)
objects = list(qs[:MAX_PAGE * PER_PAGE])  #2 !!!
paginator = Paginator(objects, PER_PAGE)
page = paginator.page(...)

Неравнодушным как всегда спасибо!