Shifting records in SQL Database while sorting with algorithm

Question

I have a table in a SQL Server database, which holds information of some images, and the relevant gallery of them. The columns are like:

ImageId, GalleryId, Order

I have a unique key on GalleryId-Order columns, that is, each image should have a unique order in its gallery.

A business requirement is to change the place (order) of an image, inside the gallery. For example, image at the order of 16, might be replaced at the new order 7. However, all the images should shift, if necessary, to provide space for this sorting operation. In this example, images with the order 7, 8, 9, ..., 15 should shift forward one level, so that the place 7 would become empty for the mentioned image.

I've written a procedure for this:

create procedure MoveImage(@imageId int, @newOrder int)
as
begin
    -- Finding the related gallery
    declare @galleryId int;
    select @galleryId = GalleryId
    from Images
    where ImageId = @imageId 

    -- Finding the count of images inside this gallery
    declare @mediaCount int;
    select @mediaCount = COUNT(ImageId)
    from Images
    where GalleryId = @galleryId

    -- Finding the current order of the image
    declare @currentOrder int;
    select @currentOrder = [Order]
    from Images
    where ImageId = @imageId

    -- Temporary shifting the current media to one order above all, to bypass the 'Each Media Should Have a Unique Order in its Gallery' unique index
    update Images
    set [Order] = @mediaCount + 1
    where ImageId = @imageId

    -- Shifting all media of the gallery between the current order and the new order, one order forward, or backward
    if @newOrder < @currentOrder
    begin
        update Images  
        set [Order] = [Order] + 1
        where GalleryId = @galleryId and [Order] >= @newOrder and [Order] <= @currentOrder
    end
    else
    begin
        update Images  
        set [Order] = [Order] - 1
        where GalleryId = @galleryId and [Order] <= @newOrder and [Order] >= @currentOrder
    end

    -- Inserting the image at the specified order
    print @newOrder
    update Images
    set [Order] = @newOrder
    where ImageId = @imageId
end
go

It works, just fine (at least as much as I've tested it). However, I don't feel Okay with this procedure, I think it might become easier and more effective. Can anyone improve this T-SQL code?

PS: parameters are checked before being passed to this procedure, so presume that there is nothing wrong with parameters, like negative @newOrder, etc.

Answer 1

There is a much, much, much easier way to do this. You can use real values for order, so when you want to move the row from position 16 to position 7 you give it an order value which is the average between the order values of rows 6 and 7.

The precision of real numbers is huge, and I presume that the re-orderings of images in your database will be happening at human reaction speeds, so you probably won't run into precision problems during the remainder of the expected lifetime of the universe. But if you are really insecure about the possibility of precision problems, you can rectify your table every once in a while, by reading the rows sorted by their order, and writing them into a new table, re-assigning the order values by copying them from an integer identity field. Then you delete the old table and rename the new table to the old name.

Answer 2

I believe there are a few significant suggestions which are currently missing from answers so far:

1. You need to be using a transaction for this... if the data end up failing part-way through your procedure you will have corrupt data.
2. you can actually do the whole thing in a single update, with no messing around with temporary ID's, etc. (Assuming auto-commit, then this will not need a transaction)
3. seriously, who had the bright idea of calling the column Order.... should be shot.

If you want to perform the update as a single operation you can have the following procedure:

create procedure MoveImage(@imageId int, @newOrder int)
as
    begin
        -- plan your transaction logic here - with auto-commit you may still
            -- want to keep a read-lock on the rows affected......

        declare @movesrc as int
        declare @movetgt as int
        declare @shift as int

        set @movesrc = (select [Order] from Images where ImageId  = @imageId)
        set @movetgt = @newOrder
        set @shift = sign(@movesrc - @movetgt)

        update Images
        set [Order] = case [Order]
                      when @movesrc then @movetgt
                      else [Order] + @shift
                  end
        where (@movesrc > @movetgt and [Order] between @movetgt and @movesrc)
           or (@movesrc < @movetgt and [Order] between @movesrc and @movetgt)

        select * from Images order by [Order]

    end
;

I have built this up in the sqlfiddle here so you can see it working.

Answer 3

Little merging, since you have an index on GalleryId, [Order]:

create procedure MoveImage(@imageId int, @newOrder int)
as
begin
    declare @mediaCount int;
    declare @galleryId int;
    declare @currentOrder int;

    -- Finding the related gallery
    -- Finding the count of images inside this gallery
    -- Finding the current order of the image
    select  TOP 1
        @galleryId = i1.GalleryId, 
        @mediaCount = COUNT(i2.ImageId),
        @currentOrder = i1.[Order]
    from Images i1
    JOIN Images i2
      ON i1.GalleryId = i2.GalleryId
    where i1.ImageId = @imageId 
    GROUP BY i1.GalleryId, i1.[Order]

    -- Temporary shifting the current media to one order above all, to bypass the 'Each Media Should Have a Unique Order in its Gallery' unique index
    update Images
    set [Order] = @mediaCount + 1
    where ImageId = @imageId

    -- Shifting all media of the gallery between the current order and the new order, one order forward, or backward
    if @newOrder < @currentOrder
    begin
        update Images  
        set [Order] = [Order] + 1
        where GalleryId = @galleryId and [Order] >= @newOrder and [Order] <= @currentOrder
    end
    else
    begin
        update Images  
        set [Order] = [Order] - 1
        where GalleryId = @galleryId and [Order] <= @newOrder and [Order] >= @currentOrder
    end

    -- Inserting the image at the specified order
    print @newOrder
    update Images
    set [Order] = @newOrder
    where ImageId = @imageId
end
go

Answer 4

I would consider changing the structure of your table to use a self-referencing foreign key that refers to the previous item.

This makes it trivial to change the position of an item within the sequence, or to insert/remove items.

In order to query the items in the correct order, you would need to use a recursive Common Table Expression.

Below is an example table structure along with a recursive CTE:

create table #Data
(
    DataID int not null primary key,
    Value varchar(50) not null,
    ParentDataID int references #Data (DataID) -- optionally put a unique constraint on this column in order to enforce only one child record
)

-- sorted order is 1, 4, 7, 9, 2, 5, 3, 8, 6
insert into #Data values
    (1, 'One', null),
    (2, 'Two', 9),
    (3, 'Three', 5),
    (4, 'Four', 1),
    (5, 'Five', 2),
    (6, 'Six', 8),
    (7, 'Seven', 4),
    (8, 'Eight', 3),
    (9, 'Nine', 7)
    ,(101, 'One Hundred One', null),
    (102, 'One Hundred Two', 109),
    (103, 'One Hundred Three', 105),
    (104, 'One Hundred Four', 101),
    (105, 'One Hundred Five', 102),
    (106, 'One Hundred Six', 108),
    (107, 'One Hundred Seven', 104),
    (108, 'One Hundred Eight', 103),
    (109, 'One Hundred Nine', 107)

;


with SortedData (DataID, Value, RootID, OrderNumber) as
(
    select
        DataID,
        Value,
        DataID,
        1
    from #Data
    where
        ParentDataID is null
        or ParentDataID = DataID

    union all

    select
        #Data.DataID,
        #Data.Value,
        SortedData.RootID,
        SortedData.OrderNumber + 1
    from #Data
    inner join SortedData on
        SortedData.DataID = #Data.ParentDataID
)
select *
from SortedData
order by RootID, OrderNumber

(EDIT: I've rearranged the content of my answer. Code examples that used to be here are now at the bottom, because I feel that the easier approach is to use the trigger that I've written, shown below)

The code below is for an "instead of insert, update, delete" trigger on the table that will automatically perform the necessary "shifting" operations when records are inserted/updated/deleted.

Note that I've changed the name of the table in my example from #Data to SortableData, because triggers cannot be added to temporary tables.

EDIT: The original trigger code was unable to handle contiguous rows being added/moved/removed from the sequence. I've now revised the trigger code to handle those scenarios

create trigger trig_SortableData on SortableData instead of insert, update, delete as begin

-- first, store a list of records that are to come after the records that are being added/moved
declare @ChildData table
(
    ChildDataID int,
    ParentDataID int
)
;

with DeletedSorted (DataID, ParentDataID, RootDataID) as
(
    select
        DataID,
        ParentDataID,
        ParentDataID
    from Deleted
    where
        not exists (
            select 1
            from Deleted d
            where
                d.DataID = Deleted.ParentDataID
        )

    union all

    select
        Deleted.DataID,
        Deleted.ParentDataID,
        DeletedSorted.RootDataID
    from Deleted
    inner join DeletedSorted on
        DeletedSorted.DataID = Deleted.ParentDataID
),
InsertedSorted (DataID, ParentDataID, LeafDataID) as
(
    select
        DataID,
        ParentDataID,
        DataID
    from Inserted
    where
        not exists (
            select 1
            from Inserted i
            where
                i.ParentDataID = Inserted.DataID
        )

    union all

    select
        Inserted.DataID,
        Inserted.ParentDataID,
        InsertedSorted.LeafDataID
    from Inserted
    inner join InsertedSorted on
        Inserted.DataID = InsertedSorted.ParentDataID
)
-- insert those records into the table variable along with the last DataID of the records being added/moved
insert into @ChildData
select
    SortableData.DataID,
    isnull(DeletedSorted.RootDataID, InsertedSorted.LeafDataID)
from SortableData
inner join InsertedSorted on
    InsertedSorted.ParentDataID = SortableData.ParentDataID
left outer join DeletedSorted on
    DeletedSorted.DataID = SortableData.ParentDataID
where
    not exists (
        select 1
        from Inserted
        where
            Inserted.DataID = SortableData.DataID
    )

-- and disengage those records from their current parent
-- Performing this update may be necessary if there is a unique constraint on ParentDataID
update d set
    d.ParentDataID = null
from SortableData d
inner join @ChildData c on
    c.ChildDataID = d.DataID


-- next, update any records that are being moved/deleted; put them after their new parent record
update d set
    d.ParentDataID = Inserted.ParentDataID
from SortableData d
inner join Deleted on
    Deleted.DataID = d.DataID
left outer join Inserted on
    Inserted.DataID = d.DataID
;

with DeletedSorted (DataID, ParentDataID, RootDataID) as
(
    select
        DataID,
        ParentDataID,
        ParentDataID
    from Deleted
    where
        not exists (
            select 1
            from Deleted d
            where
                d.DataID = Deleted.ParentDataID
        )

    union all

    select
        Deleted.DataID,
        Deleted.ParentDataID,
        DeletedSorted.RootDataID
    from Deleted
    inner join DeletedSorted on
        DeletedSorted.DataID = Deleted.ParentDataID
),
InsertedSorted (DataID, ParentDataID, LeafDataID) as
(
    select
        DataID,
        ParentDataID,
        DataID
    from Inserted
    where
        not exists (
            select 1
            from Inserted i
            where
                i.ParentDataID = Inserted.DataID
        )

    union all

    select
        Inserted.DataID,
        Inserted.ParentDataID,
        InsertedSorted.LeafDataID
    from Inserted
    inner join InsertedSorted on
        Inserted.DataID = InsertedSorted.ParentDataID
)
-- and revise those records that used to come after those records being moved in order to close the gap
update d set
    d.ParentDataID = isnull(InsertedSorted.LeafDataID, DeletedSorted.RootDataID)
from SortableData d
inner join DeletedSorted on
    DeletedSorted.DataID = d.ParentDataID
left outer join InsertedSorted on
    InsertedSorted.ParentDataID = DeletedSorted.RootDataID
where
    not exists (
        select 1
        from Deleted
        where
            Deleted.DataID = d.DataID
    )

-- and then actually remove those records that are being deleted
delete from SortableData
where
    exists (
        select 1
        from Deleted
        where
            Deleted.DataID = SortableData.DataID
    )
    and not exists (
        select 1
        from Inserted
        where
            Inserted.DataID = SortableData.DataID
    )


-- finally, insert any new records
insert into SortableData
select *
from Inserted
where
    not exists (
        select 1
        from Deleted
        where
            Deleted.DataID = Inserted.DataID
    )

-- and re-attach records to come after the added/moved records
update d set
    d.ParentDataID = c.ParentDataID
from SortableData d
inner join @ChildData c on
    c.ChildDataID = d.DataID

end

I've tested this trigger out with the following commands:

insert into SortableData values (10, 'Ten', 4)
update SortableData set ParentDataID = 1 where DataID = 5
delete from SortableData where DataID = 8
delete from SortableData where DataID = 6
insert into SortableData values (6, 'Six', 3)

I've also tested the following commands to add/move/remove multiple contiguous records in the sequence:

insert into SortableData values (10, 'Ten', 4), (11, 'Eleven', 10), (12, 'Twelve', 11)

delete from SortableData where DataID in (5,3)

update d set
    d.ParentDataID = u.ParentDataID
from SortableData d
inner join (
              select 9 as DataID,   1 as ParentDataID
    union all select 2,           8
    union all select 8,           9
) u on
    u.DataID = d.DataID

Also, below is a line to add a unique constraint on the ParentDataID column; this ensures that the non-null values are unique, but allows multiple nulls. This allows you to store multiple sequences in the table; each record with a null ParentDataID field is a root.

create unique index uq_SortableData_ParentDataID on SortableData (ParentDataID) where ParentDataID is not null

---

The code examples below are from previous versions of my answer. These demonstrate how to insert, move, and remove a single record in a sequence. However, I would prefer to use the trigger shown above because it makes these complex operations unnecessary.

Below is some code that demonstrates inserting a new record into an arbitrary position. Similar code would be needed in order to change the position of an existing record. Alternatively, the code shown below could possibly be modified and implemented as an "instead of insert" trigger.

-- @DataID, @Value, and @ParentDataID should be parameters of the insert command
-- They are defined here as variables for the sake of testing
declare @DataID int
declare @Value varchar(50)
declare @ParentDataID int

-- These values will insert a new record, "Ten", after the record "Four"
set @DataID = 10
set @Value = 'Ten'
set @ParentDataID = 4

-- This code assumes that there is a unique constraint on ParentDataID
declare @ChildDataID int

-- first, update the current record that comes after "Four"
-- set ParentDataID to null so that we can put the new record in its place (the unique constraint makes this necessary)
-- also capture the DataID of this record in the @ChildDataID variable
-- The unique constraint on ParentDataID ensures that this update statement will only affect one record.
-- If there is not a unique constraint on ParentDataID, then this approach could corrupt the data.
update #Data set
    @ChildDataID = DataID,
    ParentDataID = null
where
    ParentDataID = @ParentDataID

-- insert the new record.
insert into #Data values (@DataID, @Value, @ParentDataID)

-- now update the previous record again; set the ParentDataID to the DataID of the newly inserted record
-- this ensures that the record that used to come after "Four" will now come after the newly inserted record
update #Data set
    ParentDataID = @DataID
where
    DataID = @ChildDataID

Below is an example of moving a record to a different position within the sequence. In this case, it is moving record "Five" to come after record "One":

-- Move record "Five" to come after "One"

-- @DataID and @ParentDataID should be parameters of the update command
-- They are defined here as variables for the sake of testing
declare @DataID int
declare @ParentDataID int

-- These values will move the record "Five" to come after the record "One"
set @DataID = 5
set @ParentDataID = 1

-- This code assumes that there is a unique constraint on ParentDataID
declare @ChildDataID int

-- first, update the current record that comes after "One"
-- set ParentDataID to null so that we can put the new record in its place (the unique constraint makes this necessary)
-- also capture the DataID of this record in the @ChildDataID variable
-- The unique constraint on ParentDataID ensures that this update statement will only affect one record.
-- If there is not a unique constraint on ParentDataID, then this approach could corrupt the data.
update #Data set
    @ChildDataID = DataID,
    ParentDataID = null
where
    ParentDataID = @ParentDataID

declare @OriginalParentDataID int

update #Data set
    @OriginalParentDataID = ParentDataID,
    ParentDataID = @ParentDataID
where
    DataID = @DataID

-- update the record that comes after the record being moved
-- this record must now come after the record after which the record being moved originally came.
update #Data set
    ParentDataID = @OriginalParentDataID
where
    ParentDataID = @DataID

update #Data set
    ParentDataID = @DataID
where
    DataID = @ChildDataID

Finally, this last code example demonstrates removing a record from the sequence. In this case, it is removing record "Eight":

-- Remove record "Eight"

-- @DataID should be a parameter of the delete command
-- It is defined here as a variable for the sake of testing
declare @DataID int

-- This value will remove the record "Eight"
set @DataID = 8

declare @OriginalParentDataID int

update #Data set
    @OriginalParentDataID = ParentDataID,
    ParentDataID = null
where
    DataID = @DataID

-- update the record that comes after the record being moved
-- this record must now come after the record after which the record being moved originally came.
update #Data set
    ParentDataID = @OriginalParentDataID
where
    ParentDataID = @DataID

delete from #Data where DataID = @DataID