Re: What is the right way to deal with a table with rows that are not in a random order?

Note that in the OPs case I'd probably try testing things like turning
off seqscan, or lowering random_page_cost.  I'd also look at
clustering on the index for the field you're selecting on.