Re: Ltree - how to sort nodes on parent node

In article <1F96E061-713C-4929-A7D9-278E5B608EE1(at)solfertje(dot)student(dot)utwente(dot)nl>,
Alban Hertroys <dalroi(at)solfertje(dot)student(dot)utwente(dot)nl> 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;