Subject: Re: Querying Hierarchical Data
From: Lex Berezhny <LBerezhny@DevIS.com>
To: Eric <someone@somewhere.com>
Cc: pgsql-sql@postgresql.org
In-Reply-To: <D4z8a.8540$X14.581155@news2.telusplanet.net>
References: <D4z8a.8540$X14.581155@news2.telusplanet.net>
Content-Type: text/plain
Organization: 
Message-Id: <1046705511.15057.10.camel@hortus>
Mime-Version: 1.0
Date: 03 Mar 2003 10:31:51 -0500
Content-Transfer-Encoding: 7bit

On Sun, 2003-03-02 at 21:27, Eric wrote:
> Hi,
> 
> How do I access hierarchical data under PostgreSQL?
> Does it have SQL command similar to Oracle's CONNECT BY?
> 
> Any help is appreciated

Hey,

  I don't think PostgreSQL has a CONNECT BY command.

  But, if your hierarchical data is stored in an adjecency list model
table then you can use the following function (i wrote it as a proof of
concept and don't know how well it would scale on a VERY large dataset,
but you are welcome to try ;-)

CREATE TYPE tree_result AS (id int4, level int4, name varchar);
CREATE FUNCTION render(int4, int4) RETURNS SETOF tree_result AS '
DECLARE
    current_level tree_result%ROWTYPE;
    stack_level int4 := 1;
    start_level ALIAS FOR $1;
    limit_level ALIAS FOR $2;
    stack_oid int4;
BEGIN

    SELECT INTO stack_oid oid FROM pg_class WHERE relname = ''stack'';
    IF NOT FOUND THEN
        CREATE TEMPORARY TABLE stack (id int4, level int4, name varchar);
    END IF;

    INSERT INTO stack (id, level, name)
        (SELECT child AS id, stack_level, name
         FROM tree WHERE
                CASE WHEN start_level IS NULL OR start_level = 0
                    THEN parent IS NULL
                    ELSE parent = start_level
                END);

    WHILE stack_level > 0 LOOP
        SELECT INTO current_level * FROM stack
            WHERE level = stack_level
            ORDER BY name LIMIT 1;
        IF current_level.id IS NOT NULL THEN
            RETURN NEXT current_level;
            DELETE FROM stack WHERE id = current_level.id;
            IF stack_level+1 <= limit_level THEN
                INSERT INTO stack (id, level, name)
                    (SELECT child AS id, stack_level+1 AS level, name
                     FROM tree WHERE parent = current_level.id);
                IF FOUND THEN
                    stack_level := stack_level + 1;
                END IF;
            END IF;
        ELSE
            stack_level := stack_level - 1;
        END IF;
    END LOOP;

    RETURN;
END;
' LANGUAGE 'plpgsql';


To give an example, consider this data:

CREATE TABLE tree (child int4, parent int4, name varchar);
INSERT INTO tree VALUES (1, NULL, 'lex');
INSERT INTO tree VALUES (2, NULL, 'marina');
INSERT INTO tree VALUES (3, 1, 'oles');
INSERT INTO tree VALUES (4, 1, 'marina');
INSERT INTO tree VALUES (5, 3, 'peter');
INSERT INTO tree VALUES (6, 3, 'elvira');
INSERT INTO tree VALUES (7, 6, 'peter');
INSERT INTO tree VALUES (8, 6, 'natasha');
INSERT INTO tree VALUES (9, 4, 'valja');
INSERT INTO tree VALUES (10, 9, 'tosja');
INSERT INTO tree VALUES (11, 4, 'vitja');
INSERT INTO tree VALUES (12, 11, 'eda');

And these queries:

SELECT repeat('  ', level)||name AS display FROM render(0, 100);
     display     
-----------------
   lex
     marina
       valja
         tosja
       vitja
         eda
     oles
       elvira
         natasha
         peter
       peter
   marina
(12 rows)


SELECT id, repeat('  ', level)||name AS display FROM render(3, 100);
 id |   display   
----+-------------
  6 |   elvira
  8 |     natasha
  7 |     peter
  5 |   peter
(4 rows)


SELECT id, repeat('  ', level)||name AS display FROM render(1, 2);
 id |  display   
----+------------
  4 |   marina
  9 |     valja
 11 |     vitja
  3 |   oles
  6 |     elvira
  5 |     peter


I hope this helps. If you do use it, I would be very interested to know
what kind of performance you get.

thanks and good luck!!

 - lex