User-Defined ORDERing in SQL
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').