User-Defined ORDERing in SQL I have just read an interesting blog article regarding User-Defined resultset ordering.


  Some applications, such as todo lists, need to maintain a user-defined
  order of items. The challenge is that the order is arbitrary and can
  change when the user rearranges items


An example table could be like so:

create table items
(
  itemid int primary key,
  itemdata varchar(200),
  ...
  ...
  userorder ??? 
);


With a possible retrieval query of:

select * from items order by userorder asc;


Are there any approaches that I should consider given I'd like to keep updates to a minimum, updates atomic, and retrieval queries as simple and "performant" as possible? 

My initial thought was to use an extra TIMESTAMP column, and only update userorder and the timestamp values for a single row (with the retrieval query using ORDERing by userorder asc, usertimestamp desc), but that fails when you need to move a row in between two other rows that have the same value. 

No specific database in mind, as i use a broad spectrum myself.
Are there any approaches that I should consider given I'd like to keep updates to a minimum, updates atomic, and retrieval queries as simple and "performant" as possible?


I think of this as an esoteric variation of the "True Fractions" approach in that blog post — the advantage being that there is no need to introduce a user-defined type (at least if you are using Postgres).

This works using the natural ordering properties of varbit and mapping a sequence of them onto a binary tree such that it is always possible to generate another varbit value between any two existing adjacent values:

                          _____ 1 ____
                   ______/            \______
              _ 01 _                          11
            _/      \_                    _/      \_
        001            011            101            111
       /   \          /   \          /   \          /   \
    0001   0011    0101   0111    1001   1011    1101    1111





create table foo(id serial primary key, userorder varbit unique);

create function adj(orig varbit, b varbit) returns varbit language sql as $$
  select substring(orig for length(orig)-1)
       ||b
       ||substring(orig from length(orig));
$$;

create function f(l varbit, h varbit) returns varbit language plpgsql as $$

begin
  if l is null and h is null then return B'1'; end if;
  if l is null then return adj(h,B'0'); end if;
  if h is null then return adj(l,B'1'); end if;
  if length(l)&gt;length(h) then return adj(l,B'1'); end if;
  return adj(h,B'0');
end;
$$;






insert into foo(userorder) values(f(null,null));
select * from foo order by userorder;



id | userorder
-: | :--------
 1 | 1        






insert into foo(userorder) values(f(null,B'1'));
select * from foo order by userorder;



id | userorder
-: | :--------
 2 | 01       
 1 | 1        






insert into foo(userorder) values(f(B'01',B'1'));
select * from foo order by userorder;



id | userorder
-: | :--------
 2 | 01       
 3 | 011      
 1 | 1        






insert into foo(userorder)
values(f(B'01',B'011')),(f(B'011',B'1')),(f(B'1',null));

select * from foo order by userorder;



id | userorder
-: | :--------
 2 | 01       
 4 | 0101     
 3 | 011      
 5 | 0111     
 1 | 1        
 6 | 11       



dbfiddle here

If you initially load a lot of ordered rows, you may want to use some other algorithm for generating the initial userorder values as you will hit the worst case for space usage (each row will use one more bit for userorder than the row before). You could step through same-length values for a sufficiently large number of bits (eg for 8 values: B'0001', B'0011', B'0101', B'0111', B'1001', B'1011', B'1101', B'1111').