Re: Storing an ordered list - Mailing list pgsql-sql

What is the best way to store and ordered list that can be updated
OLTP-style?  A simplified problem is that I have an event, and the
event has an ordered list of predicates and I need to preserve the
order of the predicates.  All of the data is entered via a web
application, and I would like to support the new flashy ajax
drag-droppy thingies, meaning that there could be a significant amount
of updates if the user is dragging things all over the place.

I figure that one choice is to explicitly code the order as an integer
column in the predicate table which has the advantage of being very
easy and fast to query/order but *very* slow to reorder as all of the
predicates need to be updated.  This would seem to be a postgres/MVCC
weak spot as well.  Example:

create table event (event_id integer);
create table predicate (event_id integer not null references
event(event_id), name varchar, order integer);
insert into event (event_id) values (1);
insert into predicate (1, 'first event', 1);
insert into predicate (1, 'second predicate', 2);
select * from predicate p where p.event_id = 1 order by p.order;

I'm also thinking about a linked list, i.e.

create table event (event_id integer);
create table predicate (predicate_id integer, event_id integer not
null references event(event_id), name varchar, next_predicate integer
references predicate (predicate_id));
insert into predicate (101, 1, 'second predicate', NULL);
insert into predicate (102, 1, 'first predicate', 101);

The downside is that I'm not quite sure how to efficiently query the
linked list.  Any suggestions?

Are there any known best practices for storing ordered lists in
relational databases?  Are there any tricks that I can use with
postgres?

Even the linked list will require a lot of updates if there are is a lot of reshuffling - perhaps less though in certain circumstances, especially if the list is large and there is very little reshuffling.

If you use the linked list, remember this: to reduce the updates you are going to need more code in the application as it will have to keep track of what to update and what to not update.  It will also be more difficult to order the items using SQL so your application may have to take on that burden.  As a result, your application will become more complicated and writing reports that use the ordering will become difficult.

Another thing to think about with a linked list:  What if two people are reordering the items at the same time - they load the items at the same time, then reorder at the same time (with their own separate cache of the data) and finally save.  If you update everything, the last man to save wins but if you only update only what they change, you could end up with a mess:

Example:
    Start with:
    1 -> 2 -> 3 -> 4 -> 5
   
    Person 1 reorders to:
    1 -> 5 -> 2 -> 3 -> 4 (only update 1 -> 5, 5 -> 2 and 4 -> null)
   
    Person 2 reorders to:
    1 -> 2 -> 5 -> 3 -> 4 (only update 2 -> 5, 5 -> 3 and 4 -> null)
   
    If they then both save (assume person 1 saves and then person 2 saves) you get:
    1 -> 5
    2 -> 5
    This is going to be a big problem.

When I need something like this I go with your first approach, a simple order field.  Unless the user is reordering a small number of items in a very large list and doing it frequently, is there really a need to worry about the number of updates?  Are you worrying about a performance problem you will never have?