Generic SQL and custom sort orders

[DimPrawn]

Okay, this has bugged me for a long time.

Imagine a list held in a database table, where I want to control the sort order of the items, so that I can present the list in the order I want.

Well I could add a sortOrder column and give each item a value, 1,2,3,....5000

Now I can select and use ORDER BY sortOrder ASC

Great, but now I want the users to be able to move any item up or down the list. I could just increment/decrement sortOrder by one, but then two items would share the same sort order which is not ideal. I could renumber the sortOrder for all the items, but I may have 10,000,000 items.

So the question is, what is the optimal solution to be able to have a user controled sort order, where each item can be moved up or down the list and also be given a specific position (e.g. moved from position 3 to position 546)?

It is important that retrieving the items in the correct order is very fast and simple SQL.

[hyperD]

Disclaimer: I'm not a SQL guru...

Can you use a linked list technique here?

[DimPrawn]

Thought of that as an option (eg have a foreign key to the next item in the list), but then what would the SELECT SQL look like and how much of an impact compared to a sortOrder column?

I'm sure this is such a common requirement (user controlled sort order) that the SQL gurus will have a clever and optimised pattern for this requirement

[OrangeHopper]

Here goes, stick my head up so somebody can say how wrong I am!

Isn't the missing intelligence you want in the code that allows the user to move stuff around. It will know where you have moved from and to where in the list. It then simply updates the nextItem columns for three rows: the one before where I was; the one moved; the one before where I have moved to.

You may need a double linked list depending on the sophistication or otherwise of the front end and/or who does the update.

Sorry that isn't particularly good English but it doesn't need to be written well to be shot down in flames.

As you have probably guessed I'm not an sql guru.

[scotspine]

one question is, if you moved from position 3 to position 546, where does 546 go to? etc etc

[OrangeHopper]

I just heard a whooooosh pass straight over my head.

[maverick]

I would have thought 4 to 546 move down one place 3 becomes 546 and 547 upwards stay where they are.

[OrangeHopper]

Another whoooosh.

[maverick]

Is that the Mighty Whoooosh!

[DimPrawn]

Okay here's some example data, just has a piece of text and a desired display position

"Ford", 1
"Vauxhall", 2
"Honda", 3
"Toyota", 4
"Mazda", 5
"Saab", 6
"Porsche", 7
"Mercedes", 8
"Suzuki", 9
"BMW", 10

If I move Honda down to 9th position, it should push Suzuki up:

"Ford", 1
"Vauxhall", 2
"Toyota", 3
"Mazda", 4
"Saab", 5
"Porsche", 6
"Mercedes", 7
"Suzuki", 8
"Honda", 9
"BMW", 10

If Toyota moves up one we get:

"Ford", 1
"Toyota", 2
"Vauxhall", 3
"Mazda", 4
"Saab", 5
"Porsche", 6
"Mercedes", 7
"Suzuki", 8
"Honda", 9
"BMW", 10


If BMW moves to 2nd place, it should move Toyota down and we get:

"Ford", 1
"BMW", 2
"Toyota", 3
"Vauxhall", 4
"Mazda", 5
"Saab", 6
"Porsche", 7
"Mercedes", 8
"Suzuki", 9
"Honda", 10


So I think I can do it with a simple sortOrder column, where I have to update the sortOrder value for all rows between the original position and the new position, and either move the displaced one up or down depending if the original is above or below the target item.

At least the SELECT SQL stays simple and fast and by putting an index on the sortOrder column, fast. The downside is a lot of rows need to be updated if an item moves a long way up or down, but this I can live with.

If I went for a linked list solution, what would the SELECT SQL look like?