Shifting records in SQL Database while sorting with algorithm

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.

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.

• +1 for the real numbers. It's worth to mention it that this way it's enough to update only one record. (On the other hand, table renaming is bad - I suppose it doesn't support transactionts, nor concurrent orderings/access.) – palacsint Jan 9 '12 at 23:05
• @palacsint Yes, you are right, I really did not need to mention that. The renumbering could be achieved in-place anyway, without copying to a new table. – Mike Nakis Jan 9 '12 at 23:09

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.

• such a nice answer. Thank you for mentioning missing points. But, what's wrong with the word Order? Because I'm the culprit ;). – Saeed Neamati Jan 9 '14 at 11:13
• Since ORDER is a reserved word in all databases (as part of ORDER BY) it will always have to be escaped. Escaping values all over the place makes the query/code very hard to read. It does not add any value by keeping it Order when a different name, like ImageOrder will be easily readable, and just as useful. Even IOrder or Position would be better. Choosing names is what programmers do, and choosing names that make things easy is what better programmers do. – rolfl Jan 9 '14 at 11:19

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


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