I'd restructure the table to be split into perhaps 100 or so inherited tables (or more). That many rows in a table are usually not efficient with postgres in my experience. My target is to keep the tables under about 100 million rows. I slice them up based on the common query patterns, usually by some ID number modulo 100. I don't really ever use date ranges like most tutorials you'll see will suggest.