View · Index
No registered users in community rubick
in last 10 minutes

Using tree_sortkey for hierarchical queries in Postgres

Using tree_sortkey for hierarchical queries

Tree_sortkey is a method of making hierarchical queries. It is built in to OpenACS, and is the prefered equivalent to Oracle's CONNECT BY statement. I believe you can even make joins with tree_sortkey, which is an improvement on CONNECT BY.

I've written a newer version of this that will be included in the OpenACS documentation, in the advanced tutorial section. So I'd use that before I used this.

Hierarchical queries seem like scary things, but they're surprisingly easy with Postgres. If you have a table or view with a parent_id column, this will work:


        repeat(:indent_pattern, (tree_level(tree_sortkey) - 2)* :indent_factor) as indent,
        FROM pm_projectsx 
        ORDER BY tree_sortkey
Here's a simplified definition for this view:
                 View "public.pm_projectsx"
       Column        |           Type           | Modifiers 
 item_id             | integer                  | 
 project_name        | character varying(255)   | 
 tree_sortkey        | bit varying              | 
It looks like that's all you need to make it work. You will need to add the tree_sortkey column to your table, of type bit varying.

Here's a tree_sortkey with a join in it:

        repeat(:indent_pattern, (tree_level(p.tree_sortkey) - 5)* :indent_factor) as indent,
        p.parent_id as folder_id,
        FROM pm_projectsx p, cr_items i
        WHERE p.project_id = i.live_revision
        ORDER BY i.tree_sortkey

And another one, from Don Baccus:

Here's an example, pulling all of the children for a given parent:

  select children.*
  from some_table parent, some_table children
  where children.tree_sorktey between parent.tree_sortkey and tree_right(parent.tree_sortkey)
    and parent.tree_sortkey <> children.tree_sortkey
    and parent.key = :the_parent_key;
This example does not include the parent. To return the entire subtree including the parent, leave out the non-equals clause:
  select subtree.*
  from some_table parent, some_table subtree
  where subtree.tree_sorktey between parent.tree_sortkey and tree_right(parent.tree_sortkey)
    and parent.key = :the_parent_key;
This rather long thread explains how tree_sortkeys work. This paper describes the technique for tree_sortkeys, although the OpenACS implementation has a few differences in the implementation, to make it work for many languages and the LIKE construct in Postgres.

Thanks to Ola, Dan, and Don.


Note that you can use the tree_level() function to determine what the level you are at is.