Hacker News Reader

Comment by solidasparagus | Hacker News Reader

> makes the easy stuff easy, and the hard stuff doable

I like SQL, but I disagree. It also makes easy stuff hard.

Given many numbers (billions), how would you find the 1st, 3rd and 5th highest values?

Maybe I have done too much SQL, but for me it is trivial and easier to do than in most other languages. PostgreSQL will execute the query below in O(n) if there is no index and O(1) if there is an index on num.

Does any other language implement this in a better way? While also still giving a O(n) time complexity and O(1) space? I may have to implement my own top-n heapsort then, or my own top-n insertion sort.

    SELECT * FROM (
      SELECT
        row_number() AS n, num
      FROM t
      ORDER BY num DESC
      LIMIT 5
    ) top5 WHERE n IN (1, 3, 5);

This is assuming we do not care about ties. If we care about ties it gets a bit messier but not that bad.

In other languages, this task does not require a sort. It's just a for loop. The fact that you need a nested table and a sort illustrates my point about SQL making some easy problems hard (maybe harder is more accurate).

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).

Using an index for access path and ranking for selection

Reply on news.ycombinator.com