Обсуждение: Sorting with materialized paths

Поиск
Список
Период
Сортировка

Sorting with materialized paths

От
Ovid
Дата:
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

Re: Sorting with materialized paths

От
Tom Lane
Дата:
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

Re: Sorting with materialized paths

От
Peter Hunsberger
Дата:
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

Re: Sorting with materialized paths

От
Greg Stark
Дата:
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

Re: Sorting with materialized paths

От
Alban Hertroys
Дата:
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!

Re: Sorting with materialized paths

От
Thomas Kellerer
Дата:
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