Comment by dragonwriter
7 years ago
The SQL to do this is simple and straightforward using analytic functions (specifically nth_value); the performance is likely to suck hard if you don't have an appropriate index, but that's not an SQL problem, but a “sorting billions of numbers is expensive” problem.
SELECT
nth_value(num, 1) OVER ORDER BY num,
nth_value(num, 3) OVER ORDER BY num,
nth_value(num, 5) OVER ORDER BY num
FROM t
nth_value can be done in a faster way than sorting and picking. It can be done in O(n) while sorting is O(n log n).
Which is why PostgreSQL uses heap sort with a fixed max heap size for sort with a small limit (called "top-N heapsort" when running explain analyze). Then the complexity for getting the kth value is O(n log k) which is O(n).