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

Normally I'll add an int or smallint column named something like 'Ordinal' or 'PositionOrdinal' as you suggest, and with the exact caveat you mention — the need to update a potentially significant number of records every time a single record is re-ordered.

The benefit is that given a key for a specific task and a new position for that task, the code to move an item is just two statements:

UPDATE `Tasks` SET Ordinal= Ordinal+1 WHERE Ordinal>=@NewPosition
UPDATE `Tasks` SET Ordinal= @NewPosition WHERE TaskID= @TaskID

There are other suggestions for a doubly linked list or lexical order. Either can be faster, but at the cost of much more complicated code, and the performance will only matter when you have a lot of items in the same group.

Whether performance or code-complexity is more important will depend on your situation. If you have millions of records the extra complexity might worth it. However, I normally prefer the simpler code because users normally only order small lists by hand. If there aren't all that many items in the list the extra updates won't matter. This can typically handle thousands of records without any noticeable impact in performance.

The one thing to keep in mind with your updated example is that the column is only used for sorting and not otherwise shown directly to the user. Thus, when dragging an item from the top to the bottom as shown the only thing you need to change is that one record. It doesn't matter that you'll leave the first position empty. This means there is a small potential to overflow your integer sort with enough re-ordering, but let me say again: users normally only order small lists by hand. I've never heard of this risk actually causing a problem.

Answer 2

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 3

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).

Answer 4

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 5

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 6

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.