How do I store orders?

Question

I have an app which has tasks in it and you can reorder them. Now I was woundering how to best store them. Should I have a colomn for the ordernumber and recalculate all of them everytime I change one? Please tell me a version which doesn't require me to update all order numbers since that is very time consuming (from the executions point of view).

This is especially bad if I have to put one that is at the very top of the order and then drag it down to the bottom.

• Name (ordernumber)

--

• 1Example (1)
• 2Example (2)
• 3Example (3)
• 4Example (4)
• 5Example (5)

--

• 2Example (1) *
• 3Example (2) *
• 4Example (3) *
• 5Example (4) *
• 1Example (5) *

*have to be changed in the database

also some tasks may get deleted due to them being done

Answer 1

I'd recommend having an order column in the database. When an object is reordered, swap the order value in the database between the object you reordered and the objects that have the same order value, that way you don't have to reoder the entire set of rows.

hope that makes sense...of course, this depends on your rules for re-ordering.

Answer 2

We do it with a Sequence column in the database.

We use sparse numbering (e.g. 10, 20, 30, ...), so we can "insert" one between existing values. If the adjacent rows have consecutive numbers we renumber the minimum number of rows we can.

You could probably use Decimal numbers - take the average of the Sequence numbers for rows adjacent to where you are inserting, then you only have to update the row being "moved"

Answer 3

You may keep orders as literals, and use lexical sort:

1. A
2. Z

Add a task:

1. A
3. L
2. Z

Add more:

1. A
4. B
3. L
2. Z

Move 2 between 1 and 4:

1. A
2. AL
4. B
3. L

etc.

You update only one record at a time: just take an average letter between the first ones that differ: if you put between A and C, you take B, if you put between ALGJ and ALILFG, you take ALH.

Letter next to existing counts as existing concatenated with the one next to Z. I. e. if you need put between ABHDFG and ACSDF, you count it as between ABH and AB(Z+), and write AB(letter 35/2), that is ABP.

If you run out of string length, you may always perform a full reorder.

Update:

You can also keep your data as a linked list.

See the article in my blog on how to do it in MySQL:

• Sorting Lists

In a nutshell:

/* This just returns all records in no particular order */

SELECT  *
FROM    t_list

id      parent
------- --------
1       0
2       3
3       4
4       1

/* This returns all records in intended order */

SELECT  @r AS _current,
        @r := (
        SELECT  id
        FROM    t_list
        WHERE   parent = _current
        )
FROM    (
        SELECT  @r := 0
        ) vars,
        t_list

_current id
-------  --------
0        1
1        4
4        3
3        2

When moving the items, you'll need to update at most 4 rows.

This seems to be the most efficient way to keep an ordered list that is updated frequently.

Answer 4

If you update the database after every time you update the position of one order in the list, you can accomplish the the re-ordering in the database by executing two queries per updated order.

Assuming you have an OrderIndex field in the table of orders, and that you know the position of the order before it was moved and the new position): you can write something like:

   UPDATE Orders WHERE OrderIndex >= @NewOrderIndex SET OrderIndex = OrderIndex + 1
   UPDATE Orders WHERE OrderId = @TheOrderId SET OrderIndex = @NewOrderIndex

Edit: I like Quassnoi's answer better though. It uses only one step.

Answer 5

Out of your answers I came up with a mixture which goes as follows:

Say we have:

• 1Example (1)
• 2Example (2)
• 3Example (3)
• 4Example (4)
• 5Example (5)

Now if I sort something between 4 and 5 it would look like this:

• 2Example (2)
• 3Example (3)
• 4Example (4)
• 1Example (4.5)
• 5Example (5)

now again something between 1 and 5

• 3Example (3)
• 4Example (4)
• 1Example (4.5)
• 2Example (4.75)
• 5Example (5)

it will always take the half of the difference between the numbers

I hope that works please do correct me ;)

Answer 6

This is not an easy problem. If you have a low number of sortable elements, I would just reset all of them to their new order.

Otherwise, it seems it would take just as much work or more to "test-and-set" to modify only the records that have changed.

You could delegate this work to the client-side. Have the client maintain old-sort-order and new-sort-order and determine which row[sort-order]'s should be updated - then passes those tuples to the PHP-mySQL interface.

You could enhance this method in the following way (doesn't require floats):

1. If all sortable elements in a list are initialized to a sort-order according to their position in the list, set the sort-order of every element to something like row[sort-order] = row[sort-order * K] where K is some number > average number of times you expect the list to be reordered. O(N), N=number of elements, but increases insertion capacity by at least N*K with at least K open slots between each exiting pair of elements.

2. Then if you want to insert an element between two others its as simple as changing its sort-order to be one that is > the lower element and < the upper. If there is no "room" between the elements you can simply reapply the "spread" algorithm (1) presented in the previous paragraph. The larger K is, the less often it will be applied.

The K algorithm would be selectively applied in the PHP script while the choosing of the new sort-order's would be done by the client (Javascript, perhaps).