View · Index

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:

Examples

        SELECT
        item_id,
        repeat(:indent_pattern, (tree_level(tree_sortkey) - 2)* :indent_factor) as indent,
        project_name
        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:

        SELECT
        p.item_id,
        repeat(:indent_pattern, (tree_level(p.tree_sortkey) - 5)* :indent_factor) as indent,
        p.parent_id as folder_id,
        p.project_name
        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.

Misc.

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