5 ms·

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 i

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.

willj 6y ago
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.
- _pastel 6y ago
  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.)
  - n4r9 6y ago
    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.
    - _pastel 6y ago
      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);
      - n4r9 6y ago
        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.
      - deleted 6y ago
        [deleted]

willj 6y ago

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.

_pastel 6y ago
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.)
- n4r9 6y ago
  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.
  - _pastel 6y ago
    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);
    - n4r9 6y ago
      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.
    - deleted 6y ago
      [deleted]