Postgres Pro
Downloads
Home   >   mailing lists

Thread: Path to top of tree

Path to top of tree

From
Steve Crawford
Date:
Given a table which includes tree-type information consisting of an id
and a parent_id, is there an already existing function that will return
the path to the top of the tree for a given record?

The connectby function from the contrib tablefuncs does what I want for
a whole table, but I haven't found a way to execute it in an efficient
way to get the information for a single record. A query in the form of
"select connectby(.....) where ..." will return the answer I want, but
it builds the tree on the whole table and then filters to get the record
I want which, for 5000 records, is taking about half a minute.

Before I start writing my own function, have I overlooked something
already available or some better way to invoke connectby?

Cheers,
Steve

Re: Path to top of tree

From
"Merlin Moncure"
Date:
On Nov 13, 2007 3:35 PM, Steve Crawford <scrawford@pinpointresearch.com> wrote:
> Given a table which includes tree-type information consisting of an id
> and a parent_id, is there an already existing function that will return
> the path to the top of the tree for a given record?
>
> The connectby function from the contrib tablefuncs does what I want for
> a whole table, but I haven't found a way to execute it in an efficient
> way to get the information for a single record. A query in the form of
> "select connectby(.....) where ..." will return the answer I want, but
> it builds the tree on the whole table and then filters to get the record
> I want which, for 5000 records, is taking about half a minute.
>
> Before I start writing my own function, have I overlooked something
> already available or some better way to invoke connectby?

maybe or maybe not, but here is one way to do it:

create or replace function parent(foo) returns foo as
$$
    select parent(foo) from foo where id = ($1).parent_id
        union all
    select $1
    limit 1;
$$ language sql;

create table foo(id int, parent_id int);
insert into foo values(1, null);
insert into foo values(2, 1);
insert into foo values(3, 2);

select (parent(foo)).* from foo where id = 3;
 id | parent_id
----+-----------
  1 |
(1 row)

if you want another general tactic that works pretty well for trees in
a lot of workloads check out my array approach here:
http://merlinmoncure.blogspot.com/2007/09/one-of-my-favorite-problems-in.html

merlin

Re: Path to top of tree

From
"Merlin Moncure"
Date:
On Nov 13, 2007 10:54 PM, Merlin Moncure <mmoncure@gmail.com> wrote:
> maybe or maybe not, but here is one way to do it:
>
> create or replace function parent(foo) returns foo as
> $$
>         select parent(foo) from foo where id = ($1).parent_id
>                 union all
>         select $1
>         limit 1;
> $$ language sql;
>
> create table foo(id int, parent_id int);
> insert into foo values(1, null);
> insert into foo values(2, 1);
> insert into foo values(3, 2);
>
> select (parent(foo)).* from foo where id = 3;
>  id | parent_id
> ----+-----------
>   1 |
> (1 row)
>
> if you want another general tactic that works pretty well for trees in
> a lot of workloads check out my array approach here:
> http://merlinmoncure.blogspot.com/2007/09/one-of-my-favorite-problems-in.html

here is another way to write the function that might be a little bit faster:

create or replace function parent(foo) returns foo as
$$
  select case
    when ($1).parent_id is null then $1
    else (select parent(foo) from foo where id = ($1).parent_id)
    end;
$$ language sql;

merlin