Thread: Sorting with materialized paths
My apologies. This isn't PG-specific, but since this is running on PostgreSQL 8.4, maybe there are specific features
whichmight help.
I have a tree structure in a table and it uses materialized paths to allow me to find children quickly. However, I also
needto 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
therough 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?
Cheers,
Ovid
--
Buy the book - http://www.oreilly.com/catalog/perlhks/
Tech blog - http://blogs.perl.org/users/ovid/
Twitter - http://twitter.com/OvidPerl
Official Perl 6 Wiki - http://www.perlfoundation.org/perl6
Ovid <curtis_ovid_poe@yahoo.com> writes:
> My apologies. This isn't PG-specific, but since this is running on PostgreSQL 8.4, maybe there are specific features
whichmight help.
> I have a tree structure in a table and it uses materialized paths to allow me to find children quickly. However, I
alsoneed to sort the results depth-first, as one would expect with threaded forum replies.
I think contrib/ltree might help you here. However, it seems to sort
node names textually rather than numerically, so you might need to
change it a bit for your own purposes.
regards, tom lane
On Sun, May 9, 2010 at 8:33 AM, Ovid <curtis_ovid_poe@yahoo.com> wrote: > My apologies. This isn't PG-specific, but since this is running on PostgreSQL 8.4, maybe there are specific features whichmight help. > > I have a tree structure in a table and it uses materialized paths to allow me to find children quickly. However, I alsoneed 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 therough 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
On Sun, May 9, 2010 at 4:47 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote: > Ovid <curtis_ovid_poe@yahoo.com> writes: >> My apologies. This isn't PG-specific, but since this is running on PostgreSQL 8.4, maybe there are specific features whichmight help. >> I have a tree structure in a table and it uses materialized paths to allow me to find children quickly. However, I alsoneed to sort the results depth-first, as one would expect with threaded forum replies. > > I think contrib/ltree might help you here. However, it seems to sort > node names textually rather than numerically, so you might need to > change it a bit for your own purposes. > That's rather unfortunate. Ltree is awfully convenient and it would be nice to be able to use it. If you just used plain Postgres arrays of integers you would get the sorting you want. But you lose all the useful ltree operators for trees. -- greg
On 10 May 2010, at 20:06, Greg Stark wrote: > On Sun, May 9, 2010 at 4:47 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote: >> Ovid <curtis_ovid_poe@yahoo.com> writes: >>> My apologies. This isn't PG-specific, but since this is running on PostgreSQL 8.4, maybe there are specific featureswhich might help. >>> I have a tree structure in a table and it uses materialized paths to allow me to find children quickly. However, I alsoneed to sort the results depth-first, as one would expect with threaded forum replies. >> >> I think contrib/ltree might help you here. However, it seems to sort >> node names textually rather than numerically, so you might need to >> change it a bit for your own purposes. >> > > That's rather unfortunate. Ltree is awfully convenient and it would be > nice to be able to use it. > > If you just used plain Postgres arrays of integers you would get the > sorting you want. But you lose all the useful ltree operators for > trees. I recall from the docs that you can create arrays of ltrees. It has some special operators for that. I couldn't figure outwhat the use case for those ltree-arrays was (the docs are rather sparse), but it might just be what you're looking for. Alban Hertroys -- Screwing up is an excellent way to attach something to the ceiling. !DSPAM:737,4be8791c10411720337464!
Ovid wrote on 09.05.2010 15:33:
> 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
>
Try this:
with recursive thread_display (id, parent_id, matpath, created, sort_key)
as
(
select id, parent_id, matpath, created, array[id] as sort_key
from threads
where id = 1
union all
select c.id, c.parent_id, c.matpath, c.created, p.sort_key||array[c.id]
from threads c
join thread_display p on c.parent_id = p.id
)
select id, parent_id, matpath, created
from thread_display
order by sort_key;
Thomas