by ccmcarey on 1/15/21, 10:57 PM with 93 comments
by dmurray on 1/16/21, 10:00 AM
If you have a space of 64 bits to represent elements of some ordered field, and you insert items one at a time, there is some ordering of the items that allows you to make only 64 inserts.
Claiming that numbering the items with integers only allows you 16 insertions, but "It would take virtually forever to run out of space through repeated list reordering" using rational numbers just can't be correct. The author cherry-picked a bad implementation for the integers and a favourable insertion order for his pet approach.
Where exactly did he go wrong? By picking the first number in the sequence of integers to be 65536, one of the smallest of the unsigned 64-bit integers, and then deciding all the inserts would happen in descending order. If he had picked a number like 2^63 instead, he would have got at least 63 inserts no matter what the insertion order. Using this integer strategy also lends itself to easy reindexing if you do need to: the row of rank N gets reindexed to 2^64 / N. Or if you want to increase the size of the index field to 128 bits, bitshift everything left.
Note, just because we have this NFL theorem doesn't mean one approach can't outperform another in typical use patterns, but I don't see evidence for that here. The most logical integer-index strategy isn't considered and the insertion orders that exhaust the rational strategy are not particularly pathological.
by tzs on 1/16/21, 1:38 AM
This seems to have exposed a bug in HN. Clicking on the "past" link for the present submission does not turn up that past submission, although the links are identical.
However, clicking on the "past" link for that three year old submission does turn up the present submission.
by Animats on 1/16/21, 2:30 AM
This belongs to the class of problems involving trying to represent a tree in a relational database. There are many solutions, all with some problem.
by spiffytech on 1/16/21, 2:41 AM
I'm using Mudder.js to do it, but the algorithm is straightforward. Define an alphabet (e.g., A-Z). Every time an item is inserted/repositioned, its sort order is given the midpoint between the sort values of its two neighbors. So the first item is given the sort value M (midpoint between A and Z). Inserting before that item gets G (between A and M). Inserting between these two items gets J (between G and M).
Once you run out of letters between two sort values, the algorithm tacks a digit onto the sort value of the item ahead of it. So inserting between M and N yields MM. If you do this enough times in a pathological pattern and wind up with some long string of characters you can reflow your list and rebalance everything out evenly (though that's strictly an optimization for storage space/bandwidth, and not a requirement for the algorithm to function).
This all sorts perfectly with ORDER BY etc., supports an number of repositions bounded only by your storage space, and doesn't require arbitrary-precision decimal datatypes or fraction handling.
by putzdown on 1/16/21, 1:47 PM
by ramraj07 on 1/16/21, 8:26 AM
by exabrial on 1/16/21, 4:25 AM
by dizzystar on 1/16/21, 7:20 AM
I found this slide show from him. It covers the same ideas:
https://www.slideshare.net/billkarwin/models-for-hierarchica...
by swagasaurus-rex on 1/16/21, 1:35 AM
Early in a project, people stick to some heuristic, like using small z-index values like 0, 1, 2, 3... etc. But this has drawbacks because you can't add new z-index items in between without also shifting everything with a higher z-index
Using z-index values with a gap is a better bet. 0, 10, 20, 30, etc. Of course, you are limited to only a few items in between the original. You've also lost an expectation of ordering in the values.
Larger gaps make more sense, as long as you don't exceed the size of signed integers ±2147483647.
The author of the post mentions how floating point has a similar problem in the amount of floating point precision you can wring out before you end up with rounding errors.
The true crux of the problem is one of items related to one another, in other words it's a graph problem. I want these items to show up underneath these other items.
by asddubs on 1/16/21, 2:05 AM
by teddyh on 1/16/21, 1:29 AM
by smolder on 1/16/21, 3:09 AM
by conistonwater on 1/16/21, 9:32 AM
I do not see why this is necessary, you could also reindex the positions because only the relative order of integers matters. How hard can it be to recreate a bunch of integers once every 16 insertions in the same place in the list?
by geekpowa on 1/16/21, 1:16 PM
Drill the junior devs: use decimals if you want accuracy.
What is unsaid with this: if you want accuracy with monetary representation.
Lots of problems out there where decimals are simply inappropriate.
One day, rational as a core type in postgres would be a nice addition. Rationals should belong as a core type in most every platform where general purpose compute can happen.
by coding123 on 1/16/21, 2:11 AM
by throwaway189262 on 1/16/21, 11:19 AM
by tester756 on 1/16/21, 12:29 PM
ItemsOrderConfiguration Table
Id | Json (varchar(MAX) or proper JSON type in Relational DBs)
1 | [
{
"ItemId": 1,
"Order": 2
},
{
"ItemId": 2,
"Order": 1
},
]
{
"ItemId": 15,
"Order": 1
},
{
"ItemId": 32,
"Order": 2
},
]
by renatovico on 1/16/21, 12:29 PM
by _3u10 on 1/16/21, 4:51 AM
1. The position of an element in an array is not a property of the element but of the array.
2. Don't use sorted sets when you need the properties of an array / linked list.
You can store the todo list as an array of todos (use a user defined datatype), you can create another table called todo_list that contains an array of references to the todos. You can also create a linked list. Note that you'll have to use modern SQL to retrieve the linked list 'efficiently'.
The problem only becomes difficult when we dislike the obvious solutions because it violates some property of 'elegance' which apparently means restricting yourself to the 1980s versions of SQL implementations.
If the language we were writing this in was called JS and the code has the order of the array as a property of the object and we were continually sorting it every time we accessed the array instead of just reordering the array we'd recognize this as the anti-pattern it is. Similarly if for some reason using JS functions was considered 'inelegant', or for some reason using only JS features of 1996 instead of 2020.
Modern SQL has CTEs, functions, and arrays. They are very elegant when solving the problem of arrays in SQL.