Efficient way to store reorderable items in a database [closed]

Question

So I have a table of user favorites. There's a few million rows of them.

Currently, they have only three columns: id(pk),userId and someFkRef. There's an index on userId to allow me to select a user's favorites quickly.

Currently these are ordered by id which is effectively just the insert order. We'd like to offer the user a chance to re-order their favorites, most likely via some sort of drag and drop interaction.

My first (and I suspect naive) approach to this would be to simply add an order column and a composite index over userId,order. However, upon reflection, when the user moves their item some distance over the list, all intermediate rows between the item's start position and end position will need their order column recalculated and therefore, the index too.

This is (most likely) bad.

Before I spend ages trying to quantify exactly how bad, I'm wondering if there's a better table-based representation that is cheaper to manipulate with the kinds of operations I describe above.

Answer 1

For a drag and drop interaction, the better bet is a priority. You would start with the priorities being 1, 2, 3, and so on, just like a sort order.

But then, the user wants to move item 5 between 1 and 2. Voila! Give it the value of 1.5. No other values need to change. The index update takes care of the rest.

For this to work, the priority needs to be stored as a floating point number. That might be an issue. Also, a sufficiently large number of changes could result in pushing the limits of floating point. So, if a user tries to take the last element and insert it between the first two, s/he can get away with it about few dozen times or so.

You can fix this with a process that periodically reassigns number for one (or all users, if in batch) starting at 1.

Answer 2

If you don't need to be able to manipulate someFkRef across users (for instance, getting the list of users interested in something), then you could have only one record per user, with an ordered list of someFkRef (refA, refB).

But it's a form of de-normalization, and as it has some drawbacks, it really depends on your needs (and your future needs, that is where comes the trouble)