Re: Ltree - how to sort nodes on parent node

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

Re: Ltree - how to sort nodes on parent node

От:
Alban Hertroys <dalroi@solfertje.student.utwente.nl>
Дата:
On 20 Apr 2010, at 18:05, Harald Fuchs wrote:

> Here's a working version:
> 
>  WITH RECURSIVE tree (path, category, sort_order, parent) AS (
>    SELECT category, category, sort_order::text, parent
>    FROM node
>    WHERE parent IS NULL
>  UNION ALL
>    SELECT t.path || '.' || n.category,
>           n.category,
>           t.sort_order || '.' || n.sort_order,
>           n.parent
>    FROM tree t
>    JOIN node n ON n.parent = t.category
>  )
>  SELECT path
>  FROM tree
>  ORDER BY sort_order


May be, but then you're just re-inventing ltree again. I'm pretty sure this must be possible without adding convoluted things like casting sort orders to text (which can for example cause issues like '10' ending up between '1' and '2').

Since this is 8.4 anyway (CTE's after all), can't the sorting be done using a windowing function or something? We have recursion now, there's got to be a proper solution, I just can't get my mind around it right now.

Alban Hertroys

--
If you can't see the forest for the trees,
cut the trees and you'll see there is no forest.


!DSPAM:737,4bcdf5a610412270627163!

Re: Ltree - how to sort nodes on parent node

От:
Alban Hertroys <dalroi@solfertje.student.utwente.nl>
Дата:
On 19 Apr 2010, at 20:26, cojack wrote:

>> Alban Hertroys wrote:
>> 
>> It would help if you'd show us what result you expect from ordering the
>> above.
>> 
>> Most people would order this by path I think. However that doesn't match
>> your sort column and I can't think of any method that would give results
>> in such an arbitrary order as you seem to be specifying - unless you set
>> it by hand like you do.

> Yes, you have right, for example I create new idea of stored data in table:
> 
> here is a paste: http://pastebin.com/4pX5cM7j -- never expired link
> 
> As you can see, I have noodes with numeric type, those nodes present a sort 
> position by self. And If I type ORDER BY path; I will have data like I want 
> to have: http://pastebin.com/R4z01LC5 -- never expired link
> 
> Again, you can see now grouped data in his nodes, this is the outputed data 
> I wanted. If you know better way to make this WITHOUT recursive queries, 
> give me a hint.


Aha, looks like you want to sort each tree level by some user-specified order.

You should realise that ltree was contributed before Postgres supported (recursive) CTE's. If you're using ltree in combination with recursive CTE's you're doing twice the work that you need to do - ltree was created as a means to make recursive queries possible in the first place.

I think you have basically two ways to go about this:

1). The way you're doing this in your new examples should work, although I'd probably make the ordering numbers part of the category names and split those off when I read them. For example:
         27 | 1|Top
         28 | 1|Top.1|Science
         29 | 1|Top.2|Hobby
         30 | 1|Top.3|Colors
         31 | 1|Top.1|Science.1|Physics
         32 | 1|Top.1|Science.2|Chemistry
         33 | 1|Top.1|Science.3|Biology
         34 | 1|Top.1|Science.4|History
         35 | 1|Top.2|Hobby.1|Fishing
         36 | 1|Top.2|Hobby.2|Football
         37 | 1|Top.3|Colors.1|Black
         38 | 1|Top.3|Colors.2|Red
         39 | 1|Top.3|Colors.3|Blue
         40 | 1|Top.1|Science.5|Archeology
         41 | 1|Top.2|Hobby.3|Swimming
         42 | 1|Top.3|Colors.4|Gray
         43 | 1|Top.3|Colors.5|Purple
         44 | 1|Top.3|Colors.6|Brown
         45 | 1|Top.2|Hobby.4|Climbing

2). Drop the ltree column and go with a truly recursive approach, something like this:

CREATE TABLE node (
	category	text	NOT NULL PRIMARY KEY,
	sort_order	int	NOT NULL,
	parent		text	REFERENCES tree (category)
					ON UPDATE CASCADE
					ON DELETE CASCADE
);

WITH RECURSIVE tree AS (
	SELECT *
	  FROM node
	 WHERE parent IS NULL

	UNION ALL

	SELECT node.*
	  FROM tree, node
	 WHERE node.parent = tree.category
	 ORDER BY sort_order
)
SELECT * FROM tree;

I haven't actually used recursive CTE's before so there may be some errors in the above, but you get the general idea.

Alban Hertroys

--
Screwing up is an excellent way to attach something to the ceiling.


!DSPAM:737,4bcd773910411833268189!

Re: Ltree - how to sort nodes on parent node

От:
Alban Hertroys <dalroi@solfertje.student.utwente.nl>
Дата:
On 20 Apr 2010, at 11:59, cojack wrote:

>> 1). The way you're doing this in your new examples should work, although
>> I'd probably make the ordering numbers part of the category names and
>> split those off when I read them. For example:
>>         27 | 1|Top
>>         28 | 1|Top.1|Science
>>         29 | 1|Top.2|Hobby
>>         30 | 1|Top.3|Colors
>>         31 | 1|Top.1|Science.1|Physics
>>         32 | 1|Top.1|Science.2|Chemistry
>>         33 | 1|Top.1|Science.3|Biology
>>         34 | 1|Top.1|Science.4|History
>>         35 | 1|Top.2|Hobby.1|Fishing
>>         36 | 1|Top.2|Hobby.2|Football
>>         37 | 1|Top.3|Colors.1|Black
>>         38 | 1|Top.3|Colors.2|Red
>>         39 | 1|Top.3|Colors.3|Blue
>>         40 | 1|Top.1|Science.5|Archeology
>>         41 | 1|Top.2|Hobby.3|Swimming
>>         42 | 1|Top.3|Colors.4|Gray
>>         43 | 1|Top.3|Colors.5|Purple
>>         44 | 1|Top.3|Colors.6|Brown
>>         45 | 1|Top.2|Hobby.4|Climbing

> My and your first example doesn't work fine at all, why? Becouse when we add 
> more thank 10 sub nodes in some node, the 10 node will not be after 9, but 

That's just a matter of reserving enough padding for the numbers to fit. It does mean you bake in an upper limit to the number of items people can sort, but there is a practical limit your users are very unlikely to ever pass. I think anything past 4 digits is unlikely to happen. It's not a very clean solution, but it certainly does work.

> after 1 before 2, and this is not good idea to set sort in path. I think the 
> best idea for this will be create other column, with also ltree data type 
> and stored inside a sort/ordering data. Like:
> 
> 1
> 1.1
> 1.1.1
> 1.1.2
> 1.1.3
> 
> And while selected it from table, just cast it to int. I'll check this and 
> his performance after I return from work.

This has the same problem as the previous one, 10 will end up between 1 and 2. It is cleaner than combining both into one tree though, so with sufficient padding it should work.

> I am not interested about recursive queries, i think this kill ltree idea.


And IMHO it should. ltree is from a time when we didn't have any other means to describe data organised as a tree in Postgres. Navigating a tree is inherently recursive, so recursion is most likely the proper way to go about it.

A solution omitting recursion (like ltree) can be faster, but you will run into limitations like the one you're currently struggling with.

A solution with recursive queries will probably be more flexible and allows for referential integrity without having to write your own triggers and stuff - for example, what happens if you decide that Archeology isn't a Science but a Colour? What makes sure it's child-nodes get moved into Colors as well?

Alban Hertroys

--
If you can't see the forest for the trees,
cut the trees and you'll see there is no forest.


!DSPAM:737,4bcdf97810413554942613!

Re: Ltree - how to sort nodes on parent node

От:
Saccilotto Ramon <Ramon.Saccilotto@usb.ch>
Дата:
Hi everonye,

I don’t know if this is still a topic for anyone. But here is a query that I came up with to do the sorting. It will currently probably not make use of the ltree indexing, so it might be worth to further adapt the query.

The table (example_table) would be something like

path|ordinal
----+--------------
Top | 1
Top.Science | 1
Top.Hobbies | 2
Top.Collections | 3
…

The selection would work as follows:

/* create a intermediate table with an id column */
WITH ltreeTable AS (
  SELECT
  -- select the last part of the path as id
  subpath(path, -1) as "id",
  "path",
  "ordinal"
  FROM example_table
),

/* split the ltree path into separate parts */
treeParts AS (
  SELECT
  "id",
  -- split the path into separate parts
  unnest(regexp_split_to_array(path::text, '\.'))::ltree as "part",
  -- generate an ordinal for each array to preserve the order of the path
  generate_subscripts(regexp_split_to_array(path::text, '\.'), 1) as "idx"
  FROM ltreeTable
),

/* prefix each part with its respective zero-padded ordinal for sorting */
treePartsSorted AS (
  SELECT
  a.*,
  -- prefix each part with the ordinal
  lpad(b.ordinal::text, 4, '0') || '.' || a.part::text as "prefixed"
  FROM treeParts as a

  LEFT JOIN ltreeTable as b
  ON a.part = b.id
),

/* combine the paths back again */
treeSorting AS (
  SELECT
  "id",
  -- aggregate all parts and combine it back to an ltree path
  array_to_string(array_agg(prefixed ORDER BY idx),'.') AS "sorting"
  FROM treePartsSorted
  GROUP BY "id"
),

/* add the sorting column to the tree */
tree AS (
  SELECT
  a.*, text2ltree(b.sorting) as "sorting"
  FROM ltreeTable as a
  LEFT JOIN treeSorting as b
  ON a.id = b.id
)

SELECT * FROM tree
ORDER BY sorting asc;

Re: Ltree - how to sort nodes on parent node

От:
Alban Hertroys <dalroi@solfertje.student.utwente.nl>
Дата:
On 19 Apr 2010, at 9:23, cojack wrote:

> Hello,

> id |                     path                      | sort                                                                                                   
> ----+-----------------------------------------------+------                                                                                                  
>  1 | Top                                           |    1                                                                                                   
>  2 | Top.Science                                   |    1                                                                                                   
>  3 | Top.Science.Astronomy                         |    1                                                                                                   
>  4 | Top.Science.Astronomy.Astrophysics            |    1                                                                                                   
>  5 | Top.Science.Astronomy.Cosmology               |    2                                                                                                   
>  6 | Top.Hobbies                                   |    2                                                                                                   
>  7 | Top.Hobbies.Amateurs_Astronomy                |    2                                                                                                   
>  8 | Top.Collections                               |    3
>  9 | Top.Collections.Pictures                      |    1
> 10 | Top.Collections.Pictures.Astronomy            |    1
> 11 | Top.Collections.Pictures.Astronomy.Stars      |    1
> 12 | Top.Collections.Pictures.Astronomy.Galaxies   |    2
> 13 | Top.Collections.Pictures.Astronomy.Astronauts |    3
> 15 | Top.Science.Programing                        |    3


It would help if you'd show us what result you expect from ordering the above.

Most people would order this by path I think. However that doesn't match your sort column and I can't think of any method that would give results in such an arbitrary order as you seem to be specifying - unless you set it by hand like you do.

Alban Hertroys

--
Screwing up is an excellent way to attach something to the ceiling.


!DSPAM:737,4bcc9b1e10415135793547!

Ltree - how to sort nodes on parent node

От:
cojack <xcojack@gmail.com>
Дата:
Hello,
Im here because Oleg Bartunov invite me to this mailing list. Im searching 
for help with ltree module, in todo list (in this module) is Better 
documentation, since 2003 year, no one make something more for this. Whats 
is the problem? With example from manual about ltree, we have some data in 
our table, now add some row to table for Science node, and we will have 
something like this:

 id |                     path                      | sort                                                                                                   
----+-----------------------------------------------+------                                                                                                  
  1 | Top                                           |    1                                                                                                   
  2 | Top.Science                                   |    1                                                                                                   
  3 | Top.Science.Astronomy                         |    1                                                                                                   
  4 | Top.Science.Astronomy.Astrophysics            |    1                                                                                                   
  5 | Top.Science.Astronomy.Cosmology               |    2                                                                                                   
  6 | Top.Hobbies                                   |    2                                                                                                   
  7 | Top.Hobbies.Amateurs_Astronomy                |    2                                                                                                   
  8 | Top.Collections                               |    3
  9 | Top.Collections.Pictures                      |    1
 10 | Top.Collections.Pictures.Astronomy            |    1
 11 | Top.Collections.Pictures.Astronomy.Stars      |    1
 12 | Top.Collections.Pictures.Astronomy.Galaxies   |    2
 13 | Top.Collections.Pictures.Astronomy.Astronauts |    3
 15 | Top.Science.Programing                        |    3

Sort column, is added by my self, because Im trying to sort those columns, 
but I don't know how. depesz from irc show me example how to sort this data 
with creating ordering column in the fly:

WITH RECURSIVE rec AS (
SELECT *, btrim(to_char( sort, '0000000' )) AS ordering FROM tree WHERE 
nlevel(path) = 1
UNION ALL
SELECT t2.*, t1.ordering || '/' || btrim(to_char( t2.sort, '0000000' )) AS 
ordering FROM rec t1, tree t2 WHERE t1.path @> t2.path AND nlevel(t1.path) + 
1 = nlevel(t2.path)
)
SELECT id, subpath(path, -1) AS title, nlevel(path) AS depth, sort FROM rec 
ORDER BY ordering;

But I'm not sure it's the best way to sort this columns, so Im wrinting here 
for help and some examples, or improve the ltree manual with more example.

-- 
Regards,
cojack.

Re: Ltree - how to sort nodes on parent node

От:
cojack <xcojack@gmail.com>
Дата:
> Alban Hertroys wrote:
>
> It would help if you'd show us what result you expect from ordering the
> above.
> 
> Most people would order this by path I think. However that doesn't match
> your sort column and I can't think of any method that would give results
> in such an arbitrary order as you seem to be specifying - unless you set
> it by hand like you do.
> 
> Alban Hertroys
> 
> --
> Screwing up is an excellent way to attach something to the ceiling.
> 
> 
> !DSPAM:737,4bcc9b1e10415135793547!
> 
> 
> 
Yes, you have right, for example I create new idea of stored data in table:

here is a paste: http://pastebin.com/4pX5cM7j -- never expired link

As you can see, I have noodes with numeric type, those nodes present a sort 
position by self. And If I type ORDER BY path; I will have data like I want 
to have: http://pastebin.com/R4z01LC5 -- never expired link

Again, you can see now grouped data in his nodes, this is the outputed data 
I wanted. If you know better way to make this WITHOUT recursive queries, 
give me a hint.

-- 
Regards,
cojack.

Re: Ltree - how to sort nodes on parent node

От:
cojack <xcojack@gmail.com>
Дата:
> Alban Hertroys wrote:
> 
> 
> Aha, looks like you want to sort each tree level by some user-specified
> order.
> 
> You should realise that ltree was contributed before Postgres supported
> (recursive) CTE's. If you're using ltree in combination with recursive
> CTE's you're doing twice the work that you need to do - ltree was created
> as a means to make recursive queries possible in the first place.
> 
> I think you have basically two ways to go about this:
> 
> 1). The way you're doing this in your new examples should work, although
> I'd probably make the ordering numbers part of the category names and
> split those off when I read them. For example:
>          27 | 1|Top
>          28 | 1|Top.1|Science
>          29 | 1|Top.2|Hobby
>          30 | 1|Top.3|Colors
>          31 | 1|Top.1|Science.1|Physics
>          32 | 1|Top.1|Science.2|Chemistry
>          33 | 1|Top.1|Science.3|Biology
>          34 | 1|Top.1|Science.4|History
>          35 | 1|Top.2|Hobby.1|Fishing
>          36 | 1|Top.2|Hobby.2|Football
>          37 | 1|Top.3|Colors.1|Black
>          38 | 1|Top.3|Colors.2|Red
>          39 | 1|Top.3|Colors.3|Blue
>          40 | 1|Top.1|Science.5|Archeology
>          41 | 1|Top.2|Hobby.3|Swimming
>          42 | 1|Top.3|Colors.4|Gray
>          43 | 1|Top.3|Colors.5|Purple
>          44 | 1|Top.3|Colors.6|Brown
>          45 | 1|Top.2|Hobby.4|Climbing
> 
> 
> Alban Hertroys
> 
> --
> Screwing up is an excellent way to attach something to the ceiling.
> 
> 
> !DSPAM:737,4bcd773910411833268189!
> 
> 
> 
My and your first example doesn't work fine at all, why? Becouse when we add 
more thank 10 sub nodes in some node, the 10 node will not be after 9, but 
after 1 before 2, and this is not good idea to set sort in path. I think the 
best idea for this will be create other column, with also ltree data type 
and stored inside a sort/ordering data. Like:

1
1.1
1.1.1
1.1.2
1.1.3

And while selected it from table, just cast it to int. I'll check this and 
his performance after I return from work.

I am not interested about recursive queries, i think this kill ltree idea.

-- 
Regards,
cojack.

Re: Ltree - how to sort nodes on parent node

От:
Harald Fuchs <hari.fuchs@gmail.com>
Дата:
In article <1F96E061-713C-4929-A7D9-278E5B608EE1@solfertje.student.utwente.nl>,
Alban Hertroys  writes:

> On 20 Apr 2010, at 18:05, Harald Fuchs wrote:
>> Here's a working version:
>> 
>> WITH RECURSIVE tree (path, category, sort_order, parent) AS (
>> SELECT category, category, sort_order::text, parent
>> FROM node
>> WHERE parent IS NULL
>> UNION ALL
>> SELECT t.path || '.' || n.category,
>> n.category,
>> t.sort_order || '.' || n.sort_order,
>> n.parent
>> FROM tree t
>> JOIN node n ON n.parent = t.category
>> )
>> SELECT path
>> FROM tree
>> ORDER BY sort_order

> May be, but then you're just re-inventing ltree again.

Not quite - with proper normalization you're storing the path elements
only once and create the ltree-style paths on the fly.

> I'm pretty sure this must be possible without adding convoluted
> things like casting sort orders to text (which can for example cause
> issues like '10' ending up between '1' and '2').

Ah, you're right.  I think _some_ convolution is still needed because
we must remember the sort order for each path element.

> Since this is 8.4 anyway (CTE's after all), can't the sorting be
> done using a windowing function or something? We have recursion now,
> there's got to be a proper solution, I just can't get my mind around
> it right now.

I don't think windowing functions will help here.  Anyway, here's a
complete example which also deals with the 1/10/2 issue you mentioned
above:

CREATE TABLE node (
  id serial NOT NULL,
  category text NOT NULL,
  sort_order int NOT NULL,
  parent int NULL REFERENCES node (id),
  PRIMARY KEY (id)
);

CREATE UNIQUE INDEX node_pc_uq ON node (parent, category);

-- Enforce unambiguous sorting
CREATE UNIQUE INDEX node_ps_uq ON node (parent, sort_order);

COPY node (id, category, sort_order, parent) FROM stdin;
1	Top	1	\N
2	Science	1	1
3	Physics	1	2
4	Chemistry	2	2
5	Biology	3	2
6	History	4	2
7	Archeology	5	2
8	Hobby	2	1
9	Fishing	1	8
10	Football	2	8
11	Swimming	3	8
12	Climbing	4	8
13	Colors	3	1
14	Black	1	13
15	Red	2	13
16	Blue	3	13
17	Gray	4	13
18	Purple	5	13
19	Brown	6	13
\.

WITH RECURSIVE tree (path, id, sort_order, parent) AS (
  SELECT category, id, ARRAY[sort_order], parent
  FROM node
  WHERE parent IS NULL
UNION ALL
  SELECT t.path || '.' || n.category, n.id,
         t.sort_order || n.sort_order,
         n.parent
  FROM tree t
  JOIN node n ON n.parent = t.id
)
SELECT path, id, sort_order, parent
FROM tree
ORDER BY sort_order;

Re: Ltree - how to sort nodes on parent node

От:
Harald Fuchs <hari.fuchs@gmail.com>
Дата:
In article <59670B22-30CB-4E6E-83C8-C1D1036C9B2A@solfertje.student.utwente.nl>,
Alban Hertroys  writes:

> 2). Drop the ltree column and go with a truly recursive approach, something like this:

> CREATE TABLE node (
> 	category	text	NOT NULL PRIMARY KEY,
> 	sort_order	int	NOT NULL,
> 	parent		text	REFERENCES tree (category)
> 					ON UPDATE CASCADE
> 					ON DELETE CASCADE
> );

> WITH RECURSIVE tree AS (
> 	SELECT *
> 	  FROM node
> 	 WHERE parent IS NULL

> 	UNION ALL

> 	SELECT node.*
> 	  FROM tree, node
> 	 WHERE node.parent = tree.category
> 	 ORDER BY sort_order
> )
> SELECT * FROM tree;

Here's a working version:

  WITH RECURSIVE tree (path, category, sort_order, parent) AS (
    SELECT category, category, sort_order::text, parent
    FROM node
    WHERE parent IS NULL
  UNION ALL
    SELECT t.path || '.' || n.category,
           n.category,
           t.sort_order || '.' || n.sort_order,
           n.parent
    FROM tree t
    JOIN node n ON n.parent = t.category
  )
  SELECT path
  FROM tree
  ORDER BY sort_order

Re: Ltree - how to sort nodes on parent node

От:
Peter Hunsberger <peter.hunsberger@gmail.com>
Дата:
On Tue, Apr 20, 2010 at 1:58 PM, Alban Hertroys
 wrote:
> On 20 Apr 2010, at 11:59, cojack wrote:
>
>
>> I am not interested about recursive queries, i think this kill ltree idea.
>
>
> And IMHO it should. ltree is from a time when we didn't have any other means to describe data organised as a tree in Postgres. Navigating a tree is inherently recursive, so recursion is most likely the proper way to go about it.
>
> A solution omitting recursion (like ltree) can be faster, but you will run into limitations like the one you're currently struggling with.
>
> A solution with recursive queries will probably be more flexible and allows for referential integrity without having to write your own triggers and stuff - for example, what happens if you decide that Archeology isn't a Science but a Colour? What makes sure it's child-nodes get moved into Colors as well?
>

I've only been peripherally following this thread, so the following
may be overkill for the requirements, but the non-recursive / flat
query, solution is usually the set / subset pattern.  It's been
popularized by Joe Celko and he has gone as far as writing a book on
the topic "Trees and hierarchies in SQL for smarties".  If you don't
have many requirements for reordering the tree  this solution works
well.   It can be more of a pain if you need a GUI for tree management
(but can be done).  We use this type of solution to manage trees up to
about 100,000 nodes in size with good performance.  Other
non-recursive solutions include Vadim Tropashko's (now with Oracle)
Nested Interval Tree Encoding methods, which map directly to the
dotted path (1.1.3) type tree notations in the examples in this thread
and are a variation on the set / subset models.

-- 
Peter Hunsberger
FAQ