I have a fairly simple data structure like this:

create table project (id int auto increment primary key, name text);

create table item (id int auto increment primary key, name text,
    project_id int not null, 
    project_sort_index int not null,
    sort_index int not null,
    foreign key fk_project(project_id) references project(id));

A project can have many items. Items have two different fields for maintaining sort order, project_sort_index and sort_index.

These sort order fields apply in the following way. When I view all items belonging to a project, I need a sort order specific to each project for the items. When I view all items globally, I need a sort order for them globally.

I have a couple of questions as to how best to maintain and modify sort order for these items. Lets say that I have moved an item at index 4 to index 2. How do I propagate that change to my database efficiently?

For example, how do I now update all index numbers >= 2 to move everything down, yet close the gap left in place 4? Is there a better way of sorting lists in SQL?

  • What do these sort indices represent? Are you letting the user manually define an explicit ordering? – Dan Pichelman Apr 8 '14 at 19:41
  • Yes, it's a user ordered and reordered list. – Naftuli Kay Apr 8 '14 at 19:43
  • Are project_sort_index and sort_index completly independent from each other, and both manually defined? Or are there any rules / dependencies / constraints between the rwo? – Doc Brown Apr 8 '14 at 19:52
  • No constraints between the two; one contains sort info for one view, one contains sort info for a different view. – Naftuli Kay Apr 8 '14 at 19:53

For a small number of items (lets say <50,000) the most effective and simple solution is probably to load all items into memory, let the user reorder them the way he/she likes, regenerate the indexes and afterwards update all changed records in a single transaction. If you expect only a fraction of elements to be changed this way, you should keep track of the changed records and update only those. Otherwise, just update them all.

If you need a solution which avoids the loading of all records into memory, and allows "small movements" to be applied very effectively, you could first assign index numbers with "gaps" like 10, 20, 30, ... to your records. When you have to move item number 4 (with number 40) to the 2nd position, you try to assign the median value from the first and the new third element (which means in this example 15) to item number 4. This will allow a lot of small reorderings, until you reach the point where there is no "free space" any more between two consecutive numbers. That's the point where you renumber all items in steps of 10 again. This strategy could be further improved, for example, by "partial renumberings", or by using floats (thanks to Dan Pichelman's comment), and it will make the need of changing many records a (hopefully) seldom event. But to know if this works for your case, you should have a notion about the kind of reorderings you expect.

  • Would using floats be a viable alternative? You'd eliminate the need to renumber. – Dan Pichelman Apr 8 '14 at 20:24

If you move an item then only those items which lie between the old and new positions, inclusive, need to receive new sort_index values. If an item moves from position 4 to position 2, only 2, 3 & 4 are affected; 1 is still 1, 5 is still 5 etc.

declare @id int;
declare @old int = 4;  -- the value in the original question
declare @new int = 2;
declare @lower int;
declare @upper int;

select @lower = MIN(c1)
from (values (@old),(@new)) as t1(c1);

select @upper = MAX(c1)
from (values (@old),(@new)) as t1(c1);

update #items
set si = si + SIGN(@old - @new)
where si between @lower and @upper;

update #items
set si = @new
where id = @id;

I've tested this against SQL Server 2008R2. Your RDBMS's syntax may vary. The second UPDATE could be eliminated with more clever setting of @upper or @lower, depending on the direction of the move. Given that any real system is likely to have a unique constraint on the sort_index, and hence an index, the update is likely to be quite efficient. The number of rows modified would depend on how far the item's new position is from its previous one. I would suggest that in any practicable UI this would be quite modest. You know your data best, however.

As an aside, your table design is not normalised. If an item were in 50 projects it would have to have 50 rows in your item table, each with different project_sort_index values but all with the same sort_index. A better design would be

create table project (
    id int auto increment primary key, 
    name text);

create table item (
    id int auto increment primary key, 
    name text,
    sort_index int not null);

create table project_item (
    item_id int not null,
    project_id int not null, 
    project_sort_index int not null);

Another solution would be to hold your items as a doubly-linked list

create table item (
    id int auto increment primary key, 
    name text,
    preceeding_item_id int,    -- have to be NULLable for first & last items.
    succeeding_item_id int);

A move would then update at most 5 rows - the neighbours from the old location, those in the new, and the item itself. The application would retrieve all rows and handle the on-screen sequencing.

  • How then do I sort the values in my select? – Naftuli Kay Apr 9 '14 at 15:53
  • You don't - you let the application handle that. First it finds the one row in the result set with NULL in preceeding_item_id, then it follows the links until it comes to the item with NULL in succeeding_item_id, writing to the screen objects as it goes. Our DB servers are about 10x expensive as the app servers. Any work we can offload to the app server is a win. – Michael Green Apr 10 '14 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.