Message-ID: <3DDC053A.8060300@joeconway.com>
Date: Wed, 20 Nov 2002 13:57:14 -0800
From: Joe Conway <mail@joeconway.com>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US;
	rv:1.1) Gecko/20020826
MIME-Version: 1.0
To: Dan Langille <dan@langille.org>
Cc: pgsql-sql@postgresql.org
Subject: Re: Trees: maintaining pathnames
References: <20021117112520.C8127-200000@nezlok.unixathome.org>
	<3DDBA82F.15041.BA07175D@localhost>
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit

Dan Langille wrote:
> Given that I'm considering adding a new field path_name to the tree, 
> I can't see the ltree package will give me anything more than I can 
> get from like. My main reason for adding path_name was doing queries 
> such as:
> 
>    select * from tree where path_name like '/path/to/parent/%'
> 
> which will return me all the descendants of a give node (in this case 
> '/path/to/parent/'.[2]

FWIW, you could also do this with connectby() in contrib/tablefunc (new in 
7.3; see the README for syntax details):

test=# SELECT t.* FROM connectby('tree', 'id', 'parent_id', '1', 0, '~') AS 
c(id int, parent_id int, level int, branch text), tree t WHERE t.id = c.id;
  id | parent_id |        name
----+-----------+--------------------
   1 |           | Top
   2 |         1 | Science
   3 |         2 | Astronomy
   4 |         3 | Astrophysics
   5 |         3 | Cosmology
   6 |         1 | Hobbies
   7 |         6 | Amateurs_Astronomy
   8 |         1 | Collections
   9 |         8 | Pictures
  10 |         9 | Astronomy
  11 |        10 | Stars
  12 |        10 | Galaxies
  13 |        10 | Astronauts
(13 rows)

test=# SELECT t.* FROM connectby('tree', 'id', 'parent_id', '6', 0, '~') AS 
c(id int, parent_id int, level int, branch text), tree t WHERE t.id = c.id;
  id | parent_id |        name
----+-----------+--------------------
   6 |         1 | Hobbies
   7 |         6 | Amateurs_Astronomy
(2 rows)

test=# SELECT t.* FROM connectby('tree', 'id', 'parent_id', '8', 0, '~') AS 
c(id int, parent_id int, level int, branch text), tree t WHERE t.id = c.id;
  id | parent_id |    name
----+-----------+-------------
   8 |         1 | Collections
   9 |         8 | Pictures
  10 |         9 | Astronomy
  11 |        10 | Stars
  12 |        10 | Galaxies
  13 |        10 | Astronauts


You could also do:

CREATE OR REPLACE FUNCTION node_id(text) returns int as 'select id from tree 
where name = $1' language 'sql';

test=# SELECT t.* FROM connectby('tree', 'id', 'parent_id', 
node_id('Science'), 0) AS c(id int, parent_id int, level int), tree t WHERE 
t.id = c.id;
  id | parent_id |     name
----+-----------+--------------
   2 |         1 | Science
   3 |         2 | Astronomy
   4 |         3 | Astrophysics
   5 |         3 | Cosmology
(4 rows)


> 
> I have discussed [offlist] the option of using a secondary table to 
> store the pathname (i.e. a cach table) which would be updated using a 
> loop in the tigger instead of using cascading triggers.  I would 
> prefer to keep the pathname in the same table.
> 
> In my application, I have about 120,000 nodes in the tree.  I am 
> using PL/pgSQL quite a lot.  Perhaps moving the triggers to C at a 
> later date may provide a speed increase if the tree expands 
> considerably.

I've tested connectby() on a table with about 220,000 nodes. It is pretty fast 
(about 1 sec to return a branch with 3500 nodes), and is entirely dynamic 
(requires no triggers).

Joe