The end game is adaptive query plans. A big reason the initial plan isn't guaranteed to be optimal, even with all the right indexes, is that table statistics a

The end game is adaptive query plans. A big reason the initial plan isn't guaranteed to be optimal, even with all the right indexes, is that table statistics aren't perfect. For example, you might track a column's correlation (how closely the column's logical ordering matches its physical ordering in the heap), but that won't be broken down at a per value level. Postal code X might be very correlated, while postal code Y that is used in your query is completely uncorrelated. The ideal solution is to pick one plan initially, and then update a temporary query-specific statistic model based on the data you actually read while executing the query. Then periodically re-evaluate if an alternative plan would be faster, switching to it in a way that doesn't throw away the current partial result. Of course switching plans mid flight is very complicated, but Oracle and SQL server both support this feature, so hopefully it lands in Postgres at some point.