This exact situation has happened to me with Postgres' stock query planner when an automatic analyze got a bad sample of a large table.