Hacker News Reader

Comment by putzdown | Hacker News Reader

A linked list approach would also be worth considering. Give each item a permanent, unique id. Make each item remember the id of the next and/or previous item in the list. Reordering touches just two or three items, and there is no problem with running out of space or needing to re-index anything, ever. Of course, basic ordered query is murder from an efficiency standpoint, and the approach might be firmly rejected on that basis. But if we’re looking at approaches with a variety of tradeoffs, the linked list is worth mentioning.

View on HN

Is there a way to do this in SQL? I don’t think there’s a way to deal with low-level data structures like that within SQL, especially since SQL, as a declarative language, is meant to hide these details. I think what makes this article interesting is that it is about how to do this in SQL.

Sure. Add columns "previous" and "next"; both can also be foreign keys into this table.

Querying is a bit less straightforward, though; you need a recursive query to traverse the pointers. (Or traverse in application logic, at the cost of a bunch of unnecessary round-trips.)

Writing a select statement to return the results in order sounds tricky [I think the top-level post mentions this]. Even doing it in the application code would give me pause for thought.

It's a recursive query, but it's basically the simplest recursive query. It's not that bad.

  WITH recursive_traversal(depth, id)
  AS (
    -- base case: the root has no previous
    SELECT 0, id
    FROM todo
    WHERE previous IS NULL
      AND user_id = $1
  
    UNION ALL

    -- recursive case: traverse to next row
    SELECT depth + 1, todo.id
    FROM todo
    JOIN recursive_traversal r ON r.next = todo.id
    WHERE depth < $2
  )
  -- we only accumulated the ids, so join one more time to get the rest of the columns
  SELECT todo.*
  FROM todo
  JOIN recursive_traversal USING (id);

You're right, it's not that bad! I'm going to study recursive queries, seems like they can be really helpful for some things.

Reply on news.ycombinator.com