Bottom-up hierarchical root path query recipe in oracle


Oracle supports hierarchical querying since long and has continuously extended the set of available features, i.e. pseudo-columns, path generation, leaf sorting by name, etc. With 11gR2, Oracle even complements with the ANSI SQL standard approach: the CONNECT BY syntax for hierarchical querying that can now be replaced by the ANSI SQL standard Recursive Subquery Factoring clause, see Oracle RDBMS 11gR2 – goodbye Connect By or: the end of hierarchical querying as we know it for more information.
However, talking about hierarchical querying with Oracle always implies a top-down traversion (see another post on that subject from a couple of years ago that did not provided a PL/SQL ready solution as Implementing bottom-up path traversal for hierarchical tables). You start (START WITH) at some root node(s) of your choice and dive into the branches and leaves (CONNECT BY) by connecting child-nodes to parent-nodes until the final leaf has been consumed (check CONNECT_BY_ISLEAF) or a certain LEVEL has been reached by filter. There is tons of examples out there showing this in action. Here is just some simple code example to start off with, employing SYS_CONNECT_BY_PATH, introducing root- to leaf-node path generation over the child-to-parent relationship between columns T.P_ID and T.ID.

> select * from t1;
        ID|NAME    |      P_ID
----------|--------|----------
         1|A       |         0
         2|B       |         1
         3|C       |         1
         4|D       |         3

Test data above, hierachy below.

> select id, name, p_id, sys_connect_by_path(name, '/') as name_path from t1
  2  start with p_id = 0 connect by prior id = p_id;

        ID|NAME    |      P_ID|NAME_PATH
----------|--------|----------|-------------
         1|A       |         0|/A
         2|B       |         1|/A/B
         3|C       |         1|/A/C
         4|D       |         3|/A/C/D

There is going to be trouble though, usually for large data sets, iff someone is only interested in a single root path or, say, a couple of root paths. Given a unique leaf ID, there is no way to circumvent a full top-down traversal from the upmost root node in line to retrieve the root path thoroughly. Even using CONNECT_BY_ROOT will not help out here because this root data is always relative to the actual START WITH entry condition (see the following code fragment). Iff, uncertainly, the upmost root node is known in advance, a top-down traversal from this (perfect) starting point may still deliver a plethora of paths to leaves having another ID and are in need to be cut off using a where-clause filter.

> select id, name, p_id, sys_connect_by_path(name, '/') as name_path,
  2    connect_by_root id as r_id from t1
  3  start with p_id = 1 connect by prior id = p_id;

        ID|NAME    |      P_ID|NAME_PATH    |      R_ID
----------|--------|----------|-------------|----------
         2|B       |         1|/B           |         2
         3|C       |         1|/C           |         3
         4|D       |         3|/C/D         |         3

What now? Just traversing bottom-up from the given unique leaf ID? Jep, proper approach but only half of the business because, goofy it is, the returned paths will be reversed now.

> select id, name, p_id, sys_connect_by_path(name, '/') as name_path,
  2    level as name_level from t1
  3  start with id = 4 connect by id = prior p_id;

        ID|NAME    |      P_ID|NAME_PATH    |NAME_LEVEL
----------|--------|----------|-------------|----------
         4|D       |         3|/D           |         1
         3|C       |         1|/D/C         |         2
         1|A       |         0|/D/C/A       |         3

Will not trip us up that much, for here is the reverse path reversal trick that incorporates LISTAGG (or WM_CONCAT for Oracle < 11g) and the LEVEL pseudo-column as well as, iff you like, mimics SYS_CONNECT_BY_PATH quite cheaply by only stepping up a directed unary path up to root, no sideways, nothing to litter, just number-of-levels == number-of-nodes (inclusive) touched. The gain is so obvious that i will not bore anyone beyond belief with SET AUTOT[RACE] {ON | OFF | TRACE[ONLY]} [EXP[LAIN]] [STAT[ISTICS]] and things.

> with tmp as (
  2    select name, level as name_level from t1
  3    start with id = 4 connect by id = prior p_id )
  4  select '/' || listagg(name, '/') within group (order by name_level desc)
  5    as name_path
  6  from tmp;

NAME_PATH
-------------
/A/C/D

Putting this into some PL/SQL block finds us at ease when it comes to managing root path generation for a unique or small selection of leaves in a hierachical data set.

create or replace function p1 (
  i_id in number,
  i_sep in varchar2 default '/'
) return varchar2 authid definer
as
  v_res varchar2(4000);
begin
  with tmp as (
    select name, level as name_level from t1
    start with id = i_id connect by id = prior p_id )
  select i_sep || listagg(name, i_sep) within group (order by name_level desc)
    into v_res from tmp;
  return v_res;
end;
/

Finally:

> select id, name, p_id, p1(id) as name_path from t1 where id = 4;

        ID|NAME    |      P_ID|NAME_PATH
----------|--------|----------|-------------
         4|D       |         3|/A/C/D

Enjoy, Peter

Advertisements

One comment

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s