5 ms·

Seems like the easiest way would be to emulate a linked list. Have a pointer to the next surrogate id.

by exabrial 6y ago

andreareina 6y ago
Is there a way to sort on that without a recursive query?
- RHSeeger 6y ago
  My understanding is that it's possible, but not fast. A quick google search turned up this page, but I'm sure there are more https://stackoverflow.com/questions/515749/how-do-i-sort-a-linked-list-in-sql https://stackoverflow.com/questions/515749/how-do-i-sort-a-l... I seem to recall seeing _something_ more elegant than a linked list for this type of thing, but I don't recall what is what, offhand.
  - names_are_hard 6y ago
    All the answers on that page, except perhaps the Oracle one which uses a technique in not familiar with, are using recursion in CTEs
- lisper 6y ago
  Yes: retrieve all the records and assemble the list in memory.
names_are_hard 6y ago
The linked list solution is easiest to update, not easiest to retrieve. So it depends what scenario you're optimizing for.
- jerf 6y ago
  For pretty much any list that a human is ordering, it is the optimal solution. Humans do not manually re-order lists with more than a couple hundred elements in them in general, and I'd submit by a 1000, if you're supporting extensive manual reordering you shouldn't be. (For example, the JIRA board we use nominally orders any of thousands or 10,000s of bug in the backlog in total order, but the orders are honestly meaningless past about 50 or so, because we humans simply do not have that detailed of a total order in mind! So it mat initially look like an example, but it really isn't... it's just an accident of implementation.) A DB schema with an ID for the whole collection and a linked list is basically optimal here. Various obvious extension present themselves at that point, such as multiple orders by moving the linked list to an external table or adding reverse links. You don't need a complicated CTE, in 2021 you just query the whole list by the collection ID and assemble in memory. By the time this solution doesn't scale, you've almost certainly got other problems where your data structure no longer matches the true nature of the data. Humans do not generally have total orders on 10,000s of elements. In those rare cases where for some reason you do, which I have encountered 0 times in ~25 years, by all means use some other solution. But don't expect it to come up often.

Seems like the easiest way would be to emulate a linked list. Have a pointer to the next surrogate id.

andreareina 6y ago

Is there a way to sort on that without a recursive query?

RHSeeger 6y ago
My understanding is that it's possible, but not fast. A quick google search turned up this page, but I'm sure there are more https://stackoverflow.com/questions/515749/how-do-i-sort-a-linked-list-in-sql https://stackoverflow.com/questions/515749/how-do-i-sort-a-l... I seem to recall seeing _something_ more elegant than a linked list for this type of thing, but I don't recall what is what, offhand.
- names_are_hard 6y ago
  All the answers on that page, except perhaps the Oracle one which uses a technique in not familiar with, are using recursion in CTEs
lisper 6y ago
Yes: retrieve all the records and assemble the list in memory.

names_are_hard 6y ago

The linked list solution is easiest to update, not easiest to retrieve. So it depends what scenario you're optimizing for.

jerf 6y ago
For pretty much any list that a human is ordering, it is the optimal solution. Humans do not manually re-order lists with more than a couple hundred elements in them in general, and I'd submit by a 1000, if you're supporting extensive manual reordering you shouldn't be. (For example, the JIRA board we use nominally orders any of thousands or 10,000s of bug in the backlog in total order, but the orders are honestly meaningless past about 50 or so, because we humans simply do not have that detailed of a total order in mind! So it mat initially look like an example, but it really isn't... it's just an accident of implementation.) A DB schema with an ID for the whole collection and a linked list is basically optimal here. Various obvious extension present themselves at that point, such as multiple orders by moving the linked list to an external table or adding reverse links. You don't need a complicated CTE, in 2021 you just query the whole list by the collection ID and assemble in memory. By the time this solution doesn't scale, you've almost certainly got other problems where your data structure no longer matches the true nature of the data. Humans do not generally have total orders on 10,000s of elements. In those rare cases where for some reason you do, which I have encountered 0 times in ~25 years, by all means use some other solution. But don't expect it to come up often.