DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com;
	h=received:message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition;
	b=LMyD65BO8trq/ls5O4nHJJC5UOvcPgejqO46/0Isz8HSapeZfo1gOpnnDPUqQq2sSrw8KVvAO7OxntJ/OH5WXMZZwHvP+eMlojz5cbWnRGGCUITwT2HzmPVnRgz+2Y/+l95Ccn/t8K+ARCXrZTEdcE2COKwXgxsbWoUg6s/mkWM=
Message-ID: <e9c163070607251958x2ef2a315w4204aa2f90e70bbe@mail.gmail.com>
Date: Tue, 25 Jul 2006 22:58:47 -0400
From: "Michael Artz" <mlartz@gmail.com>
To: pgsql-sql@postgresql.org
Subject: Storing an ordered list
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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?

Thanks
-Mike