Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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!

share|improve this question
    
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

5 Answers 5

up vote 6 down vote accepted

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.

share|improve this answer
    
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

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)

share|improve this answer
    
I'll update the question with some more context –  Tom Brunoli Apr 18 '13 at 0:07

"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

share|improve this answer

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.

http://www.postgresql.org/docs/8.2/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.

share|improve this answer

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.

share|improve this answer
3  
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). –  MichaelT 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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