Right, it is a prerequisite, and there are some complexities in practice. You're right -- CLUSTER is a seriously expensive operation and locks the entire table

Right, it is a prerequisite, and there are some complexities in practice. You're right -- CLUSTER is a seriously expensive operation and locks the entire table, to boot. So we didn't really do that. Instead, we used pg_repack which is a great tool to do online clustering without the locks. Additionally, we use pg_partman (another great tool!) to partition our data by month. Once a given month is finished, we can ensure the partition table for that month is ordered optimally and then never worry about it again. This particular table is mostly appended to, so it's not so bad. If you were updating or deleting records, you'd have to run pg_repack more aggressively (or take similar actions) to get good performance.