How to make ability to order records in DB?

Question

I need to make ability to reorder records, storing in DB (I use MS SQL, but seems it's no matter). I see possible 2 solutions:

1. Add Order column. Then if we want to reorder 2 records, we need to change values of Order column for these 2 records. Value of the first record set to the second and vice versa. Problem - we should add an unique constraint to order column and we can't do it easy, because on the first step we catch error like:

{"Violation of UNIQUE KEY constraint 'IX_EscortItems'. Cannot insert duplicate key in object 'dbo.EscortItems'. The duplicate key value is (2, 20).\r\nThe statement has been terminated."}

2. Second approach is singly linked list. Add column Parent, store null for the first element or Id of the previous element. But we have the same problem with unique constraint.

What is the right approach to solve this problem?

Answer 1

Four options for you. I like option 4 but the first one is easiest.

Option 1. Just start one higher

The values in the Order column don't matter, just their relative values. Whether you number ten rows from 1 to 10, 11 to 20, or 57 to 66 are all the same.

Thus, a very simple solution is just to start one higher than your highest Order column: if your rows have Order values from 1 to 10, and you need to reverse them, assign them values from 20 to 11.

They will end up sorting correctly, and you will have no uniqueness violations because they are in a separate range of values.

The down side of this is that is a little tricky if you don't want to re-do the entire list and just want to swap two values.

Option 2. Include a sort version number in the uniqueness constraint

Instead of adding one column Order, add two, SortOrder and SortVersion. Apply the uniqueness constraint to the combination of these two columns.

If you want to re-order the items in the list, increase the SortVersion column by one when you save the new value for SortVersion.

Option 3. Delete the rows and re-insert them

Depending on the framework you are using, this may be the easiest option, since you will have the records stored in the application tier as domain objects. Just wipe them out and re-insert them in the order desired.

This may not be feasible if you aren't using an EF or if there are FK relationships that would result in a cascading delete.

Option 4. Store the "order by" column in a separate table

Technically speaking this is the most normalized option, since sort order is probably not an attribute of the entity but is instead an attribute of the relationship between the entity and some other entity. So Order actually violates 3NF, believe it or not-- columns values should depend on the key (1NF), the whole key (2NF), and nothing but the primary key (3NF), and in this case the Order column depends on the entity's relationship within a greater context. To normalize this you should have a join table.

So let's say you have an invoice table and an line_item table. Add a third table, invoice_line_item table that contains InvoiceID, LineItemID, and SortOrder. If you wish to re-order the rows, delete all of them, and then re-insert them. This avoids any issues with FK or related objects, since those FKs would not be in this third table but one of the other tables. This amounts to changing the relationship between the line items and the invoices, so it makes sense to delete and replace them. Naturally you will want to wrap the whole thing in a transaction.

Answer 2

There are multiple approaches that you can use:

1. The easiest one is to forgo the UNIQUE constraint on the column that specifies the ordering (either as linked list or as sequence number). It is then up to the software to ensure that eventually the database is consistent again.

2. Use sequence numbers with gaps.
   If you initially start with sequence numbers like 10, 20, 30, etc., then you can re-order them by allocating sequence numbers in-between the ones already given out.

   For example, to put the fourth element between the first and second, the sequence numbers would become 10, 15, 20, 30, 50, etc.

   To avoid running out of gaps to place elements, you can either periodically normalize the sequence numbers, or you can use floating point sequence numbers.

Answer 3

The unique constraint should be a combination of the Order column and a foreign key to a parent table. I'll use a "Shopping Cart" as an example.

Table: ShoppingCartItems
- ShoppingCartId (FK to ShoppingCarts table)
- DisplayNumber (int)

In this case, the unique constraint would ensure the combination of ShoppingCartItems.ShoppingCartId and ShoppingCartItems.DisplayNumber is unique within the table - so that a shopping cart cannot have more than one item with then same display order.

Answer 4

I use negative for temp

declare int @rowA = 7 
declare int @rowB = 22

update table set order = -@rowB where order =  @rowA; 
update table set order =  @rowA where order =  @rowB; 
update table set order =  @rowB where order = -@rowB;

You can wrap it in a transaction but most likely you are not going to get conflicts

Answer 5

Three suggestions:

1. Always make your updates in a sequence that does not cause duplicates. For example, to swap 2 and 3, first update 2 with null, then insert 2 to replace 3, then finally insert 3.
2. You will probably need a query to insert a record in the middle of the sorted list. If you number your records in sequence, you will have to renumber many records to insert one. If you use a linked list, you only have to update two. For that reason, I expect you will find the linked list less expensive at run time, and probably easier to code.
3. I think it is conventional to name your column sort_key, ordinal or perhaps position.

An open source implementation for Active Record in Ruby might inspire you. Read the source of the acts_as_list gem and compare it with these ideas.

Answer 6

Part of the basic idea of relational databases in general, is that records don't have an "inherent" order in the database itself¹.

Ordering is normally imposed on the result of a query. In this case, we can decide on what column(s) specify the order in which we want items displayed, and order the result accordingly.

For example, we might want to be able to produce reports of orders by either the date/time of each order (i.e., display them in the order in which they were placed):

select ID, value, date /* , ... */ from Orders
order by ship_date

... or the date/time the order was shipped,

select ID, value, date /* , ... */ from Orders
order by ship_date

... or perhaps descending order by size (so we can quickly see the biggest orders, regardless of when they happened).

select ID, value, date /* , ... */ from Orders
order by value desc

You can, of course, add an order_by column (by another name if you prefer) when/if you really want the orders to be displayed in an order that's entirely arbitrary (or at least based on criteria that aren't stored in the database). In this case, when want to reorder, you have a couple of choices. One is to simply not tell the database that this column contains unique values. Another is to simply avoid duplication. For your example, you started with records numbered 1 and 2. To reverse them, you can change the numbers to 4 and 3 respectively.

To carry this out programmatically, you find the largest value currently in the column², then use one greater than that as the base value when reordered. You might also want to check the minimum value currently in use. If it's greater than the number of records, you can re-start numbering from 0.

---

^{1. Though MS SQL does have a concept of a "clustered index", which directly relates to the order in which records are stored--this is basically an optimization though. 2. You'll typically index this column, so this operation we can expect this operation to be quite fast.}

Answer 7

Often when using an order column, what's important is the order itself, not the specific values. So if you use an order column, you don't have to care what the numbers in it are, so long as they are sorted correctly relative to each other.

So if you want to move a record up in the order, you can then:

• increment all the order values from the insert point and higher to create an open slot
• update the record's order value to that slot.

No conflicts

Further illustrated. If you have order values:

1,2,3,4,5,6,7,8

and you want to move the item at #7 into #3, you first run an update like

update foo set order = order +1 where container = X and order >=3

This gives you

1,2,4,5,6,7,8,9

Then you set the order value of the specific item you want to move

update foo set order = 3 where id = 102334

And you might end up with

1,2,3,4,5,6,7,9

You'd follow a similar pattern for other types of re-arrangements.

This obviously works best when you are dealing with smallish or moderately sized sets. If you have 15,000,000 records with a specific order, you'll probably want to use one of the other approaches.

Answer 8

This is where you should dig deeper into the requirements and not worry too much about the implementation. It takes care of itself. There is no one better way of doing it.

Does anyone really care if you have unique numbers to sort by? What if, as a user (assuming I'm doing this manually), I just don't care if they're all zero? If you think they inadvertently will include a duplicate and they assume the order will match what they're seeing in their interface, you can always post a warning. Again, is there a requirement for this unique and sorted number like in an invoicing system (I recall working on a system for a firm in Germany that doesn't allow gaps in these numbers)?

If there is some extremely complicated and time-consuming algorithm to do the sorting and you want to save this value for performance purposes, why bother with any constraint in the db? Let the code handle it.

I work with a system that allows the user to setup over-riding sorting on drop-down lists. The admin assigns numbers and you just make it work. A trapping for duplicates is just not worth it.