How to speed up SELECT with high variance of highly selective WHERE and sort?

Question

PostgreSQL

There is a table T with fields A, B, C and D.
The type of the fields is not so important, the main thing is that the more / less comparison operators (int, float, timestamp, ...) are applicable to them.
Queries to this table have the following variations:
1) Sorting is always applied (ASC or DESC) by any one of the listed fields.
2) Min/max restrictions are possible (only min, only max, or both) for any of the listed fields in any combination.
At a certain number of lines, everything works slowly. That is the problem.
What has already been done:
1) Built b-tree indexes for all fields, which gave an excellent result in speeding up queries where:
a) only sorting occurs
b) low selective restrictions are applied along with sorting
c) when a highly selective constraint is applied to the same field on which the sort is performed.
In principle, the result is predictable.
Probably already clear when problems arise. Namely, with highly selective restrictions on a field other than the sort field.
The selectivity of such restrictions can be zero. Then the pipe.
The problem does not seem unique to me. How to deal with it?

Answer 1

Thanks to all. They already helped me.
The problem is that the default default_statistics_target=100 is too small for histograms in my table with 4 million rows. I set it to 1000, recalculated the stat, and now pg makes smarter plans.