(I'm not not very familiar with Postgres, but this is common among RDBMSs). What changed is size and/or statistics. Also, if the Query Optimizer supports something like parameter sniffing, that happened. Unacceptable? Not really. Annoying? Very much so.