I believe this query is well optimized, but it's slow if the all the blocks aren't already in memory.
Here's example explain output. You can see it takes over 7 seconds to run when it needs to hit the disk, and almost all of it is related to checking if the user has "messages."
On a second run, it's extremely fast (< 50ms). So I'm thinking it's a lack of clustering on the "Index Cond: (to_id = users.user_id)" that's the culprit.
I'm afraid of using CLUSTER due to the exclusive lock, but I found pg_repack while researching:
Does it seem likely that doing an --order-by on the to_id column would have a significant impact in this case? pg_repack seems pretty stable and safe at this point?
I am going to try and test this in a dev environment first but wanted feedback if this seemed like a good direction?