To: pgsql-sql@postgresql.org
From: Thomas Kellerer <spam_eater@gmx.net>
Subject: Re: WITH RECURSION output ordering with trees
Date: Fri, 10 Jul 2009 13:23:17 +0200
Lines: 59
Message-ID: <h378b6$drn$1@ger.gmane.org>
References: <E6A0649F1FBFA3408A37F505400E7AC215CE67@email.attiksystem.ch>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US;
	rv:1.8.1.22) Gecko/20090605 Thunderbird/2.0.0.22 Mnenhy/0.7.6.666
In-Reply-To: <E6A0649F1FBFA3408A37F505400E7AC215CE67@email.attiksystem.ch>

Philippe Lang, 10.07.2009 11:10:
> 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:
> 
> I'd like to perform a real recursion, and show the tree structure in a
> more appopriate way, like this:
> 
> Any idea how to do that? (without trying to sort on the lookup column,
> whose values can be random outside this test)


The manual has a nice hint on this adding up IDs to "generate" a path like column that can be used for sorting. 

Try the following:

WITH RECURSIVE parse_tree (depth, id, lookup, parent_id, sort_path) AS
(
  SELECT 0, 
    parent.id, 
    cast(parent.lookup as text),
    parent.parent_id, 
    array[0] as sort_path 
  FROM recursion_sample parent 
  WHERE parent_id IS NULL
  UNION ALL
  SELECT 
    parent.depth + 1,
    child.id, 
    rpad(' ', depth * 2) || child.lookup, 
    child.parent_id,
    parent.sort_path || child.id
  FROM parse_tree parent JOIN recursion_sample child on child.parent_id = parent.id
)
select id, lookup
from parse_tree
order by sort_path
;

This will output:

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

Thomas