I understand better the query planner choice now. In my case ANALYZE or not does not have an effect, I suspect this is because key_id is a relation to another table with a number of row of the same magnitude (though not 1:1), and both tables (and their ids) grow with time. A simple histogram would tell a "flat" story, while in practice there is a strong correlation between id and key_id (older entries have lower numbers, recent entries have the higher numbers), and my key_id comparison is essentially a filter on the tables' tails. The worst case happens in my case if the key_id criterion selects just the last row, the query planner currently does a full table scan with "key_id >" while a "key_id BETWEEN" scans just one row. In my case I can live with a BETWEEN, and setting the higher bound to the Max(Int64) is going to be safe. It is indeed a less obvious choice than I first thought. Thanks all!