Re: tree ordering with varbit - Mailing list pgsql-general

Scott Lamb wrote:
> create table mb.message (
>         message_id      serial primary key,
>         messageroot_id  integer not null references mb.messageroot,
>         parent_id       integer references mb.message (message_id),
>         ...
> );
>
> all of the messages with the same messageroot make a forest. If I wanted
> to sort them hierarchically based when they were posted, I'd want a sort
> key that has their post time prefixed by that of all their ancestors, so
> the greatest ancestor comes first. Or better yet, their IDs, since
> that's unique and means children of two parents that happened to be
> posted at the same time wouldn't be lumped together, and IDs should
> increase as posting times increase.

Do you mean something like this?

regression=# CREATE TABLE connectby_int(keyid int, parent_keyid int);
CREATE TABLE
regression=# \copy connectby_int from 'data/connectby_int.data'
\.
regression=# select * from connectby_int;
  keyid | parent_keyid
-------+--------------
      1 |
      2 |            1
      3 |            1
      4 |            2
      5 |            2
      6 |            4
      7 |            3
      8 |            6
      9 |            5
(9 rows)

regression=# SELECT * FROM connectby('connectby_int', 'keyid', 'parent_keyid',
'2', 0, '~') AS t(keyid int, parent_keyid int, level int, branch text);
  keyid | parent_keyid | level | branch
-------+--------------+-------+---------
      2 |              |     0 | 2
      4 |            2 |     1 | 2~4
      6 |            4 |     2 | 2~4~6
      8 |            6 |     3 | 2~4~6~8
      5 |            2 |     1 | 2~5
      9 |            5 |     2 | 2~5~9
(6 rows)

If so, the connectby() function is in contrib/tablefunc in the
soon-to-be-released version 7.3

There are some imperfections in the way this currently works from the
standpoint of using "branch" to sort, but in many cases it will do pretty much
what you want.

In the next version (i.e. for 7.4) I'll probably add a way to pad each segment
in the branch to a user specified length with a user specified character. The
example above would then look something like:

regression=# SELECT * FROM connectby('connectby_int', 'keyid', 'parent_keyid',
'2', 0, '~', 3, '0') AS t(keyid int, parent_keyid int, level int, branch text);
  keyid | parent_keyid | level | branch
-------+--------------+-------+---------
      2 |              |     0 | 002
      4 |            2 |     1 | 002~004
      6 |            4 |     2 | 002~004~006
      8 |            6 |     3 | 002~004~006~008
      5 |            2 |     1 | 002~005
      9 |            5 |     2 | 002~005~009

That way 010 would sort after 009, instead of before it (10 vs 9).

I didn't really directly answer your questions, but I hope this helps anyway.

Joe