63

I have a table similar to this:

CREATE TABLE example (
  id integer primary key,
  name char(200),
  parentid integer,
  value integer);

I can use the parentid field to arrange data into a tree structure.

Now here's the bit I can't work out. Given a parentid, is it possible to write an SQL statement to add up all the value fields under that parentid and recurse down the branch of the tree ?

UPDATE: I'm using posgreSQL so the fancy MS-SQL features are not available to me. In any case, I'd like this to be treated as a generic SQL question.

3
  • I'm using posgreSQL so the fancy MS-SQL features are not available to me. In any case, I'd like this to be treated as a generic SQL question. BTW, I'm very impressed to have 6 answers within 15 minutes of asking the question! Go stack overflow! Sep 9, 2008 at 23:28
  • 3
    This is heirarchical data. I've found Anthony Mollinaro's discussions on heirarchical data in SQL Cookbook (O'Reilly) to be really handy; he covers virtually all popular DBMSs, including PostrgreSQL.
    – J. Polfer
    Mar 20, 2009 at 13:37
  • 1
    If you come here from google check @Chris KL response, since PostgreSQl 8.4 recursive queries are available on postgreSQL.
    – regilero
    Jun 20, 2011 at 12:24

11 Answers 11

42

Here is an example script using common table expression:

with recursive sumthis(id, val) as (
    select id, value
    from example
    where id = :selectedid
    union all
    select C.id, C.value
    from sumthis P
    inner join example C on P.id = C.parentid
)
select sum(val) from sumthis

The script above creates a 'virtual' table called sumthis that has columns id and val. It is defined as the result of two selects merged with union all.

First select gets the root (where id = :selectedid).

Second select follows the children of the previous results iteratively until there is nothing to return.

The end result can then be processed like a normal table. In this case the val column is summed.

1
  • If I understand your code correctly, it takes some (id, value) tuples matching on selectedid. Then joins those with a new instance of sumthis, which again contains those same tuples. So why would this query ever terminate? My understanding failure lies probably at how :selectedid is set. Or maybe where the values for the child sumthis tables come from
    – lucidbrot
    Jun 12, 2017 at 7:41
34

Since version 8.4, PostgreSQL has recursive query support for common table expressions using the SQL standard WITH syntax.

15

If you want a portable solution that will work on any ANSI SQL-92 RDBMS, you will need to add a new column to your table.

Joe Celko is the original author of the Nested Sets approach to storing hierarchies in SQL. You can Google "nested sets" hierarchy to understand more about the background.

Or you can just rename parentid to leftid and add a rightid.

Here is my attempt to summarize Nested Sets, which will fall woefully short because I'm no Joe Celko: SQL is a set-based language, and the adjacency model (storing parent ID) is NOT a set-based representation of a hierarchy. Therefore there is no pure set-based method to query an adjacency schema.

However, most of the major platforms have introduced extensions in recent years to deal with this precise problem. So if someone replies with a Postgres-specific solution, use that by all means.

4
  • @Portman I've looked at nested sets. Seems like a good idea, but it seems like the insert/delete cost is terribly high.
    – Kibbee
    Sep 10, 2008 at 0:40
  • Yes, seems. But trust me - once you write the CRUD procedures, it performs very well.
    – Portman
    Sep 10, 2008 at 1:18
  • 1
    Every update in the nested-sets model requires you to update > 50% of the rows in the table. It's a clever mechanism, but it's totally contraindicated in any real-world situation. I'm generally a fan of Celko, but he's wrong on this point.
    – Sarah G
    Nov 19, 2013 at 19:46
  • Intelligententerprise Link is dead now
    – bf2020
    Feb 27, 2014 at 2:45
12

There are a few ways to do what you need in PostgreSQL.

Something like this:

create or replace function example_subtree (integer)
returns setof example as
'declare results record;
         child record;
 begin
  select into results * from example where parent_id = $1;
  if found then
    return next results;
    for child in select id from example
                  where parent_id = $1
      loop
        for temp in select * from example_subtree(child.id)
        loop
          return next temp;
        end loop;
      end loop;
  end if;
  return null;
end;' language 'plpgsql';

select sum(value) as value_sum
  from example_subtree(1234);
10

A standard way to make a recursive query in SQL are recursive CTE. PostgreSQL supports them since 8.4.

In earlier versions, you can write a recursive set-returning function:

CREATE FUNCTION fn_hierarchy (parent INT)
RETURNS SETOF example
AS
$$
        SELECT  example
        FROM    example
        WHERE   id = $1
        UNION ALL
        SELECT  fn_hierarchy(id)
        FROM    example
        WHERE   parentid = $1
$$
LANGUAGE 'sql';

SELECT  *
FROM    fn_hierarchy(1)

See this article:

2
  • +1 for recursive CTE which is supported by all major DBMS nowadays - except for MySQL and SQLite
    – user330315
    Jan 11, 2011 at 16:13
  • Maybe I'm doing it wrong, but if I have any more than one field specified in the first SELECT clause, eg SELECT id, name, I get an each UNION query must have the same number of columns error at the SELECT fn_hierarchy line. I guess in the final SELECT I can re-join onto the example table to get the rest of the fields, but it's not so elegant any more.
    – poshest
    Aug 6, 2015 at 14:45
2

The following code compiles and it's tested OK.

create or replace function subtree (bigint)
returns setof example as $$
declare
    results record;
    entry   record;
    recs    record;
begin
    select into results * from example where parent = $1;
    if found then
        for entry in select child from example where parent = $1 and child  parent loop
            for recs in select * from subtree(entry.child) loop
                return next recs;
            end loop;
        end loop;
    end if;
    return next results;
end;
$$ language 'plpgsql';

The condition "child <> parent" is needed in my case because nodes point to themselves.

1

Oracle has "START WITH" and "CONNECT BY"

select 
    lpad(' ',2*(level-1)) || to_char(child) s

from 
    test_connect_by 

start with parent is null
connect by prior child = parent;

http://www.adp-gmbh.ch/ora/sql/connect_by.html

1

Just as a brief aside although the question has been answered very well, it should be noted that if we treat this as a:

generic SQL question

then the SQL implementation is fairly straight-forward, as SQL'99 allows linear recursion in the specification (although I believe no RDBMSs implement the standard fully) through the WITH RECURSIVE statement. So from a theoretical perspective we can do this right now.

1

None of the examples worked OK for me so I've fixed it like this:

declare
    results record;
    entry   record;
    recs    record;
begin
    for results in select * from project where pid = $1 loop
        return next results;
        for recs in select * from project_subtree(results.id) loop
            return next recs;
        end loop;
    end loop;
    return;
end;
0

is this SQL Server? Couldn't you write a TSQL stored procedure that loops through and unions the results together?

I am also interested if there is a SQL-only way of doing this though. From the bits I remember from my geographic databases class, there should be.

-1

If you need to store arbitrary graphs, not just hierarchies, you could push Postgres to the side and try a graph database such as AllegroGraph:

Everything in the graph database is stored as a triple (source node, edge, target node) and it gives you first class support for manipulating the graph structure and querying it using a SQL like language.

It doesn't integrate well with something like Hibernate or Django ORM but if you are serious about graph structures (not just hierarchies like the Nested Set model gives you) check it out.

I also believe Oracle has finally added a support for real Graphs in their latest products, but I'm amazed it's taken so long, lots of problems could benefit from this model.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.