Django - Ordered Table
I want my user to be able to add an object to the database (in my case a file), and for that object to automatically go to the last "position" , later that user would be able to use some kind of UI to change that object to be "above" or "reorder" the table.
Obviously a table doesn't have an order, its part of the basics of data tables. After reading some posts I saw I had 2 options:
- a "order" integer value that would represent the priority of this item
- a "next" pointer making it sort of an ordered list.
For me, I will make much more reads from the DB than writes so I chose the first one. My problem is how do I implement adding a new file, deleting an old one and changing order.
Currently, As I see it every time I do any change to the DB I would have to call an ORDER_BY the integer field and then:
- Delete: delete the item and update -1 everything that comes after it in the "order"
- New: Order by and give it the same number as the last item+1
- reorder: give it the "order" value of the object it surpassed and update everything that's underneath +1.
The only problem is that I feel its really expensive to make and order_by call and change so many DB rows for every little change. Is there any other way to go about it? I'm sure it's a pretty common problem.
What I would do (and what I have done) is to store an 'order' field. You can order by this column when you select and get back the records in order.
As for how to insert and reorder, that depends on how much data. For a simple 'Todo' type application, where you have < 100 items (I grabbed that number out of the air), there's nothing wrong with loading that many Model objects, updating their count and saving them.
If you have a sorted list of models, you can update the order with:
for i, model in enumerate(models): model.sort_order = i model.save()
In terms of optimisation:
Your numbers don't have to be consecutive. If you delete a record, you don't have to modify any other records, they will still be in order. So that's one operation.
If you want to insert often, then one optimisation you can make is to leave gaps (e.g. model.sort_order = i * 10) and then you have space to insert between two records. If you run out of space then you can take one of two strategies, depending on your use case:
if you do frequent inserts, then you can re-number, as above (leaving larger spaces). Re-numbering is expensive, but you have to do it infrequently
if you do not do frequent inserts, you can shuffle the numbers down (i.e. increment numbers after the inserted element). In the worst case this is as expensive as a complete re-numbering, but in the average case will half as expensive.
If you want to swap two items, you just swap their sort orders. That requires only two updates.
So the only cases where you need to update more than 2 records is when you run out of space or you want to completely change the order of all records.
For much larger lists you may be able to write some custom SQL to shuffle the numbers up, but you should only do that once you start noticing a problem.
You can update the order field for a whole series of rows in your database with a single ORM call which translates into a single DB hit:
This adds 1 to the sort_order field of all objects greater than 300, allowing you to insert your new object there.
I just came with this idea on how to reorder large group of row without having to change "all" the records, So i have never tested it. You still need an "order" column but it will be a float instead of an int.
Let's say you have this in your DB:
(A,1), (B,2), (C,3), (D,4), (E,5), (F,6), (G,7)
(where the second value is the "order" field) And you want to move F before D, i.e.:
(A,1), (B,2), (C,3), (F,6), (D,4), (E,5), (G,7)
The algorithm to update the "order" fields would be:
- Set F's order = D's order
- Set D's order to the half between his old value (4) and the value of next one (E), that is 4.5
now your table now looks like this:
(A,1), (B,2), (C,3), (F,4), (D,4.5), (E,5), (G,7)
Another example, now let's move A before D, i.e.:
(B,2), (C,3), (F,4), (A,1), (D,4.5), (E,5), (G,7)
again we update the order fields with the same algorythm. First we set A's order to D's order and D's order to the half between his old value and the next one:
(B,2), (C,3), (F,4), (A,4.5), (D,4.75), (E,5), (G,7)
With this algorythm you only have to do two UPDATES involving only 1 row each. Maybe you'll need a "next" field too on your table... and if one day the orders become messy, you could always reset them to integer values
I just came out with this idea, maybe there are more efficient ways to do it :P
Hope this helps