Re: Ltree - how to sort nodes on parent node

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