1) Make front-end calculate the next-id for each element after a sort, and call the back-end to update only required records.
2) next_id is a unique key, so if data was stale, worst case, a transaction error occurs, inform user that sort failed and undo the optimistic update, but this happens if multiple users are sorting the same list like crazy. generally, it just works. can be problematic if users are doing mass updates on a giant list. in such a case, instead of allowing free-sort, adding a user-adjustable "priority" column which allows equals would make much more sense.
3) deletes and inserts are more costly, because now they also require an extra read and update, but we never have the case of updating the whole list, and updating a record through a unique indexed key is an insignificant cost (in most cases - noted as otherwise someone would surely nerd-snipe me with an uncommon case, hehe).
4) for whatever reason, you want sorted results from the back-end and not do sorting on the front-end, if keys are not sorted, means recursive CTE, which isn't the end of the world but could be slower and means additional complexity.
5) you can change next_id to prev_id and spare the updates for the common case of inserting at the bottom (you still need the read, and a retry mechanism on transaction fail though)
If your application only needs to deal with the list as a whole, then this doesn't matter, you load it in and build the linked list in memory using a hash lookup. Or as someone else mentioned recursive CTEs can do it too but for something small I'd just load it in and be done with it. This article is really overthinking things for the typical real world case.
I thought the point of the article is it just interesting that sql seems well suited for lists, and has primitives for ordering but that within sql alone a performant ordered list is more complicated than one would expect before thinking.
Why the constraint on sql alone? In many reporting systems you can generate reports based on an sql query, so a query that pulls out the data in order can be useful in a real world use case.
I used this approach as part of a personal learning project. It ended up working very well because I was using Mongo, so I could just use $graphLookup with an index on the next ID.
It was definitely fast enough for my purposes, sorting about 30k items in 3 different linked lists in just a second or two. The function allows you to limit your depth or modify your starting location in the linked list (graph) which opens a lot of possibilities and/or performance improvements when only loading the first N records.
It seems like you're in one of two situations: (1) you want the entire list, or (2) you want a small "page" of entries in the list, starting from a known point. For (1), you can fetch all of the entries in table order, whatever that may be, and then figure out the list order after you have the entries. For (2), you make the database do seeks for you in a loop, but it's not such a big deal because it's a small number of them.
I guess the worst case is where you want to iterate over a large dataset in list order, but either you can't fit it in memory, or you don't want it all to go over the wire. In that case...yeah I don't know...what's the linked list equivalent of a B-tree? :)
I don't think a linked list that stores multiple elements really gets its own special name (beyond "unrolled") but you can read more about implementation considerations at https://en.wikipedia.org/wiki/Unrolled_linked_list
Fortunately modern SQL dialects that support recursive CTEs make the syntax for doing this in a single query approachable . I haven't found good data on how performant recursive CTEs are at scale, but it's surely better than doing the loop with round trips to the database inside your application code.
Recursive CTEs are an excellent way to write a very slow query.
You save the cost of network round trips, parsing the query, optimizing the join order etc., but your recursive CTE is otherwise executed once per iteration. For trees, that's typically the depth; for linked lists, it'll be the length of the list. In practice they both suck, and will be trivially outperformed by almost any other technique.
Comments
Why not (assuming that every entry has a unique ID) add a “next_id” field, and treat it like a linked list?
I implemented this. Some notes:
1) Make front-end calculate the next-id for each element after a sort, and call the back-end to update only required records.
2) next_id is a unique key, so if data was stale, worst case, a transaction error occurs, inform user that sort failed and undo the optimistic update, but this happens if multiple users are sorting the same list like crazy. generally, it just works. can be problematic if users are doing mass updates on a giant list. in such a case, instead of allowing free-sort, adding a user-adjustable "priority" column which allows equals would make much more sense.
3) deletes and inserts are more costly, because now they also require an extra read and update, but we never have the case of updating the whole list, and updating a record through a unique indexed key is an insignificant cost (in most cases - noted as otherwise someone would surely nerd-snipe me with an uncommon case, hehe).
4) for whatever reason, you want sorted results from the back-end and not do sorting on the front-end, if keys are not sorted, means recursive CTE, which isn't the end of the world but could be slower and means additional complexity.
5) you can change next_id to prev_id and spare the updates for the common case of inserting at the bottom (you still need the read, and a retry mechanism on transaction fail though)
That was my thought, but the query is not simple to get the list in order. Plus inserts also require an update.
If your application only needs to deal with the list as a whole, then this doesn't matter, you load it in and build the linked list in memory using a hash lookup. Or as someone else mentioned recursive CTEs can do it too but for something small I'd just load it in and be done with it. This article is really overthinking things for the typical real world case.
I largely agree with everything you said.
I thought the point of the article is it just interesting that sql seems well suited for lists, and has primitives for ordering but that within sql alone a performant ordered list is more complicated than one would expect before thinking.
Why the constraint on sql alone? In many reporting systems you can generate reports based on an sql query, so a query that pulls out the data in order can be useful in a real world use case.
Rebuilding a linked list can be very expansive compared to a SELECT * ORDER BY position;
I used this approach as part of a personal learning project. It ended up working very well because I was using Mongo, so I could just use $graphLookup with an index on the next ID.
It was definitely fast enough for my purposes, sorting about 30k items in 3 different linked lists in just a second or two. The function allows you to limit your depth or modify your starting location in the linked list (graph) which opens a lot of possibilities and/or performance improvements when only loading the first N records.
How do you get the list back in order if there are thousands of entries?
It seems like you're in one of two situations: (1) you want the entire list, or (2) you want a small "page" of entries in the list, starting from a known point. For (1), you can fetch all of the entries in table order, whatever that may be, and then figure out the list order after you have the entries. For (2), you make the database do seeks for you in a loop, but it's not such a big deal because it's a small number of them.
I guess the worst case is where you want to iterate over a large dataset in list order, but either you can't fit it in memory, or you don't want it all to go over the wire. In that case...yeah I don't know...what's the linked list equivalent of a B-tree? :)
I don't think a linked list that stores multiple elements really gets its own special name (beyond "unrolled") but you can read more about implementation considerations at https://en.wikipedia.org/wiki/Unrolled_linked_list
A skip list: https://en.wikipedia.org/wiki/Skip_list
Retrieving the list will involve a lot of random seeks. A database is not that great at it versus scans.
Fortunately modern SQL dialects that support recursive CTEs make the syntax for doing this in a single query approachable . I haven't found good data on how performant recursive CTEs are at scale, but it's surely better than doing the loop with round trips to the database inside your application code.
Recursive CTEs are an excellent way to write a very slow query.
You save the cost of network round trips, parsing the query, optimizing the join order etc., but your recursive CTE is otherwise executed once per iteration. For trees, that's typically the depth; for linked lists, it'll be the length of the list. In practice they both suck, and will be trivially outperformed by almost any other technique.
A linked list is a degenerate tree, after all
I agree, that seems like a better approach, though there isn't really a way to do the sorting in plain SQL with that method.