Using a sort order column in a database table

Question

Let's say I have a Product table in a shopping site's database to keep description, price, etc of store's products. What is the most efficient way to make my client able to re-order these products?

I create an Order column (integer) to use for sorting records but that gives me some headaches regarding performance due to the primitive methods I use to change the order of every record after the one I actually need to change. An example:

Id    Order
5     3
8     1
26    2
32    5
120   4

Now what can I do to change the order of the record with ID=26 to 3?

What I did was creating a procedure which checks whether there is a record in the target order (3) and updates the order of the row (ID=26) if not. If there is a record in target order the procedure executes itself sending that row's ID with target order + 1 as parameters.

That causes to update every single record after the one I want to change to make room:

Id    Order
5     4
8     1
26    3
32    6
120   5

So what would a smarter person do?

• I use SQL Server 2008 R2.

Edit:

I need the order column of an item to be enough for sorting with no secondary keys involved. Order column alone must specify a unique place for its record.

In addition to all, I wonder if I can implement something like of a linked list: A 'Next' column instead of an 'Order' column to keep the next items ID. But I have no idea how to write the query that retrieves the records with correct order. If anyone has an idea about this approach as well, please share.

Answer 1

Update product set order = order+1 where order >= @value changed

Though over time you'll get larger and larger "spaces" in your order but it will still "sort"

This will add 1 to the value being changed and every value after it in one statement, but the above statement is still true. larger and larger "spaces" will form in your order possibly getting to the point of exceeding an INT value.

Alternate solution given desire for no spaces:

Imagine a procedure for: UpdateSortOrder with parameters of @NewOrderVal, @IDToChange,@OriginalOrderVal

Two step process depending if new/old order is moving up or down the sort.

If @NewOrderVal < @OriginalOrderVal --Moving down chain 

--Create space for the movement; no point in changing the original 
    Update product set order = order+1 
    where order BETWEEN @NewOrderVal and @OriginalOrderVal-1;

end if

If @NewOrderVal > @OriginalOrderVal --Moving up chain

--Create space  for the momvement; no point in changing the original  
  Update product set order = order-1 
  where order between @OriginalOrderVal+1 and @NewOrderVal
end if

--Finally update the one we moved to correct value

    update product set order = @newOrderVal where ID=@IDToChange;

Regarding best practice; most environments I've been in typically want something grouped by category and sorted alphabetically or based on "popularity on sale" thus negating the need to provide a user defined sort.

Answer 2

Use the old trick that BASIC programs (amongst other places) used: jump the numbers in the order column by 10 or some other convenient increment. You can then insert a single row (indeed, up to 9 rows, if you're lucky) between two existing numbers (that are 10 apart). Or you can move row 370 to 565 without having to change any of the rows from 570 upwards.

Answer 3

Here is an alternative approach using a common table expression (CTE).

This approach respects a unique index on the SortOrder column, and will close any gaps in the sort order sequence that may have been left over from earlier DELETE operations.

/* For example, move Product with id = 26 into position 3 */
DECLARE @id int = 26
DECLARE @sortOrder int = 3


;WITH Sorted AS (
    SELECT  Id,
            ROW_NUMBER() OVER (ORDER BY SortOrder) AS RowNumber
    FROM    Product
    WHERE   Id <> @id
)

UPDATE  p
SET     p.SortOrder = 
        (CASE 
            WHEN p.Id = @id THEN @sortOrder
            WHEN s.RowNumber >= @sortOrder THEN s.RowNumber + 1
            ELSE s.RowNumber
        END)
FROM    Product p
        LEFT JOIN Sorted s ON p.Id = s.Id 

Answer 4

It is very simple. You need to have "cardinality hole".

Structure: you need to have 2 columns:

1. pk = 32bit int

2. order = 64bit bigint (BIGINT, NOT DOUBLE!!!)

Insert/UpdateL

1. When you insert first new record you must set order = round(max_bigint / 2).

2. If you insert at the beginning of the table, you must set order = round("order of first record" / 2)

3. If you insert at the end of the table, you must set order = round("max_bigint - order of last record" / 2)

4. If you insert in the middle, you must set order = round("order of record before - order of record after" / 2)

This method has a very big cardinality. If you have constraint error or if you think what you have small cardinality you can rebuild order column (normalize).

In maximality situation with normalization (with this structure) you can have "cardinality hole" in 32 bit.

It is very simple and fast!

Remember NO DOUBLE!!! Only INT - order is precision value!

Answer 5

One solution I have used in the past, with some success, is to use a 'weight' instead of 'order'. Weight being the obvious, the heavier an item (ie: the lower the number) sinks to the bottom, the lighter (higher the number) rises to the top.

In the event I have multiple items with the same weight, I assume they are of the same importance and I order them alphabetically.

This means your SQL will look something like this:

ORDER BY 'weight', 'itemName'

hope that helps.

Answer 6

I am currently developing a database with a tree structure that needs to be ordered. I use a link-list kind of method that will be ordered on the client (not the database). Ordering could also be done in the database via a recursive query, but that is not necessary for this project.

I made this document that describes how we are going to implement storage of the sort order, including an example in postgresql. Please feel free to comment!

https://docs.google.com/document/d/14WuVyGk6ffYyrTzuypY38aIXZIs8H-HbA81st-syFFI/edit?usp=sharing