12

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

1
  • In that example, you wouldn't need to update all the positions. If you just set record 1 to position 6 you're good. A better example might be pulling the bottom record up to the top. Feb 13, 2009 at 18:27

6 Answers 6

14

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:

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.

3
  • 1
    I've never come across an elegant algorithm to do this (happy to be enlightened though!) so have so far preference to use a floating point number and "average" of the two adjacent values.
    – Kristen
    Feb 13, 2009 at 21:48
  • 1
    This is so clever. I wish I had seen this before doing MY implementation :-( May 28, 2009 at 3:22
  • I'm a bit inexperienced in MySql and I've got couple of questions: What does actually the SELECT statement do into the FROM field? I know it acts as a kind of view, but I don't understand the variable assignation there. Also what does the vars property mean? It would be nice to have it better explained here or in your blog ;-)
    – Aritz
    Sep 16, 2014 at 6:40
9

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.

2

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

6
  • That should work, but precision of a double is finite. (So is the size of an int, so I'm not saying it's bad: just something to be aware of). Feb 13, 2009 at 18:50
  • Also, this means doing a lookup for at least three items: the item to reorder, plus items 1 greater and 1 less than the main item's new position, so you can use their values for the new average. Depending on how you do things this can be just as expensive or even more so than just a simple update. Feb 13, 2009 at 18:53
  • Not sure I agree: "Simple update" of, say, 10 items requires some means of allocating them a new number (which might mean getting them into a temporary table first, and assigning them a number based on some sort order, and then JOINing it that to the original table to UPDATE it with a new number)
    – Kristen
    Feb 13, 2009 at 21:45
  • "precision of a double is finite" - indeed. Worth renumbering the whole table, periodically or when precision is running out somewhere, to allow growing-space
    – Kristen
    Feb 13, 2009 at 21:46
  • oh :( I thought mine was like Quassnoi's just with numbers instead of letters thought mine would take up less space on the drive and ordering by numbers was easier than by letters. Maybe mine could be okay if on every sunday or sth it recalculates them so there are no point anything anymore. Feb 14, 2009 at 10:22
1

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"

1

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

1
  • Pretty close to the real thing. This is indeed a complex thing to handle properly, especially if you have to manager some ordered lists that can be changed by multiple users at the same time. Sep 9, 2009 at 1:37
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.