Re: Sorting with materialized paths

On Sun, May 9, 2010 at 8:33 AM, Ovid <curtis_ovid_poe(at)yahoo(dot)com> wrote:
> My apologies. This isn't PG-specific, but since this is running on PostgreSQL 8.4, maybe there are specific features which might help.
>
> I have a tree structure in a table and it uses materialized paths to allow me to find children quickly. However, I also need to sort the results depth-first, as one would expect with threaded forum replies.
>
>  id | parent_id | matpath |          created
> ----+-----------+---------+----------------------------
>  2 |         1 | 1       | 2010-05-08 15:18:37.987544
>  3 |         1 | 1       | 2010-05-08 17:38:14.125377
>  4 |         1 | 1       | 2010-05-08 17:38:57.26743
>  5 |         1 | 1       | 2010-05-08 17:43:28.211708
>  7 |         1 | 1       | 2010-05-08 18:18:11.849735
>  6 |         2 | 1.2     | 2010-05-08 17:50:43.288759
>  9 |         5 | 1.5     | 2010-05-09 14:02:43.818646
>  8 |         6 | 1.2.6   | 2010-05-09 14:01:17.632695
>
> So the final results should actually be sorted like this:
>
>  id | parent_id | matpath |          created
> ----+-----------+---------+----------------------------
>  2 |         1 | 1       | 2010-05-08 15:18:37.987544
>  6 |         2 | 1.2     | 2010-05-08 17:50:43.288759
>  8 |         6 | 1.2.6   | 2010-05-09 14:01:17.632695
>  3 |         1 | 1       | 2010-05-08 17:38:14.125377
>  4 |         1 | 1       | 2010-05-08 17:38:57.26743
>  5 |         1 | 1       | 2010-05-08 17:43:28.211708
>  9 |         5 | 1.5     | 2010-05-09 14:02:43.818646
>  7 |         1 | 1       | 2010-05-08 18:18:11.849735
>
> Rationale:  this is for a threaded forum and id 6 is a reply to id 2, so it needs to show up after that one.  Here's the rough structure of what the output would look like (imagine an HTML forum):
>
> * id 1 (root post)
>    * id 2
>        * id 6
>            * id 8
>    * id 3
>    * id 4
>    * id 5
>        * id 9
>    * id 7
>
> How would I work that out? Can I do that in straight SQL or should additional information be added to this table?
>

This is (once more) a flat query if you use a set / subset tree
implementation. Joe Celko's book "Trees and Hierarchies in SQL for
Smarties" might be the fastest way to get up to speed on this, but you
can also figure it out if you spend a bit of time with Google....
Basically, every node in the tree is a table row with two columns, say
left and right. All children are contained within the left and right
of the parent. Pre-order tree traversal gives the algorithm for
assigning left and right. Once done, your problem is solved by
ordering on left.

--
Peter Hunsberger