This shows that it thinks there will be 8,686 rows, but actually traverses 347,308.
Yes, I see what you mean.
Have you manually run a VACUUM on these tables? Preferrably a full one if you can.
Every night, it runs Vacuum verbose analyze on the entire database. We also have the autovacuum daemon enabled (in the default config).
About 2 weeks ago, I ran cluster followed by vacuum full - which seemed to help more than I'd expect.
[As I understand it, the statistics shouldn't change very much from day to day, as long as the database workload remains roughly constant. What we're actually doing is running a warehouse sorting books - so from one day to the next the particular book changes, but the overall statistics basically don't.]
I notice that you appear ot have multiple sorts going on.
Are all of those actually necessary for your output?
I think so. I didn't actually write all of this, so I can't be certain.
Also consider
using partial or multicolumn indexes where useful.
Already done that. The query was originally pretty quick, with a few weeks worth of data, but not now. (after a few months). The times don't rise gradually, but have a very sudden knee.