How to save a particular, mutable "order" into a Database

Question

Suppose I have some objects, and I want the user to be able to reorder them in any way they wish, say, by dragging them around. So I'd have

• cheese
• muffins
• milk

and then the user drags 'milk' to the top, making the new order

• milk
• cheese
• muffins

Is there a best practice how to store the order of these objects in a database? The naive approach would probably be to just store a numerical value called "order" for each object, but this seems like too much hassle to me, because you'd have to shuffle the order-values around most of the time.

Answer 1

The "naive" approach you suggest is also the best practice!

Answer 2

If you want to have them redisplayed in the same order AND you want them to be able to reordered at any time I don't think you can get away from storing some value that indicates display priority in the database. I've used the very approach you describe to order items in an FAQ, researchers associated with a grant, the order of items in a menu, ...

Answer 3

Taking Tony Andrews' answer into consideration, you could alternatively store a "next" index with each entry. Then when you pull them all in, walk the array by following the chain. That makes moving an item easier, as you only have to touch maximum two rows.

The disadvantage with this approach is if you ever need a subset (e.g. the first 3 items) you still need to pull in all the items, or use a SQL loop. So it's between affecting all rows during update, or accessing all items during read. As ever, measure the speed and see which is better for your situation.

Answer 4

Yup, in a relational database there is no order, it's one of the fundamental concepts. So there's just no way without a numerical value or something like that.

Answer 5

Looking at Tony Andrew's and Mark's answers in particular, it seems I really have only two alternatives:

• Saving a 'next' value, making the objects behave like a linked list (see Mark's answer)
  With this, changing the order is cheap, but I'd have to retrieve the items and then sort them by their 'next' value, which is expensive
• Saving an 'order' value (see Tony Andrew's answer)
  This makes retrieving cheap but saving a new order potentially expensive, because in the worst case, I'd have to change all the order values. cletus points out that one could use a large number in the form of 2^n for the order multiplier.

Meta: All of these answers are good and correct, which one should I choose as correct?

Answer 6

In my applications read operations are going to happen much more frequently than writes. Go with the numerical value to indicate sort order and deal with the cost of reordering the items. This is more than made up for by the fact that you can efficiently retrieve the items in the correct order for display purposes (which in a typical application happens more frequently than resorting does).

Also, as already mentioned, if you retrieve a subset of the data (filter on type or something) the remaining items are still in the proper sort order.

Remember the mantra K.I.S.S.