Hacker News Reader

Comment by cthor | Hacker News Reader

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.

View on HN

I'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.

have 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

This 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.

if 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.

Nope but I will next time. This is quite clever. It's likely equivalent to using arbitrary precision numbers but probably performs a lot better.

Agree. 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.

I assume that this method was invented for storing some large ordered list - not for a literal Todo list app. Any realistically sized Todo list can be stored anywhere. Hell, you could probably use pingfs for it.

You could even use a paper actually :)

I 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).

That was my first thought. Disallow inserting into the middle of the list and solution 1 becomes much simpler.

Er, wouldn’t you do all the updates in a single transaction? If one fails then it rolls back all the changes.

Yes, ideally in a single UPDATE statement.

I'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.

Postgres bulk update:

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

Postgres: http://sqlfiddle.com/#!17/a8367/1

And 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);

OK, 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.

This is just off the top of my head, but to move an item from position P to Q, you would do something like this:

    update items
    set pos = case
        when pos = P then Q
        when P < Q and pos between P and Q then pos - 1
        when Q < P and pos between Q and P then pos + 1
        else pos
    end

Plus a where clause to limit the shuffling to the actual list being reordered, since you would keep all users' lists in the same table.

idk if this is what the parent had in mind, but this seems straightforward enough:

    update t
    set user_order =
        case
        when id = 123
        then 500
        else user_order + 1
        end
    where id = 123 or user_order >= 500;

If you do them in a transaction with the correct isolation level, it will appear as a single atomic update.

We 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.

You could probably do #1 pretty easily with a descending sort on each country's population.

I 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.

We 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.

you 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).

I 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.

Reply on news.ycombinator.com