7 ms·
Having run into this problem a few times now, Approach 1 is unfortunately best. Two reasons: (1) If updates fail, you don't get a resulting broken state (2) T
by cthor 9y ago
Having run into this problem a few times now, Approach 1 is unfortunately best. Two reasons:
(1) If updates fail, you don't get a resulting broken state
(2) The size of the lists is not that large (<50), so the extra writes are not that expensive.
Essentially, with any variation on fractional updates (where only 1-2 rows are updated per list update), the client is sending to the server "move item a to position x". Then, shortly after, "move item b to position y", etc. And if any intermediate step fails, the server and client are out of sync.
If, instead, the client message is "here is the new state of the list: (a,b,c)" and the server updates, failed requests only leave the state temporarily out of sync. The client will continue to send the complete correct state at each update.
- 220V_USKettle 9y agoI agree. I have found this to be the 'easiest' with 'smaller' list sizes (definitely less than 50 - ordering of UI elements). Implement a specific call that takes a list of all IDs in the new order, and batch run the UPDATEs on the server side. I did enjoy the article, but did not realize it was PostgreSQL specific until towards the end. Very clever, Argyle.
- speleding 9y agoI agree, but I use a small improvement to the first approach: split each insert into two steps: "insert at end" and "reorder". That way: (a) the insert is nice and simple and (b) you can reuse the code for re-order which you likely need anyway (and which solves the foreign key constraint issue, perhaps by doing it in a single SQL update).
- mason55 9y agoThat was my first thought. Disallow inserting into the middle of the list and solution 1 becomes much simpler.
- billysielu 9y agoAgree. I wonder what problem anyone would have with Approach 1 that also meant the other approaches were optimal solutions. If your problem is there are too many items in the list, that's going to be a usability problem so you'd probably need to categorize the items. If performance is such an issue that ordering <50 items with approach 1 is unacceptable you undoubtedly have performance issues with the rest of your app too.
- chris_wot 9y agoEr, wouldn’t you do all the updates in a single transaction? If one fails then it rolls back all the changes.
- etatoby 9y agoYes, ideally in a single UPDATE statement.
- adrianmonk 9y agoI'm not sure how to do that because a single UPDATE statement only has one WHERE clause. You'd have to come up with an expression to put in the SET part that gives the right values for different rows. I guess you can always swap pairs of rows with subtraction, like swapping row 5 and 7 would be: update t set user_order = 5 + (7 - user_order) where id in (123, 456) Maybe you could use case statements to make an enumerated function in the more general case of updating multiple rows, but that's a bit ugly.
- Beanis 9y agoPostgres bulk update: http://sqlfiddle.com/#!17/b3d19/1 http://sqlfiddle.com/#!17/b3d19/1 You can do something similar in MySQL with temp tables. Bulk update through upsert (slightly different than a bulk update, since it can create rows too) MySQL: http://sqlfiddle.com/#!9/a6f050/1 http://sqlfiddle.com/#!9/a6f050/1 Postgres: http://sqlfiddle.com/#!17/a8367/1 http://sqlfiddle.com/#!17/a8367/1
- adrianmonk 9y agoOK, so SQL extensions, so just the usual reasons to do bulk changes. I thought they might have mentioned it here because there was something unique to say about it in the context of this problem.
- imtringued 9y agoAnd preferably you use the postgres specific "unnest(array1, array2, ...)" function which turns array parameters passed into the query into a temporary table that you can query. UPDATE example SET position = CAST(temp.position AS INTEGER) FROM unnest(:ids, :positions) AS temp (id, position) WHERE example.id = CAST(temp.id AS INTEGER);
- baq 9y agoyou should generally use some concurrency control approach like optimistic or pesimistic locking (UPDATE state = new WHERE state = old/SELECT FOR UPDATE - but the latter isn't a good idea for UI).
- zeroimpl 9y agoI've run into this problem when keeping a single large (100000+) list sorted. In my case it was very important not to change the sort value on rows that didn't need to. I had considered most of the solutions listed in the article except for the true fraction method. I believe that solution was explored by the author as they thought floating points were somehow solving a problem that couldn't be solved by integers. I settled on an approach that is essentially Solution 2 but using integers instead, each time bisecting the other two integers. The important aspect is that when inserting at the head or tail of the list, you bisect between MININT (-2^63) or MAXINT (2^63-1) respectively.
- chii 9y agohave you considered using a string and have them sort lexographically? To insert, you have to create a new string that sorts between the two, which this library proposes an algorithm for: https://github.com/fasiha/mudderjs https://github.com/fasiha/mudderjs
- godshatter 9y agoThis was my thought, too. Use a point-based versioning-like scheme as a string (1.1.25, 1.1.26, 1.1.26.1, 1.2, etc). You will have to worry about adding prefixed 0s, though, as powers of ten are increased if you want it to sort correctly, and of course there is presumably a hard-limit on the size of the string. It might be possible to have a table that keys to the first that has a level and a value. For 1.1.26.1 above, it would have the rows (1, 1), (2, 1), (3, 26), (4, 1) (with keys to the table rows). Not sure exactly how to write the sql to join it all together and sort it, but it seems possible, at least if you have some known maximum number of levels.
- chii 9y agoif you use the full unicode space as alphabets, you can probably get a lot of mileage out of just having a 255 char column (or bigger, if expecting a large number of items constantly changing). Most databases will have a inbuilt way to lexographically sort text, and so you won't have to do anything extra. The smarts is in the computation of the ordering string.
- fusiongyro 9y agoI agree, but I note that Hibernate will put nulls in your list if you have gaps in the sequence. I have run into issues as a result of this.
- chiph 9y agoWe did #1 at a previous job - the users wanted their common countries in a list of countries to appear at the top of the drop-down (US, Canada, Germany, etc) and not in the natural sort position. It was something that practically never got changed once it was set up, so the update problem was handled manually via DBA scripts.
- yellowapple 9y agoYou could probably do #1 pretty easily with a descending sort on each country's population.
- gglitch 9y agoWe also went with option 1, but sidestepped the OP's problem by not requiring the index to be unique. I guess our naive approach was pretty expensive, but in two steps, we first incremented all values from the target position, then inserted the new item. It was performant at our scale, and seemed elegant at the time.