46

I'm working on a wishlist system, where users can add items to their various wishlists, and I plan to allow users to re-order the items later on. I am not really sure about the best way to go about storing this in a database while remaining fast and not turning in to a mess (this app will be used by a fairly large user base, so I don't want it to go down to clean up stuff).

I initially tried a position column, but it seems like that would be quite inefficient having to change every other item's position value when you move them around.

I have seen people using a self-reference to refer to the previous (or next) value, but again, it seems like you would have to update a whole lot of other items in the list.

Another solution I've seen is using decimal numbers and just sticking items in the gaps between them, which seems like the best solution so far, but I'm sure there has to be a better way.

I would say a typical list would contain up to about 20 or so items, and I will probably limit it to 50. The re-ordering would be using drag and drop and will probably be done in batches to prevent race conditions and such from the ajax requests. I'm using postgres (on heroku) if it matters.

Does anyone have any ideas?

Cheers for any help!

  • Can you do a bit of benchmarking and tell us whether IO or Database will be a bottleneck? – rwong Apr 18 '13 at 20:00
  • Related question on stackoverflow. – Jordão Apr 18 '13 at 20:34
  • With self-reference, when moving an item from one place in the list to the other you only have to update 2 items. See en.wikipedia.org/wiki/Linked_list – Pieter B Nov 28 '16 at 9:33
  • Hmm, not sure why linked lists are hardly getting any attention in the answers. – Christiaan Westerbeek Jun 28 '18 at 7:15
30

First, don't try to do anything clever with decimal numbers, because they'll spite you. REAL and DOUBLE PRECISION are inexact and may not properly represent what you put into them. NUMERIC is exact, but the right sequence of moves will run you out of precision and your implementation will break badly.

Limiting moves to single ups and downs makes the whole operation very easy. For a list of sequentially-numbered items, you can move an item up by decrementing its position and incrementing the position number of whatever the previous decrement came up with. (In other words, item 5 would become 4 and what was item 4 becomes 5, effectively a swap as Morons described in his answer.) Moving it down would be the opposite. Index your table by whatever uniquely identifies a list and position and you can do it with two UPDATEs inside a transaction that will run very quickly. Unless your users are rearranging their lists at superhuman speeds, this isn't going to cause much of a load.

Drag-and-drop moves (e.g., move item 6 to sit between items 9 and 10) are a little trickier and have to be done differently depending on whether the new position is above or below the old one. In the example above, you have to open up a hole by incrementing all positions greater than 9, updating item 6's position to be the new 10 and then decrementing the position of everything greater than 6 to fill in the vacated spot. With the same indexing I described before, this will be quick. You can actually make this go a bit faster than I described by minimizing the number of rows the transaction touches, but that's a microoptimization you don't need until you can prove there's a bottleneck.

Either way, trying to outdo the database with a home-brewed, too-clever-by-half solution doesn't usually lead to success. Databases worth their salt have been carefully written to do these operations very, very quickly by people who are very, very good at it.

  • This is exactly how I handled it in a project bid preparation system we had a gazillion years ago. Even in Access, the update was likety-split fast. – HLGEM Apr 18 '13 at 19:18
  • Thanks for the explination, Blrfl! I did attempt to do the latter option, but I found that if I deleted items from the middle of the list, it would leave gaps in the positions (it was quite a naïve implementation). Is there an easy way to avoid creating gaps like this, or would I have to do it manually each time I re-ordered something (if i have to actually manage it at all)? – Tom Brunoli Apr 18 '13 at 23:00
  • 2
    @TomBrunoli: I'd have to think on the implementation a bit before saying for sure, but you might be able to pull off most or all of the renumbering automagically with triggers. E.g., if you delete item 7, the trigger decrements all rows in the same list numbered greater than 7 after the delete takes place. Inserts would do the same thing (inserting an item 7 would increment all rows 7 or higher). The trigger for an update (e.g., move item 3 between 9 and 10) would be moderately more complex but is certainly within the realm of doable. – Blrfl Apr 19 '13 at 2:42
  • I hadn't actually looked in to triggers before but that seems like a good way to do it. – Tom Brunoli Apr 19 '13 at 3:29
  • 1
    @TomBrunoli: It occurs to me that using triggers to do this may cause cascades. Stored procedures with all changes in a transaction might be the better route for this. – Blrfl Apr 20 '13 at 12:49
11

I have seen people using a self-reference to refer to the previous (or next) value, but again, it seems like you would have to update a whole lot of other items in the list.

Why? Say you take a linked-list table approach with columns (listID, itemID, nextItemID).

Inserting a new item into a list costs one insert, and one modified row.

Repositioning an item costs three row modifications (the item being moved, the item before it, and the item before its new location).

Removing an item costs one delete and one modified row.

These costs remain the same regardless of whether the list has 10 items or 10,000 items. In all three cases there's one less modification if the target row is the first list item. If you're more often operating on the last list item it may be beneficial to store prevItemID rather than next.

10

"but it seems like that would be quite inefficient"

Did you measure that? Or is that just a guess? Don't make such assumptions without any proof.

"20 to 50 items per list"

Honestly, that is not "a whole lot of items", to me that sounds just very few.

I suggest you stick to the "position column" approach (if that's the most simple implementation for you). For such small list sizes, don't start unnecessary optimizing before you experience real performance problems

10

Same answer from here https://stackoverflow.com/a/49956113/10608


Solution: make index a string (because strings, in essence, have infinite "arbitrary precision"). Or if you use an int, increment index by 100 instead of 1.

The performance problem is this: there is no "in between" values between two sorted items.

item      index
-----------------
gizmo     1
              <<------ Oh no! no room between 1 and 2.
                       This requires incrementing _every_ item after it
gadget    2
gear      3
toolkit   4
box       5

Instead, do like this (better solution below):

item      index
-----------------
gizmo     100
              <<------ Sweet :). I can re-order 99 (!) items here
                       without having to change anything else
gadget    200
gear      300
toolkit   400
box       500

Even better: here is how Jira solves this problem. Their "rank" (what you call index) is a string value that allows a ton of breathing room in between ranked items.

Here is a real example of a jira database I work with

   id    | jira_rank
---------+------------
 AP-2405 | 0|hzztxk:
 ES-213  | 0|hzztxs:
 AP-2660 | 0|hzztzc:
 AP-2688 | 0|hzztzk:
 AP-2643 | 0|hzztzs:
 AP-2208 | 0|hzztzw:
 AP-2700 | 0|hzztzy:
 AP-2702 | 0|hzztzz:
 AP-2411 | 0|hzztzz:i
 AP-2440 | 0|hzztzz:r

Notice this example hzztzz:i. The advantage of a string rank is that you run out of room between two items, you still don't have to re-rank anything else. You just start appending more characters to the string to narrow down focus.

  • 1
    I was trying to come up with some way to do this by only updating a single record, and this answer explains the solution I was thinking up in my head very well. – NSjonas Apr 10 at 16:29
5

This is really a question of scale, and use case..

How many items do you expect in a list? If millions, i think gong the decimal route is the obvious one.

If 6 then integers renumbering is the obvious choice. s Also the questions is how the lists or rearranged. If you are using a up and down arrows (moving up or down one slot at a time), the i would use integers then swap with the prev (or next) on move.

Also how often do you commit, if the user can make 250 changes then commit at once, than i say integers with renumbering again...

tl;dr: Need more info.


Edit: "Wish lists" sounds like a lot of small lists (assumption, this may be false).. So I say Integer with renumbering. (Each list contains its own Postion)

  • I'll update the question with some more context – Tom Brunoli Apr 18 '13 at 0:07
  • decimals don't work, as the precision is limited, and each inserted item potentially takes 1 bit – njzk2 Jun 13 '18 at 4:19
3

If the objective is to minimize number of database operations per reordering operation:

Assuming that

  • All shopping items can be enumerated with 32-bit integers.
  • There is a maximum size limit for a user's wish list. (I saw some popular website use 20 - 40 items as limit)

Store the user's sorted wish list as a packed sequence of integers (integer arrays) in one column. Every time the wish list is reordered, the entire array (single row; single column) is updated - which is to be performed with a single SQL update.

https://www.postgresql.org/docs/current/static/arrays.html


If the objective is different, stick with the "position column" approach.


Regarding the "speed", make sure to benchmark the stored procedure approach. While issuing 20+ separate updates for one wish list shuffle may be slow, there might be a fast way using stored procedure.

2

Use a floating point number for the position column.

You can then reorder the list changing only the position column in the "moved" row.

Basically if your user wants to position "red" after "blue" but before "yellow"

Then you just need to calculate

red.position = ((yellow.position - blue.position) / 2) + blue.position

After a few million re-positions you may get floating point numbers so small that there is no "between" -- but this is about as likely as sighting a unicorn.

You could implement this using an integer field with an initial gap of say 1000. So your intial oredring would be 1000->blue,2000->Yellow,3000->Red. After "moving" Red after blue you would have 1000->blue,1500->Red,2000->Yellow.

The problem is that with a seemingly large initial gap of 1000 as few as 10 moves will get you into a situation like 1000->blue,1001-puce,1004->biege ...... where you will no longer be able to insert anything after "blue" without re-number the whole list. Using floating point numbers there will always be a "halfway" point between the two positions.

  • 4
    Indexing and sorting in a datbase based on floats is more expensive than ints. Ints also are a nice ordinal type... doesn't need to be sent as bits to be able to be sorted on the client (the difference between two numbers that render the same when printed, but have different bit values). – user40980 Apr 18 '13 at 2:06
  • But any scheme using ints means you need to update all/most of the rows in the list every time the order changes. Using floats you only update the row which moved. Also "floats more expensive than ints" very much depends on the implementation and hardware used. Certainly the extra cpu involved is insignificant compared with the cpu required to update a row and its associated indexes. – James Anderson Apr 18 '13 at 5:58
  • 5
    For the naysayers, this solution is exactly what Trello (trello.com) does. Open up your chrome debugger and diff the json output from before/after a reorder (drag/drop a card) and you get - "pos": 1310719, + "pos": 638975.5. To be fair, most people don't do trello lists with 4 million entries in them, but Trello's list size & use case is pretty common for user-sortable content. And anything user-sortable has approximately nothing to do with high performance, int vs float sorting speed is moot for that, especially considering databases are mostly constrained by IO performance. – zelk Jan 28 '17 at 15:34
  • 1
    @PieterB As for 'why not use a 64 bit integer', it's mostly ergonomics for the developer, I would say. There is approximately as much bit depth <1.0 as there is >1.0 for your average float, so you can default the 'position' column to 1.0 and insert 0.5, 0.25, 0.75 just as easily as doubling. With integers, your default would have to be 2^30 or so, makes it a bit tricky to think about when you're debugging. Is 4073741824 bigger than 496359787? Start counting digits. – zelk Jan 28 '17 at 15:42
  • 1
    Furthermore, if you ever hit a case where you run out of space between numbers... it's not that hard to fix. Move one of them. But the important thing is that this works in a best-effort kind of way, which handles many concurrent edits by different parties (e.g. trello). You can split two numbers, maybe even sprinkle a bit of random noise, and voila, even if someone else did the same thing at the same time there is still a global order, and you didn't need to INSERT inside a transaction to get there. – zelk Jan 28 '17 at 15:51
2

OK I face this tricky problem recently, and all the answers in this Q&A post gave many inspiration. The way I see it, each solution has its pros and cons.

  • If the position field has to be sequential without gaps, then you will basically need to re-order the entire list. This is an O(N) operation. The advantage is that the client side would not need any special logic to obtain the order.

  • If we want to avoid the O(N) operation BUT STILL maintain a precise sequence, one of the approach is to use "self-reference to refer to the previous (or next) value". This is a textbook linked list scenario. By design, it will NOT incur "a whole lot of other items in the list". However, this requires the client-side (a web service or perhaps a mobile app) to implement the linked-list travesal logic to derive the order.

  • Some variation does not use reference i.e. linked list. They choose to represent the entire order as a self-contained blob, such as a JSON-array-in-a-string [5,2,1,3,...]; such order will then be stored in a separated place. This approach also has a side effect of requiring the client side code to maintain that separated order blob.

  • In many cases, we do not really need to store the exact order, we just need to maintain a relative rank among each record. Therefore we can allow gaps between sequential records. Variations includes: (1) using integer with gaps such as 100, 200, 300... but you will quickly run out of gaps and then need the recover process; (2) using decimal which comes with natural gaps, but you will need to decide whether you can live with the eventual precision limitation; (3) using string-based rank as described in this answer but be careful the tricky implementation traps.

  • The real answer can be "it depends". Revisit your business requirement. For example, if it is a wish list system, personally I would happily use a system organizes by just few ranks as "must-have", "good-to-have", "maybe-later", and then present items without particular order inside each rank. If it is a delivering system, you can very well use the delivery time as a rough rank which comes with natural gap (and natural conflict prevention as no delivery would happen at the same time). Your mileage may vary.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.