How to design table that can be re-sequenced?

Question

I need to make a design decision about database. The requirment is that one database table has an AUTO_INCREMENT PRIMARY KEY field called id. By default, each row is shown to user (in web) sorted ascendenting by id. For example, if there are 4 records in the table. The UI will show rows in sequence of 0, 1, 2, 3.

Now, there is requirement that user can drag & drop row in UI to change sequence. Say, user drag rom 3 and drop it befow 0. So, the display sequence turns to be 3, 0, 1, 2. This sequence should be persistent into database.

I'm wondering how to design database table to make this persistent and scalable. My first thought is that each row has a "sequence" field indicating the display sequence. By default, the value should be same as id. When selecting data from database for display, the rows are sorted ascending on sequence instead of id.

If sequence is changed, then it is updated to new value. The result is that it may involves a lot of changes in other rows. Taking example above, originally the table is like this:

|id   | sequence |
|0    | 0        |
|1    | 1        |
|2    | 2        |
|3    | 3        |

Now, after drag row with id 3 to first. Its sequence is updated to 0. At the same time, row with id 0, 1, 2 should also be updated.

|id   | sequence |
|0    | 1        |
|1    | 2        |
|2    | 3        |
|3    | 0        |

I'm afraid this approach will make re-sequence cost a lot resource and not scalable. So, I suppose the sequence can be intiialized by multiplying id with K(say, 10). This leaves gaps between sequence value for insertion. However, the gap can still consumed up if K+1 rows are moved to this gap.

|id   | sequence |
|0    | 0        |
|1    | 10       |
|2    | 20       |
|3    | 30       |

This seems a common problem to database design. Anybody has better idea to achive this?

Answer 1

The obvious answer to me is to use the last solution you mentioned but with decimals (floats).

So you start with, say: {0.1, 0.2, 0.3, 0.4, 0.5}. If you move the last item to between 0.2 and 0.3 it becomes 0.25. If you move it to the top it becomes 0.05. Each time you simply take the mid-point of the two numbers on either side. In other words, the average of the previous/next items.

Another similar solution is to use characters, then sort by strings alphabetically. Starting with {1, 2, 3, 4, 5}, if you move the 5 between 2 and 3 you'd use 25. If you do a string sort of the list you keep the right order: {1, 2, 25, 3, 4}.

The only problem I can think of with these methods is that eventually, you will hit the limit of floating point precision, i.e. trying to find a number between 0.0078125 and 0.0078124. A few ways to solve this:

• Run a script every so often that runs through every item and reorders them to {0.1, 0.2, 0.3, ...}.
• Don't use two decimal places when you can use one. Between 0.2 and 0.25 you could use 0.23 instead of the calculated 0.225.
• Re-sequence locally, not globally. If you have {0.2, 0.3, 0.6} and want to insert after 0.2, you could set the second one to 0.4 and insert the new item at 0.3.

Answer 2

The ID and Sequence/SortOrder are separate and should not depend on each other at all.

for a move-up/move-down feature: You can swapping Sequence/SortOrder Values

or

For a drag and drop feature:

1) Establish the new Sequence/OrderNumber for the selected record.

2) Get the selected records current sequence, then Update the selected record with the new number.

3) a) If the New Sequence number is below the current sequence number increment all the sequence numbers for the records that have a sequence number >= the new sequence number (exlcuding the selected one)

b) if the New sequence number is above the current sequence number, decrement all the sequence numbers below the new selected one and above the current one.

Hope this makes sense and I have though it out the right way (below is the actual implementation).

I have implemented this in a single SQL statement that has some small amount of logic, not for the purists, but its works well.

Here is an example (OP: you will want to change the GUID IDs to INTs):

CREATE PROCEDURE [proc_UpdateCountryRowOrder]
    @ID UNIQUEIDENTIFIER,
    @NewPosition INT
AS

SET NOCOUNT ON

DECLARE @CurrentPosition INT
DECLARE @MaximumPosition INT

IF (@NewPosition < 1) SET @NewPosition = 1

SELECT @CurrentPosition = [Countries].[Order]
FROM [Countries]
WHERE [Countries].[ID] = @ID

SELECT @MaximumPosition = MAX([Countries].[Order])
FROM [Countries]

IF (@NewPosition > @MaximumPosition) SET @NewPosition = @MaximumPosition

IF (@NewPosition <> @CurrentPosition)
BEGIN
    IF (@NewPosition < @CurrentPosition)
    BEGIN
        BEGIN TRAN

        UPDATE [Countries]
        SET [Countries].[Order] = [Countries].[Order] + 1
        WHERE [Countries].[Order] >= @NewPosition
        AND [Countries].[Order] < @CurrentPosition

        UPDATE [Countries]
        SET [Countries].[Order] = @NewPosition
        WHERE ID = @ID

        COMMIT TRAN
    END
    ELSE
    BEGIN
        BEGIN TRAN

        UPDATE [Countries]
        SET [Countries].[Order] = [Countries].[Order] - 1
        WHERE [Countries].[Order] <= @NewPosition
        AND [Countries].[Order] > @CurrentPosition

        UPDATE [Countries]
        SET [Countries].[Order] = @NewPosition
        WHERE ID = @ID

        COMMIT TRAN
    END
END
GO