Ordering in a database

I've got a list of items in a database (once more Microsoft Access). These items need to be displayed on a web page, in an arbitrary order that the user can decide.

That's easy enough, add an "order" field to the table, then do SELECT * FROM Foo ORDER BY [order] ASC; or whatever.

The problem is how to let the user update this. We can define the entire re-ordering process in terms of swapping: the user moves an entry down, which means the "order" field gets swapped on that entry and the one below it. Easy enough, but I see two problems:
1. if an item is moved from the top of the list to the bottom, all items need to be updated (not terribly problematic since this list will never be very long).
2. This is a multi-user system, so the following could happen: user A loads the list and changes the order, user B loads the list and changes the order, user A saves his changes, user B saves his changes. Usually I just use the "last user to click OK wins" approach, but if I only update the entries they swapped, and they picked the wrong ones, you could end up with duplicate order numbers or numbers missing. In order to prevent this I would have to update every item each time the ordering needs to be stored.

What would be a good way to deal with this? Should I perhaps use a separate "index" table to store the order, or something else entirely?

Any insights are greatly appreciated.

might I ask what the goal of the ordering is?. Is this something for the end user to make the display more friendly or does this have something to do with the business logic of the records?

For storing the order in the DB i would personally use an "index" table to hold the order simply for seperation's sake.

If the only thing you care about is the relative order of one item compared to another, then there are a couple of things to think about:

1. The actual "order number" doesn't need to be a neat, clean sequence of integers with no gaps.
2. I guess that's the only thing I was thinking. 

So considering (1) and (2) above, , I've solved this problem by using floating-point numbers for my order.  Rather than doing a swap operation, when I want to move an item to a different place in the order, I just do the following:

1. Find the order values for the two items that you want to place your item in between.
2. Average their order values and use that as the order value for your item.

With this method, you only ever need to update one row, the row that you want to move in the order.  And, you may be able to write a single query to perform the update, which would minimize your risk of duplicate entries.

(As an aside, I would think about how big of a deal duplicate entries are in your item order.  In most applications that I've done, they don't matter too much.)

Ang3lFir3 wrote:

might I ask what the goal of the ordering is?

It's an admin page for a website. It's the ordering of news items on front page (which won't always be by date).

Items with the same value would not stop the thing from functioning, except that they might not display in the intended order, and swapping them wouldn't have any effect anymore.

Why not simply add a DisplayOrder Column to the table and order by that?  :O

Sven Groot wrote:

. . .swapping them wouldn't have any effect anymore.

Might I (humbly  ) add that I think my solution to this problem is self-correcting, meaning that if two items do end up with the same ordering value, then changing the order of one of them will move it to a new, unique value.

Say your items get the following order values:

1    1.0
2    2.0
3    2.0
4    3.0

By reordering item #3 and putting it right where it is, you get the following:

1   1.0
2   2.0
3   2.5
4   3.0

jmbledsoe wrote:



Sven Groot wrote: . . .swapping them wouldn't have any effect anymore.

Might I (humbly  ) add that I think my solution to this problem is self-correcting, meaning that if two items do end up with the same ordering value, then changing the order of one of them will move it to a new, unique value.

Say your items get the following order values:

1    1.0
2    2.0
3    2.0
4    3.0

By reordering item #3 and putting it right where it is, you get the following:

1   1.0
2   2.0
3   2.5
4   3.0

That's pretty much the way I do it, except I use powers of 10

10
20
30
40

phreaks wrote:

Why not simply add a DisplayOrder Column to the table and order by that? 

Did you even read my original post?

phreaks wrote:

 That's pretty much the way I do it, except I use powers of 10

10
20
30
40

Ooh, how BASIC.

Actually that's not powers of 10. Powers of 10 would be 10, 100, 1000 etc.

What do you do when you run out of "in-between" values? RENUM? Floats at least wouldn't have that problem, but I bet it becomes a mess after a while.

Create a second table which stores UserID, RowID of the rows in the table to be sorted, and a sequence number - that way each user can preserve their own ordering and all you have to do is join the tables on RowID, matching on UserID.

Sven Groot wrote:



phreaks wrote:  That's pretty much the way I do it, except I use powers of 10 10 20 30 40

Ooh, how BASIC.

Actually that's not powers of 10. Powers of 10 would be 10, 100, 1000 etc.

What do you do when you run out of "in-between" values? RENUM? Floats at least wouldn't have that problem, but I bet it becomes a mess after a while.

Yeah, yeah yeah, I know it isn't a power of 10, but you get my point.

I am sick with the strep throat today and on my meds that make my head feel funny.

And yes, I read your post, I was trying to articulate that I agree with your idea for a seperate index table, same principal.

To tell you the truth, I have never run out of in-betweeners because our fields don't change very often.

I remember this challenge when designing some CMS sites in Vignette and the solution was use a combination of Order Index, EffectiveDate and EndDate.
When an editor attempted to add a new item, it would manage the ordering of the indexes.

That was all written in TCL/tk though.

IanL wrote:



Create a second table which stores UserID, RowID of the rows in the table to be sorted, and a sequence number - that way each user can preserve their own ordering and all you have to do is join the tables on RowID, matching on UserID.

There is only one global ordening that multiple people can change, no per-user stuff. It's an admin page.

Sven Groot wrote:


What do you do when you run out of "in-between" values? RENUM? Floats at least wouldn't have that problem, but I bet it becomes a mess after a while.

Agreed over time that would make for one crazy mess... however a little maintenance application could easily renum the floats say once a night (or hour depending on expected use), a windows service or scheduled console app could easily do that. kinda feels like a hack though so its up to you.

I know you are using Access for this but if it were SQLServer couldn't you actually do something similar to that kind of maintenance from within SQL? (just curious as I've never looked into it)

Sven Groot wrote:

but I bet it becomes a mess after a while.

Yes, it is messy (to us puny humans ), and you could write a maintenance application to renumber if you really wanted to, but why bother?  The computer doesn't care if your order is:

1.0
2.0
3.0
4.0

or

2.134567E-7
8.165843E-3
6.843781E5
5.187456E13

If you want to go into the database table and reorder things manually, you could just type 1, 2, 3, 4... and everything would work out.

In that case, it's even simpler; simply add the sequence number column and add a Read-Write lock around the code that read/modifies the ordering.

Sven Groot wrote:

1. if an item is moved from the top of the list to the bottom, all items need to be updated (not terribly problematic since this list will never be very long).

You could always implement it as:

MoveBottom(current_item)
{
   current_item.Order = MAX(Items.Order) + 1
}

Sven Groot wrote:

2. This is a multi-user system, so the following could happen: user A loads the list and changes the order, user B loads the list and changes the order, user A saves his changes, user B saves his changes. Usually I just use the "last user to click OK wins" approach, but if I only update the entries they swapped, and they picked the wrong ones, you could end up with duplicate order numbers or numbers missing. In order to prevent this I would have to update every item each time the ordering needs to be stored.

You could swap orders based on primary keys, instead of "Order".

ie

Swap(PK1, PK2)
{
   temp = item[PK1].Order

   item[PK1].Order = item[PK2].Order
   item[PK2].Order = temp
}

 It will work strangely if multiple users are in that list at the same time, but you can always blame multi-user issues.

Swapping the display order numbers on two rows should be done as one transaction and optimistic concurrency should detect when someone else has updated those rows since you read the data and so generate an exception. You can catch the exception and take the opportunity to reload the data with the new display orders and allow the user to try again.

This is one time when you might not want to use a timestamp (rowversion) for your optimistic concurrency but do it the long way by specifying the original values for the data. If all you are doing is changing the display order by swapping pairs, multiple changes might take place to move line 5 up to be line 1. This might cause lines 2, 3 & 4 to be rewritten several times with no significant change to their data. Using a timestamp (rowversion) for optimistic concurrency could give many false positive reports of clashes where using original values would not.

SimonJ