Thread: celko nested set functions -- tree move

I'm not sure that keying off lft is safe in a multi-user environment.  I
opted to create and use an objid on the tree definition table, since its
identity is static.  I also found that when trees get active, allowing for
tree IDs increased operation speed quite a bit (i actually push this to
two levels--a 'universe id' and then a 'tree id').  Here's my version. 
Clearly not as elegantly written, but nothing's gone awry yet.

--
---------------------------------------------------------------------------
--    Title: trackmyproject_tree_move()
-- Function: moves a tree branch in the hierarchy from one parent to
--           another.
--    parms: srcobj       the branch/object to be moved
--           newparent    the new parent for the object to be moved
--  Returns: zero
--
---------------------------------------------------------------------------
CREATE FUNCTION trackmyproject_tree_move( INT4, INT4 ) RETURNS INT4 AS ' DECLARE   t_srcobj ALIAS FOR $1;   t_newparent
ALIASFOR $2;   srcspan INT4;   srclft INT4;   srcrgt INT4;   srcuid INT4;   srctid INT4;   newparentrgt INT4;
newparentuidINT4;   newparenttid INT4;   moveoffset INT4;   myrec RECORD; BEGIN
 
   -- get src span info (distance between lft and rgt plus one)   SELECT ((rgt - lft) + 1) INTO srcspan FROM
list_objects    WHERE objid_auto=t_srcobj;
 
   LOCK TABLE list_objects;
   -- find out where the new parent currently ends   SELECT rgt, universeid, treeid INTO myrec FROM list_objects
WHEREobjid_auto=t_newparent;
 
   newparentrgt := myrec.rgt;   newparentuid := myrec.universeid;   newparenttid := myrec.treeid;
   -- create the gap at the bottom of the hierarchy for the   -- new parent big enuf for the source object and its tree
 UPDATE list_objects     SET lft = CASE WHEN lft > newparentrgt         THEN lft + srcspan         ELSE lft END,
rgt= CASE WHEN rgt >= newparentrgt         THEN rgt + srcspan         ELSE rgt END     WHERE rgt >= newparentrgt AND
  universeid=newparentuid AND       treeid=newparenttid;
 
   -- move the object tree in to the newly created gap   -- (may seem like a repetative select, but the above UPDATE
--MAY have moved the source object)   SELECT lft, rgt, universeid, treeid INTO myrec FROM list_objects     WHERE
objid_auto=t_srcobj;  srclft := myrec.lft;   srcrgt := myrec.rgt;   srcuid := myrec.universeid;   srctid :=
myrec.treeid;
   -- this works even if we are jumping trees or moving up or down within   -- the same tree   moveoffset := srclft -
newparentrgt;  UPDATE list_objects     SET lft = lft - moveoffset,       rgt = rgt - moveoffset,       universeid =
newparentuid,      treeid = newparenttid     WHERE lft >= srclft AND rgt <= srcrgt AND       universeid=srcuid AND
treeid=srctid;
 
   -- close the gap where the source object was   UPDATE list_objects     SET lft = CASE WHEN lft > srclft         THEN
lft- srcspan         ELSE lft END,       rgt = CASE WHEN rgt > srclft         THEN rgt - srcspan         ELSE rgt END
 WHERE rgt >= srclft AND       universeid=srcuid AND       treeid=srctid;
 
   RETURN 0;

END;
' LANGUAGE 'plpgsql';


> Robert Treat and I came up with a better way to move
> nodes from one branch to another inside of a nested tree:

I think you should take a closer look at Greg's function. It is uses
lfts as parameters in the function mainly just to make the function
implementation independent; I was able to easily adapt it to my schema
which uses unique id's for each object in the tree hierarchy.

After looking your function over, I also have some concerns about moving
children to new parents with lft and rgt smaller than the child, because
the math is different depending on which way your moving in the tree.
It's possible that your use of treeid's and universe id's makes up for
this, though it's a little hard to discern without seeing the schema,
perhaps you can post schema and some test data? 

I'm also curious how many nodes you have in your tree, and at how many
levels. It seems like your function would have performance issues over
large trees since it requires 3 select statements, 3 updates, and a lock
table. Compare this with Greg's function which requires 2 selects and 1
update, with no lock. 

As a final note, you might want to rewrite your select statements like:
SELECT rgt, universeid, treeid  
FROM list_objects
WHERE objid_auto=t_newparent
INTO newparentrgt, newparentuid, newparenttid;

I think it's more readable and probably a little more efficient since
you are doing less variable assignment.

Robert Treat

On Tue, 2002-11-26 at 00:13, Martin Crundall wrote:
> I'm not sure that keying off lft is safe in a multi-user environment.  I
> opted to create and use an objid on the tree definition table, since its
> identity is static.  I also found that when trees get active, allowing for
> tree IDs increased operation speed quite a bit (i actually push this to
> two levels--a 'universe id' and then a 'tree id').  Here's my version. 
> Clearly not as elegantly written, but nothing's gone awry yet.
> 
> --
> ---------------------------------------------------------------------------
> --    Title: trackmyproject_tree_move()
> -- Function: moves a tree branch in the hierarchy from one parent to
> --           another.
> --    parms: srcobj       the branch/object to be moved
> --           newparent    the new parent for the object to be moved
> --  Returns: zero
> --
> ---------------------------------------------------------------------------

Hi Robert;
  The math actually works either way; if it goes negative, the offset is
positive, which is okay.  Your selects are way more elegant.  I guess I
was just raising the point that using a key other than lft (which tends
to move around in an active tree), is probably safer.  The table lock
just keeps the lft and rgt values static while the two updates are
done.  If I combined the two updates, I could probably loose the lock;
I took the conservative route.
  The node list is around 10k, though using the universe id and tree id
to separate trees, I try to keep trees to around 2k or thereabouts so
that tree manip functions remain reasonably fast.  I've found that a
vacuum full analyze is needed at least once a day.  Looking over the
tree, I don't see too many nodes that are indented further than ten
levels, although some are as deep as 20.  I really like Celko's model
for this app; it makes navigation a snap.  Modifying the core functions
to deal with sub-trees, however, was a logic nightmare for my feeble
brain.
  Got it on the INTO clause; tks for the tip.  I know I have work to do
to tighten up the core code in various places.
  The schema's quite large; I'll post it somewhere soon.
  Martin

> I think you should take a closer look at Greg's function. It is uses
> lfts as parameters in the function mainly just to make the function
> implementation independent; I was able to easily adapt it to my schema
> which uses unique id's for each object in the tree hierarchy.
>
> After looking your function over, I also have some concerns about moving
> children to new parents with lft and rgt smaller than the child, because
> the math is different depending on which way your moving in the tree.
> It's possible that your use of treeid's and universe id's makes up for
> this, though it's a little hard to discern without seeing the schema,
> perhaps you can post schema and some test data?
>
> I'm also curious how many nodes you have in your tree, and at how many
> levels. It seems like your function would have performance issues over
> large trees since it requires 3 select statements, 3 updates, and a lock
> table. Compare this with Greg's function which requires 2 selects and 1
> update, with no lock.
>
> As a final note, you might want to rewrite your select statements like:
> SELECT
>     rgt, universeid, treeid
> FROM
>     list_objects
> WHERE
>     objid_auto=t_newparent
> INTO
>     newparentrgt, newparentuid, newparenttid;
>
> I think it's more readable and probably a little more efficient since
> you are doing less variable assignment.
>
> Robert Treat
>
> On Tue, 2002-11-26 at 00:13, Martin Crundall wrote:
>> I'm not sure that keying off lft is safe in a multi-user environment.
>> I opted to create and use an objid on the tree definition table, since
>> its identity is static.  I also found that when trees get active,
>> allowing for tree IDs increased operation speed quite a bit (i
>> actually push this to two levels--a 'universe id' and then a 'tree
>> id').  Here's my version.  Clearly not as elegantly written, but
>> nothing's gone awry yet.
>>
>> --
>> ---------------------------------------------------------------------------
>> --    Title: trackmyproject_tree_move()
>> -- Function: moves a tree branch in the hierarchy from one parent to
>> --           another.
>> --    parms: srcobj       the branch/object to be moved
>> --           newparent    the new parent for the object to be moved --
>>  Returns: zero
>> --
>> ---------------------------------------------------------------------------