Re: Storing an ordered list

On 7/25/06, Michael Artz <mlartz(at)gmail(dot)com> wrote:
>
> 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?

==================================================================
Aaron Bono
Aranya Software Technologies, Inc.
http://www.aranya.com
==================================================================