There seems to be a few situations in which Postgres considers an "on average slightly better" plan over a "more predictable plan"
The failure mode of which can be the following:
SELECT min(number) FROM table WHERE filter = 'value'
(assuming a large enough table (~1M rows), indexes on number and filter separately)
If the filter is "not very selective" (10k, 1% of the table matches) but the values on the matches are mostly higher compared to the other 99% of the table - then postgres won't take that into account, and will instead assume that scanning an index on
number will be faster (and get a match after on average ~100 rows assuming a uniform distribution of values). It will then effectively scan through 999k rows before getting a match.
The same query has an alternate plan - index scanning on
filter=value which will require traversing all matches. If the filter is not very selective like before, this could be a terrible plan (1% of the table being traversed) but it is more predictable - it doesn't depend on the distribution of the values.
Incidentally, if the filter becomes selective enough (aka, the planner anticipates few enough matches), then it will systematically use this plan.
In this case, intuitively I'd like the query planner to try out the "best" plan, up to the expected cost (say, a few hundred) - then give up on that plan and carry on with the more predictable plan, in order to hedge against the worst case scenario, and run the second plan.
Would that be possible, has it been considered in the past, and is there another solution to this kind of problem?