Comment by im3w1l
7 years ago
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).
7 years ago
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).