How should I store sorted items in a database?

Question

In my application, users can rearrange their favorite books in whatever order they choose.

I have a "books" table in my database with a row for each book. Currently, there's an integer column called "position" that stores the position of each book: 1 for the top book, 2 for the next one, etc.

The problem is that if someone drags a book from, say, position #11000 to position #1, I then have to make 11,000 updates to the database. This seems inefficient. Is there a better way to do this?

One idea I've had would be just to have another table called "book_sort_orderings" or something, with a row for each user. And one column would be a huge text column that stores a sorted list of book ids. Then when the user rearranges the books, I can pull this value out into my code, perform the rearrangement there, and update the database row. Of course, any time a book is added or deleted I'd have to update this array as well. Is this the "right" way to go about things? Or is there something clever I can do to speed things up without changing my current setup?

Answer 1

You'd be surprised how fast a decent DBMS can update 11,000 rows, assuming you do it in a "bulk" fashion (as opposed to making a separate database round-trip for each row).

But if you want to avoid that, use the old BASIC trick (from the time BASIC still had line numbers): leave gaps!

Instead of using positions: 1, 2, 3, 4, 5 etc... use 10, 20, 30, 40, 50 etc....

So when you need to move (say) the first item to the next-to-last place, just modify 10 to 41 and you'll end-up with: 20, 30, 40, 41, 50 etc.... Obviously, you'll need to do some fiddling in case a gap gets completely filled, but this strategy should be able almost eliminate massive UPDATEs.

---

The other possibility is to implement a doubly-linked list: instead of order, keep an ID of the previous and the next item. Reordering can be done by simply "re-linking" the IDs, much as you would in an in-memory list. Unfortunately, you'd also prevent the DBMS from sorting the items directly (at least without awkward and probably inefficient recursive queries) - you'd have to do the sorting at the application level, so I'd recommend agains it

---

And one column would be a huge text column that stores a sorted list of book ids.

Please don't do that. You'd be violating the 1NF and there are very good reasons not to do that, including data consistency and performance (you'd have to rewrite the whole field for any single change to any portion of it).

Answer 2

Your current solution does not seem to work for multiple user settings. If the book's order is set in the Book table, wouldn't it be permanent for all users?

As others have mentioned, its typically best to keep your data normalized, which would require you to add another table like you are suggesting. So you could have a new BookOrdering table. So it'd have a book_id, a user_id and position column. That way for every user and every book there is an assigned position.

So there would be a default ordering (which would not be stored in this table), but users would have the ability to change the order. The table would only record changes from default. When you want to load the user's books, you'd first check this table for a certain user_id, and then shift/adjust the order accordingly.