September 29, 2009: On summing up values of nodes of a hierarchical query

Here's a table that stores hierarchical information. Its hierarchical because its column id_p (standing for id of parent) references the column id of the same table.

create table hierarchical_values (
  id    number   primary key,
  id_p           references hierarchical_values,
  info  varchar2(10),
  amt   number
);

This table is filled with some data. Note that the column amt is only filled for leaves.

insert into hierarchical_values values ( 1, null, 'a'                    , null);
insert into hierarchical_values values ( 4,    1,   'ad'                 , null);
insert into hierarchical_values values (10,    4,     'adj'              , null);
insert into hierarchical_values values (32,   10,         'ADJ1'         ,    6);
insert into hierarchical_values values (33,   10,         'ADJ2'         ,    7);
insert into hierarchical_values values (34,   10,         'ADJ3'         ,    3);
insert into hierarchical_values values (35,   10,         'ADJ4'         ,    1);
insert into hierarchical_values values (11,    4,     'adk'              , null);
insert into hierarchical_values values (29,   11,         'ADK1'         ,    3);
insert into hierarchical_values values (30,   11,         'ADK2'         ,    4);
insert into hierarchical_values values (31,   11,         'ADK3'         ,    5);
insert into hierarchical_values values (12,    4,     'adl'              , null);
insert into hierarchical_values values (21,   12,       'adlu'           , null);
insert into hierarchical_values values (27,   21,         'ADLU1'        ,    1);
insert into hierarchical_values values (28,   21,         'ADLU2'        ,    2);
insert into hierarchical_values values (22,   12,       'adlv'           , null);
insert into hierarchical_values values (36,   22,         'ADLV1'        ,    2);
insert into hierarchical_values values (37,   22,         'ADLV2'        ,    7);
insert into hierarchical_values values (38,   22,         'ADLV3'        ,    1);
insert into hierarchical_values values (39,   22,         'ADLV4'        ,    4);
insert into hierarchical_values values ( 5,    1,   'ae'                 , null);
insert into hierarchical_values values (13,    5,     'aem'              , null);
insert into hierarchical_values values (45,   13,       'AEM1'           ,   22);
insert into hierarchical_values values (46,   13,       'AEM2'           ,   18);
insert into hierarchical_values values (47,   13,       'AEM3'           ,   20);
insert into hierarchical_values values (14,    5,     'aen'              , null);
insert into hierarchical_values values (43,   14,       'AEN1'           ,   14);
insert into hierarchical_values values (44,   14,       'AEN2'           ,    6);
insert into hierarchical_values values (15,    5,     'aeo'              , null);
insert into hierarchical_values values (48,   15,       'AEO1'           ,   20);
insert into hierarchical_values values ( 6,    1,   'af'                 , null);
insert into hierarchical_values values (49,    6,     'AF1'              , 1000);
insert into hierarchical_values values ( 2, null, 'b'                    , null);
insert into hierarchical_values values ( 7,    2,   'bg'                 , null);
insert into hierarchical_values values (16,    7,     'bgp'              , null);
insert into hierarchical_values values (50,   16,       'BGP1'           ,   25);
insert into hierarchical_values values (51,   16,       'BGP2'           ,   75);
insert into hierarchical_values values (17,    7,     'bgq'              , null);
insert into hierarchical_values values (53,   17,       'BGQ1'           ,    5);
insert into hierarchical_values values (18,    7,     'bgr'              , null);
insert into hierarchical_values values (52,   18,       'BGR1'           ,   27);
insert into hierarchical_values values ( 8,    2,   'bh'                 , null);
insert into hierarchical_values values ( 3, null, 'c'                    , null);
insert into hierarchical_values values ( 9,    3,   'ci'                 , null);
insert into hierarchical_values values (19,    9,     'cis'              , null);
insert into hierarchical_values values (23,   19,       'cisw'           , null);
insert into hierarchical_values values (24,   23,         'ciswx'        , null);
insert into hierarchical_values values (26,   24,           'ciswxz'     , null);
insert into hierarchical_values values (40,   26,             'CISWXZ1'  ,   15);
insert into hierarchical_values values (41,   26,             'CISWXZ2'  ,   16);
insert into hierarchical_values values (42,   26,             'CISWXZ3'  ,   14);
insert into hierarchical_values values (25,   23,         'ciswy'        , null);
insert into hierarchical_values values (55,   25,           'CISWY1'     ,   30);
insert into hierarchical_values values (20,    9,     'cit'              , null);
insert into hierarchical_values values (54,   20,       'CIT1'           ,    9);

In order to make it possible to view the hierarchical data in the table more appealing for the human eye, I create a view:

create view hierarchical_values_v as
  select 
    rownum  rownum_,
    level   level_,
    id,
    info,
    substr(lpad (' ', (level-1)*2) || info,1,30) info_,
    amt
  from
    hierarchical_values
  start with
    id_p is null
  connect by
    prior id = id_p
;

Selecting from the view gives me:

set pagesize 5000

select
  substr(info_,1,30),
  amt
from 
  hierarchical_values_v 
order by
  rownum_ /*desc*/
;

SUBSTR(INFO_,1,30)                    AMT
------------------------------ ----------
a
  ad
    adj
      ADJ1                              6
      ADJ2                              7
      ADJ3                              3
      ADJ4                              1
    adk
      ADK1                              3
      ADK2                              4
      ADK3                              5
    adl
      adlu
        ADLU1                           1
        ADLU2                           2
      adlv
        ADLV1                           2
        ADLV2                           7
        ADLV3                           1
        ADLV4                           4
  ae
    aem
      AEM1                             22
      AEM2                             18
      AEM3                             20
    aen
      AEN1                             14
      AEN2                              6
    aeo
      AEO1                             20
  af
    AF1                              1000
b
  bg
    bgp
      BGP1                             25
      BGP2                             75
    bgq
      BGQ1                              5
    bgr
      BGR1                             27
  bh
c
  ci
    cis
      cisw
        ciswx
          ciswxz
            CISWXZ1                    15
            CISWXZ2                    16
            CISWXZ3                    14
        ciswy
          CISWY1                       30
    cit
      CIT1                              9

Now, I'd like to sum up amt for each node. For instance, the sum of amt for node adlv should be 14 (Which is the sum of the leaves ADLV1, ADLV2, ADLV3 and ADLV4, or 2+7+1+4 respectively). In the same spirit, the sum of amt for node cisw should be 75 which is the sum of the nodes ciswx and ciswy which (in recursive turn) is the some of CISWXZ1, CISWXZ2, CISWXZ3 and CISWY1 or 15+16+14+30.

I can achieve this goal by selecting from the tree if it is turned upside-down (by ordering by rownum_ desc)...

set pagesize 5000

select
  rownum_,
  level_,
  substr(info_,1,30),
  amt
from 
  hierarchical_values_v 
order by
  rownum_ desc
;

   ROWNUM_     LEVEL_ SUBSTR(INFO_,1,30)                    AMT
---------- ---------- ------------------------------ ----------
        55          4       CIT1                              9
        54          3     cit
        53          6           CISWY1                       30
        52          5         ciswy
        51          7             CISWXZ3                    14
        50          7             CISWXZ2                    16
        49          7             CISWXZ1                    15
        48          6           ciswxz
        47          5         ciswx
        46          4       cisw
        45          3     cis
        44          2   ci
        43          1 c

        ... more records snipped ...

The «trick» is to remember the last record's level_ and to compare it with the actual or current record's level_. Depending on whether the last record's level_ is smaller, equal or greater then the actual level_, three different actions must be performed. In order to keep track of the last record's level_, the variable last_level is used. This variable is initialized with 0.

Also, I need to store the sums of amt for each level_ from 1 through the actual record's level_ - 1. A collection seems to be the appropriate method to do that. So, I create a collection type sum_on_level and a variable (total_sum_on_level) of that type.

I have now everything in order to start iterating over the records:

Read one (1st) record (level_: 4, amt: 9, rownum_: 55)

level_ > last_level: This means, we have to do two «calculations»:

add amt to all elements in total_sum_on_level in the range 1 .. last_level-1.
set the elemens in total_sum_on_level to amt in the range last_level .. level_-1

Since last_level is now 0, nothing can be done for the first step. The second step sets the elements between 0 and 3 (last_level, level_ -1 ) to amt.

The collection total_sum_on_level now looks like

total_sum_on_level
level_:	0	1	2	3	-	-	-	-	-
cumulated sum of amt:	9	9	9	9	-	-	-	-	-

Also, the read record is appended to the result set nodes which now looks like:

nodes
info	amt	rownum_
CIT1	9	55

Finally, last_level is set to level_ (which is 4).

Read one (2nd) record (level_: 3, amt: -, rownum_: 54)

level_ < last_level: This means that we only put one record at the end of nodes. The member amt is set to the value of total_sum_on_level(level_) (which happens to be 9).

So, nodes now looks as:

nodes
info	amt	rownum_
CIT1	9	55
cit	9	54

last_level is set to level_ (which is 3).

Read one (3rd) record (level_: 6, amt: 30, rownum_: 53)

level_ > last_level. First step: add amt to all elements in total_sum_on_level in the range 1 .. last_level-1 (1 .. 2). Second step: set the elements in total_sum_on_level to amt in the range last_level .. level_ - 1.

Thus, total_sum_on_level looks now:

total_sum_on_level
level_:	0	1	2	3	4	5	-	-	-
cumulated sum of amt:	39	39	39	30	30	30	-	-	-

The read record is appended to the result set nodes:

nodes
info	amt	rownum_
CIT1	9	55
cit	9	54
CISWY1	30	53

Read one (4th) record (level_: 5, amt: -, rownum_: 52)

level_ < last_level: Put the record at the end of nodes with member set to the value of total_sum_on_level(level_):

nodes
info	amt	rownum_
CIT1	9	55
cit	9	54
CISWY1	30	53
ciswy	30	52

and set last_level to 5.

Read one (5th) record (level_: 7, amt: 14, rownum_: 51)

level_ > last_level: add amt to total_sum_on_level(1 .. last_level-1) and set total_sum_on_level(last_level .. level_) to amt:

total_sum_on_level
level_:	0	1	2	3	4	5	6	7	-
cumulated sum of amt:	53	53	53	44	44	14	14	14	-

Append the read record to nodes:

nodes
info	amt	rownum_
CIT1	9	55
cit	9	54
CISWY1	30	53
ciswy	30	52
CISWXZ3	14	51

Read one (6th) record (level_: 7, amt: 16, rownum_: 50)

level_ = last_level: This means that we have to cumulate amt to the elements in total_sum_on_level in the range 1 .. level_-1:

total_sum_on_level
level_:	0	1	2	3	4	5	6	7	-
cumulated sum of amt:	69	69	69	60	60	30	30	14	-

and append the read record to nodes:

nodes
info	amt	rownum_
CIT1	9	55
cit	9	54
CISWY1	30	53
ciswy	30	52
CISWXZ3	14	51
CISWXZ2	16	50

Set last_level to 7.

Read one (7th) record (level_: 7, amt: 15, rownum_: 49)

level_ = last_level: again, we have to cumulate amt to the elements in total_sum_on_level in the range 1 .. level_-1:

total_sum_on_level
level_:	0	1	2	3	4	5	6	7	-
cumulated sum of amt:	84	84	84	75	75	45	45	14	-

and append the read record to nodes:

nodes
info	amt	rownum_
CIT1	9	55
cit	9	54
CISWY1	30	53
ciswy	30	52
CISWXZ3	14	51
CISWXZ2	16	50
CISWXZ1	15	49

Read one (8th) record (level_: 6, amt: -, rownum_: 48)

level_ < last_level: Put the record at the end of nodes with member set to the value of total_sum_on_level(level_):

nodes
info	amt	rownum_
CIT1	9	55
cit	9	54
CISWY1	30	53
ciswy	30	52
CISWXZ3	14	51
CISWXZ2	16	50
CISWXZ1	15	49
ciswxz	45	48

If this rules are applied to the entire set, and nodes are then displayed in reversed order, we obtain the desired sums for all nodes.

In order to do this, I create a node object type which keeps track of the summed up values of amt for each node and leaf in the table:

create or replace type node as object (
  info    varchar2(30),
  amt     number,
  rownum_ number
);
/

Also, I want a collection of nodes which will eventually store the values for each record found in hierarchical_values. So, I create an approprate type for it:

create or replace type node_t as table of node;
/

Lastly, I need a procedure that actually filles the nodes into a variable whose type is node_t. This procedure will be the member procedure do_sum of the following object:

create or replace type sum_nodes as object (
  nodes node_t,

  constructor function sum_nodes return self as result,

  member procedure do_sum
);
/

And the specification:

create or replace type body sum_nodes as

  constructor function sum_nodes return self as result is begin
    nodes := node_t();
    return;
  end sum_nodes;

  member procedure do_sum is 
    type  sum_on_level is table of number index by pls_integer;
    total_sum_on_level sum_on_level;

    last_level           number := 0;

  begin

    for r in (
      select level_, rownum_, info_, amt
      from hierarchical_values_v
      order by rownum_ desc
    ) loop

       nodes.extend;

       if      r.level_ < last_level then

               nodes(nodes.count) := node(r.info_, total_sum_on_level(r.level_), r.rownum_);

       elsif   r.level_ = last_level then

               nodes(nodes.count) := node(r.info_, r.amt, r.rownum_);

               for i in 1 .. r.level_-1 loop
                 total_sum_on_level(i) := nvl(total_sum_on_level(i), 0) + nvl(r.amt, 0);
               end loop;


       else -- r.level_ > last_level

               nodes(nodes.count) := node(r.info_, nvl(r.amt, 0), r.rownum_);

               for i in 1 .. last_level - 1 loop
                 total_sum_on_level(i) := total_sum_on_level(i) + nvl(r.amt, 0);
               end loop;

               for i in last_level .. r.level_ - 1 loop
                 total_sum_on_level(i) := nvl(r.amt, 0);
               end loop;

       end if;

       last_level := r.level_;

    end loop;

  end do_sum;

end;
/

In action...

set serveroutput on size 1000000 format wrapped

declare
  s     sum_nodes := sum_nodes();
begin
  s.do_sum;

  for r in (select * from table(s.nodes) t order by t.rownum_) loop
    dbms_output.put_line(rpad(r.info, 30, '.' )|| to_char(r.amt,'9999'));
  end loop;

end;
/

a............................. 1146
  ad..........................   46
    adj.......................   17
      ADJ1....................    6
      ADJ2....................    7
      ADJ3....................    3
      ADJ4....................    1
    adk.......................   12
      ADK1....................    3
      ADK2....................    4
      ADK3....................    5
    adl.......................   17
      adlu....................    3
        ADLU1.................    1
        ADLU2.................    2
      adlv....................   14
        ADLV1.................    2
        ADLV2.................    7
        ADLV3.................    1
        ADLV4.................    4
  ae..........................  100
    aem.......................   60
      AEM1....................   22
      AEM2....................   18
      AEM3....................   20
    aen.......................   20
      AEN1....................   14
      AEN2....................    6
    aeo.......................   20
      AEO1....................   20
  af.......................... 1000
    AF1....................... 1000
b.............................  132
  bg..........................  132
    bgp.......................  100
      BGP1....................   25
      BGP2....................   75
    bgq.......................    5
      BGQ1....................    5
    bgr.......................   27
      BGR1....................   27
  bh..........................    0
c.............................   84
  ci..........................   84
    cis.......................   75
      cisw....................   75
        ciswx.................   45
          ciswxz..............   45
            CISWXZ1...........   15
            CISWXZ2...........   16
            CISWXZ3...........   14
        ciswy.................   30
          CISWY1..............   30
    cit.......................    9
      CIT1....................    9

More on Oracle

This is an on Oracle article. The most current articles of this series can be found here.


	René Nyffenegger's collection of things on the web
	René Nyffenegger on Oracle - Most wanted - Feedback