7

This question already has an answer here:

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.

marked as duplicate by Evan Carroll, Joe Obbish, hot2use, Paul White Mar 22 '18 at 21:24

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • Can ANY order be defined by the user at any time? If so I can't see any way of doing this other than updating every row on every change, due to the sequential nature of the data. – George.Palacios Mar 21 '18 at 15:21
4

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)>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').

2

Intro

Some really old BASIC languages required a Line Numbers for every line of code.

When programming, the line numbers where usually spaced out in multiples of 10. This allowed you to add more code between lines at a later date.

Your items table should follow the same concept.

Basic algorithm

  1. Values for userorder start off as multiples of 10 start with 10 for each userid
  2. Application updates userorder as needed
  3. You renumber that user's userorder using Analytics
  4. Values for 'userorder` remain as multiples of 10.
  5. commit the data changes.

Re-enumeration code

This is basically what I have used:

merge into items a
using (
  select i.itemid
    ,10 * row_number() over (partition by i.userid order by i.userorder)
      as new_userorder
  from items i
  where i.userid=?
) b
on (a.itemid = b.itemid)
when matched then update
  set a.userorder=b.new_userorder
;

I'm assuming this table holds everyone's TODO list and each user is identified by userid.

This example uses ROW_NUMBER() from Oracle. You'll have to substitute it for whatever RDBMS you are using.

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