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!

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.
