I think (a part of) Your problem is that order by random() is O(N
logN) complexity, while You are after O(N) .
The solution (in pseudocode)
random_sample(resultset,K):
result := first K rows from resultset
resultset.scrollto(K+1)
p = K+1
while(resultset.hasMoreRows())
row = resultset.current()
resultset.advance()
if(random() < K/p)
replace a random element in result with row
p = p+1
return result
the invariant being that at each step result contains a random sample
of K elements.
It should be fairly easy to implement in plpgsql.
Greetings
Marcin
