Received: from localhost.localdomain (postgresql.org [64.49.215.8]) by localhost (Postfix) with ESMTP id 6BB0F475BE6 for ; Mon, 6 May 2002 21:02:40 -0400 (EDT) Received: from fepZ.post.tele.dk (fepz.post.tele.dk [195.41.46.133]) by postgresql.org (Postfix) with ESMTP id A478E47592E for ; Mon, 6 May 2002 21:02:14 -0400 (EDT) Received: from localhost.localdomain ([80.196.138.103]) by fepZ.post.tele.dk (InterMail vM.4.01.03.23 201-229-121-123-20010418) with ESMTP id <20020507010216.BUOV26021.fepZ.post.tele.dk@localhost.localdomain>; Tue, 7 May 2002 03:02:16 +0200 Subject: Optimizing the implementation of an optimized tree From: Christian Rishoej To: pgsql-sql@postgresql.org Cc: Anders Johannsen Content-Type: multipart/mixed; boundary="=-oiqsmfZJKq4FZG+O6iQV" X-Mailer: Ximian Evolution 1.0.3 Date: 07 May 2002 03:02:16 +0200 Message-Id: <1020733336.892.79.camel@penelope.dyndns.dk> Mime-Version: 1.0 X-Archive-Number: 200205/40 X-Sequence-Number: 7676 --=-oiqsmfZJKq4FZG+O6iQV Content-Type: text/plain Content-Transfer-Encoding: 7bit Hi, Recently I needed to store a hiearchy of pages on a website in Postgres in a way that would allow for fast extraction of parts of the tree for menu generation and "path" specification (which nodes in the tree make up the path from the root to my position?). This can be accomplished by letting each node in the tree have an l and r value with values determined by traversing the edge of the tree and assigning the value of integer that is incremented at each node visit to l and doing the same thing for r, this time traversing the edge of the tree backwards. The tree then becomes: CREATE TABLE tree ( id serial PRIMARY KEY, parent int REFERENCES tree, l int DEFAULT NULL, r int DEFAULT NULL, ); The parent id strictly not needed, but I chose to include it for convenience. I can easily extract a complete branch like this: SELECT treeNode.id FROM tree treeNode, tree treeParent WHERE treeNode.l BETWEEN treeParent.l AND treeParent.r AND treeParent.id = $1 ORDER BY treeNode.l And the "path" from the root to a particular node like this: SELECT treeNode.id FROM tree treeNode, tree currentNode WHERE currentNode.r BETWEEN treeNode.l AND treeNode.r AND currentNode.id = $1 ORDER BY treeNode.l; Now, in order to avoid having to maintain the values of l and r for each node when the tree is modified I created triggers in PL/PGSQL that handle INSERTs of new nodes into the tree, DELETEs of existing nodes and UPDATEs of a node's position in the tree (i.e. the parant field). The implementation is included as an attachment. I am very interested in comments on the implementation - especially hints on possible optimizations. It seems to me that the PL/PGSQL-definition of each function is parsed at each call. Is this true? Is it possible to avoid this? It is my understanding that Postgres does not yet support triggers that fire on the update of a paricular column. Therefore I have a check in the UPDATE trigger that checks if the parent-field was modified. Is there any was to do this in a nicer manner? Regards, Christian --=-oiqsmfZJKq4FZG+O6iQV Content-Description: Content-Disposition: inline; filename=triggers.sql Content-Transfer-Encoding: quoted-printable Content-Type: text/x-sql; charset=ANSI_X3.4-1968 CREATE TABLE tree ( id serial PRIMARY KEY, parent int REFERENCES tree, l int DEFAULT NULL, r int DEFAULT NULL,=20 ); -- Are these a good idea? CREATE INDEX tree_l_idx ON tree (l); CREATE INDEX tree_r_idx ON tree (r); CREATE OR REPLACE FUNCTION handle_tree_insert() RETURNS opaque AS ' DECLARE parentR INTEGER; BEGIN=20 IF NEW.l ISNULL THEN parentR :=3D ( SELECT r FROM tree WHERE id =3D NEW.parent ); UPDATE tree SET l=3Dl+2 WHERE l >=3D parentR; UPDATE tree SET r=3Dr+2 WHERE r >=3D parentR; NEW.l :=3D parentR; NEW.r :=3D parentR + 1; END IF; RETURN NEW; END; ' LANGUAGE PLPGSQL;=09 CREATE TRIGGER on_tree_insert BEFORE INSERT ON tree=20 FOR EACH ROW EXECUTE PROCEDURE handle_tree_insert(); =20=20=20=20 CREATE OR REPLACE FUNCTION handle_tree_delete() RETURNS opaque AS ' DECLARE decr INTEGER; BEGIN=20 -- RAISE NOTICE ''Gets here, ID %'', OLD.id; IF NOT OLD.l ISNULL THEN decr :=3D (((OLD.r - OLD.l - 1) / 2 ) + 1) * 2; -- RAISE NOTICE ''...and executes stuff (decrementing with %)'', decr; UPDATE tree SET parent =3D NULL, l =3D NULL, r =3D NULL WHERE l > OLD.l = AND r < OLD.r; DELETE FROM tree WHERE parent ISNULL AND l ISNULL AND r ISNULL; UPDATE tree SET l =3D l - decr WHERE l > OLD.l; UPDATE tree SET r =3D r - decr WHERE r > OLD.r; END IF; RETURN OLD; END; ' LANGUAGE PLPGSQL;=09 CREATE TRIGGER on_tree_delete AFTER DELETE ON tree=20 FOR EACH ROW EXECUTE PROCEDURE handle_tree_delete(); CREATE OR REPLACE FUNCTION handle_tree_update() RETURNS opaque AS ' DECLARE parentR INTEGER; span INTEGER; dist INTEGER; BEGIN=20 IF (NOT OLD.parent ISNULL) AND (NOT NEW.parent ISNULL) AND (OLD.parent <>= NEW.parent) THEN span :=3D OLD.r - OLD.l + 1; -- Get the R value of the new parent parentR :=3D ( SELECT r FROM tree WHERE id =3D NEW.parent ); -- Determine the distance dist =3D parentR - OLD.l; -- Make the gab UPDATE tree SET l =3D l + span WHERE l >=3D parentR; UPDATE tree SET r =3D r + span WHERE r >=3D parentR; =09 -- Move our branch to the newly created gab -- Decrement nodes after the old position to close the old gab -- If dist is < 0 then our own branch was moved steps - this must= be taken into consideration IF (dist > 0)=20 THEN UPDATE tree SET l =3D l + (dist), r =3D r + (dist) WHERE l >=3D OL= D.l AND r <=3D OLD.r; UPDATE tree SET l =3D l - span WHERE l >=3D OLD.l;=20 UPDATE tree SET r =3D r - span WHERE r >=3D OLD.r; ELSE=20 UPDATE tree SET l =3D l + (dist - span), r =3D r + (dist - span) WHERE = l >=3D (OLD.l + span) AND r <=3D (OLD.r + span); UPDATE tree SET l =3D l - span WHERE l >=3D (OLD.l + span);=20 UPDATE tree SET r =3D r - span WHERE r >=3D (OLD.r + span); END IF; END IF; RETURN NULL; END; ' LANGUAGE PLPGSQL;=09 CREATE TRIGGER on_tree_update AFTER UPDATE ON tree=20 FOR EACH ROW EXECUTE PROCEDURE handle_tree_update(); --=-oiqsmfZJKq4FZG+O6iQV--