Content-class: urn:content-classes:message
MIME-Version: 1.0
Content-Type: text/plain;
	charset="US-ASCII"
Content-Transfer-Encoding: quoted-printable
Subject: WITH RECURSION output ordering with trees
Date: Fri, 10 Jul 2009 11:10:36 +0200
Message-ID: <E6A0649F1FBFA3408A37F505400E7AC215CE67@email.attiksystem.ch>
Thread-Topic: WITH RECURSION output ordering with trees
Thread-index: AcoBQENg5GS0MQjhTMOooFxAnyDGqw==
From: "Philippe Lang" <philippe.lang@attiksystem.ch>
To: <pgsql-sql@postgresql.org>

Hi,

I'm playing with the new "WITH RECURSIVE" feature of 8.4. I'm trying to
figure out how to use it with trees.

Here is the test code I use:

---------------------------------------------------------
--DROP TABLE recursion;

CREATE TABLE recursion
(
  id serial,
  lookup varchar(16),
  parent_id integer,
  primary key(id),
  foreign key(parent_id) references recursion(id)
);

INSERT INTO recursion VALUES(1,    'a1',     NULL);
INSERT INTO recursion VALUES(2,    'b11',    1);
INSERT INTO recursion VALUES(645,  'c111',   2);
INSERT INTO recursion VALUES(823,  'c112',   2);
INSERT INTO recursion VALUES(243,  'c113',   2);
INSERT INTO recursion VALUES(6,    'b12',    1);
INSERT INTO recursion VALUES(845,  'c121',   6);
INSERT INTO recursion VALUES(583,  'c122',   6);
INSERT INTO recursion VALUES(9,    'b13',    1);
INSERT INTO recursion VALUES(10,   'c131',   9);

WITH RECURSIVE parse_tree (depth, id, lookup, parent_id) AS
(
  SELECT=20
    0,
    parent.id,=20
    parent.lookup,=20
    parent.parent_id=20
  FROM recursion AS parent=20
  WHERE parent_id IS NULL
 =20
  UNION ALL
 =20
  SELECT=20
    parent.depth + 1,
    child.id,=20
    child.lookup,=20
    child.parent_id=20
  FROM parse_tree parent, recursion AS child
  WHERE child.parent_id =3D parent.id
)

SELECT * FROM parse_tree;
---------------------------------------------------------

Here is the result:

 depth | id  | lookup | parent_id
-------+-----+--------+-----------
     0 |   1 | a1     |
     1 |   2 | b11    |         1
     1 |   6 | b12    |         1
     1 |   9 | b13    |         1
     2 | 645 | c111   |         2
     2 | 823 | c112   |         2
     2 | 243 | c113   |         2
     2 | 845 | c121   |         6
     2 | 583 | c122   |         6
     2 |  10 | c131   |         9

I'd like to perform a real recursion, and show the tree structure in a
more appopriate way, like this:

 depth | id  | lookup | parent_id
-------+-----+--------+-----------
     0 |   1 | a1     |
     1 |   2 | b11    |         1
     2 | 645 | c111   |         2
     2 | 823 | c112   |         2
     2 | 243 | c113   |         2
     1 |   6 | b12    |         1
     2 | 845 | c121   |         6
     2 | 583 | c122   |         6
     1 |   9 | b13    |         1
     2 |  10 | c131   |         9

Any idea how to do that? (without trying to sort on the lookup column,
whose values can be random outside this test)

Best regards,

Philippe Lang