Matthew Sackman <matthew(at)lshift(dot)net> writes:
> Obviously, to me, this is a problem, I need these queries to be under a
> second to complete. Is this unreasonable?
Yes. Pulling twenty thousand rows at random from a table isn't free.
You were pretty vague about your disk hardware, which makes me think
you didn't spend a lot of money on it ... and on low-ball hardware,
that sort of random access speed just isn't gonna happen.
If the queries you need are very consistent, you might be able to get
some mileage out of CLUSTERing by the relevant index ... but the number
of indexes you've created makes me think that's not so ...
regards, tom lane