Best way to save a ordered List to the Database while keeping the ordering

Question

I was wondering if anyone has a good solution to a problem I've encountered numerous times during the last years.

I have a shopping cart and my customer explicitly requests that it's order is significant. So I need to persist the order to the DB.

The obvious way would be to simply insert some OrderField where I would assign the number 0 to N and sort it that way.

But doing so would make reordering harder and I somehow feel that this solution is kinda fragile and will come back at me some day.

(I use C# 3,5 with NHibernate and SQL Server 2005)

Thank you

Solution 1

FWIW, I think the way you suggest (i.e. committing the order to the database) is not a bad solution to your problem. I also think it's probably the safest/most reliable way.

Solution 2

Ok here is my solution to make programming this easier for anyone that happens along to this thread. the trick is being able to update all the order indexes above or below an insert / deletion in one update.

Using a numeric (integer) column in your table, supported by the SQL queries

CREATE TABLE myitems (Myitem TEXT, id INTEGER PRIMARY KEY, orderindex NUMERIC);

To delete the item at orderindex 6:

DELETE FROM myitems WHERE orderindex=6;    
UPDATE myitems SET orderindex = (orderindex - 1) WHERE orderindex > 6;

To swap two items (4 and 7):

UPDATE myitems SET orderindex = 0 WHERE orderindex = 4;
UPDATE myitems SET orderindex = 4 WHERE orderindex = 7;
UPDATE myitems SET orderindex = 7 WHERE orderindex = 0;

i.e. 0 is not used, so use a it as a dummy to avoid having an ambiguous item.

To insert at 3:

 UPDATE myitems SET orderindex = (orderindex + 1) WHERE orderindex > 2;
 INSERT INTO myitems (Myitem,orderindex) values ("MytxtitemHere",3)

Solution 3

Best solution is a Doubly Linked list. O(1) for all operations except indexing. Nothing can index SQL quickly though except a where clause on the item you want.

0,10,20 types fail. Sequence column ones fail. Float sequence column fails at group moves.

Doubly Linked list is same operations for addition, removal, group deletion, group addition, group move. Single linked list works ok too. Double linked is better with SQL in my opinion though. Single linked list requires you to have the entire list.

Solution 4

How about using a linked list implementation? Having one column the will hold the value (order number) of the next item. I think it's by far the easiest to use when doing insertion of orders in between. No need to renumber.

Solution 5

Unfortunately there is no magic bullet for this. You cannot guarentee the order of any SELECT statement WITHOUT an order by clause. You need to add the column and program around it.

I don't know that I'd recommend adding gaps in the order sequence, depending on the size of your lists and the hits on the site, you might gain very little for the over head of handling the logic (you'd still need to cater for the occasion where all the gaps have been used up). I'd take a close look to see what benifits this would give you in your situation.

Sorry I can't offer anything better, Hope this helped.

View more solutions

Comments

[Tigraine]

I somehow feel that keeping that order may cause headaches in the future. So I asked and maybe someone finds a better solution.

[user1066101]

Since you usually fetch the whole cart for display purposes, renumbering the whole cart doesn't seem to actually be a problem.

[Roland Tepp]

Don't worry - there is no better way than using the ordering column. As for the future headaches... do not try to optimize for the use cases that you are not aware of.

[user1066101]

Since you usually fetch the whole cart for display purposes, renumbering the whole cart doesn't seem to actually be a problem

[Tigraine]

I agree, it just felt too fragile. But after I realized I can put the whole ordering logic in the Repository and the whole thing is transparent to my Business Code it works perfectly. Thanks for your advice.

[belugabob]

That would only be OK if you wrote the system in BASIC ;-)

[belugabob]

Seriously, though, this approach would only postpone the need to actually do a sort, and then you have two different bits of functionality in your code. If you're probably going to have to handle a sort at some point, why not just do it at the start and keep the level of complexity down?

[user35559]

This is the best solution IMHO. For e.g., I have more than 300 movies in my Netflix queue. If I move an item from position 297 to the top, netflix would not have to do 300 updates. Just 3 updates at best

[cdmckay]

What comes after Z in your varchar field sorting?

[Kevin Coulombe]

If the list happened to be large enough that you would not want to update every row when you reorder something, you might be able to use a floating point DisplayOrder column. I haven't tried it but it's just an idea...

[akn]

What is the best way to get the first 50 items? Do I need to read them one-by-one, or is there any magic sql solution?

[Decade Moon]

@akn This would be possible using a recursive query and then limiting the number of rows by 50 to get the first 50 rows.

[David Given]

Does the absence of locality grouping cause problems? i.e., does reading the list in sequence cause a prohibitive number of disk seeks as the cursor jumps around the database?

[ANewGuyInTown]

I do not understand how does doubly linked list help with "ordering" and "saving order sequences as float or int" in database? Isn't doubly linked list operation only happen on the application side? How do you update the database with the list? you'll still have to write an algorithm to save the ordered column in database. Unless I'm missing something.

[States]

@ANewGuyInTown He is saying implement your row data structure as if it were a doubly linked list. An entry would have references to before and after siblings in the list hierarchy.

[xji]

I also thought about this but what about the performance. Wouldn't recursively querying dozens of items take much more time than the rank ID method? Guess it might be more suited to scenarios where reordering is frequent and the number of items isn't very large then, just as what we learnt from the algorithms and data structures basics.