From: "Adam Erickson" <adamre@cox.net>
To: <h012@ied.com>, <pgsql-sql@postgresql.org>
Subject: Re: retrieving all rows from a "tree" in one select - how ?
Date: Fri, 9 Aug 2002 17:04:23 -0500
Message-ID: <ALEKKHACBIAEBNBPFKPCEEDLEFAA.adamre@cox.net>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="us-ascii"
Content-Transfer-Encoding: 7bit
Importance: Normal
In-Reply-To: <no.Yo.N.nN.0208091650190.2280-100000@business.com>

I'll be curious to see the responses to this.  I myself deal with this same
situation every day.  Although we're currently using MySQL but moving it to
postgres (which is why I'm on these lists..)

>  -- select a tree starting with node 1234 and all its descendants:
> SELECT * FROM t WHERE id=1234 OR ANCESTOR(t.parent) IS 1234;

I've seen some really weird solutions to this.  I'm not sure if a subselect
can do this or not.  I doubt it.  Since MySQL limits us greatly we resort to
a lookup field for each record in the node.

ie. (Forgive ASCII art please)

1 --> 2
     --> 4
     --> 5
     --> 6
        --> 8
           --> 9
  --> 3
     --> 7
        --> 10

The record for id=9 would have a field index='-1-2-6-8-x'

When we want all records under node id=6 we just use:
select * from t where index like "%-6-%";

We prefix with '-' for arbitrary level searches.  We suffix with -x for an
unknown (but good) reason.  My memory is leaving me.

>  -- select the path from tree node 2345 to the root
> SELECT * FROM t WHERE id=2345 OR DESCENTANT(t.parent) IS 2345;

With our lookup/index field this is trivial.  Unfortunately, it makes the
application responsible for parsing and is probably not what you're after.

Just my two cents.  It works very well for us (make the lookup field an
index btw) but their is probably a much better way in postgres.  I don't
remember if postgres allows regexes in the where clause (ie. rlike in mysql)
but with that you can "find all nodes 3 or more leaves down from node 123"
or even weirder stuff.  We have trees with 60,000 nodes 30-40 levels deep.
Queries on the tree take very little time at all.

Adam Erickson