There is a path in the analyze code where if the least-seen value in the sample was seen more than once (i.e. no value was seen exactly once) then it assumes that the seen values are all the values that exist. I think the logic behind that is dubious. I think it is pretty clear that that is kicking in here. But why? I think the simple answer is that you analyzed the wrong table, and the statistics shown here might be accurate for some time in the past but are no longer accurate. It is hard to see how a value present 5000 times in a table of 274602 rows could have evaded sampling if they were present at the time the sample was done.
As I mentioned in a reply to Andreas, I also added an "analyze ..." to the other two tables as an experiment. It made no difference. However ...
Your comment about missing 5000 values solved the problem: those values were only inserted in the previous SQL statement, inside of a transaction. The code is reconciling two collections across two different servers: First it inserts all new values, then it deletes obsolete values. So the "select ..." in question is including the very 5000 rows that were just inserted.
I added an "analyze" between the insert and the delete. Instant fix.
It also solves one other mystery: This query only caused problems on the small test system, and has been working well on a production database with about 100x more data. In production, each "category" is already populated with a significant amount of data. The production system already has good statistics, so this one insert/delete doesn't change the statistics.
