Dimensional Benchmarking of SQL for Fixed-Depth Hierarchies

In my recent article,Dimensional Benchmarking of Bracket Parsing SQL I showed how it was much more efficient to to solve a particular database querying problem using a database function than by two other pure SQL methods. I have also written articles using recursive PL/SQL functions to traverse network or hierarchical data structures, such as PL/SQL Pipelined Function for Network Analysis.

Networks or hierarchies of arbitrary depth are difficult to traverse in SQL without using recursion. However, there also exist hierarchies of fixed and fairly small depths, and these can be traversed either recursively or by a sequence of joins for each of the levels. In this article I compare the performance characteristics of three traversal methods, two recursive and one non-recursive, using my own benchmarking package (A Framework for Dimensional Benchmarking of SQL Performance), on a test problem of a fixed level organization structure hierarchy, with 5 levels for performance testing and 3 levels for functional testing.

The three queries tested were:

  • JNS_QRY: Sequence of joins
  • PLF_QRY: Recursive pipelined function
  • RSF_QRY: Recursive subquery factors

Fixed Level Hierarchy Problem Definition

A hierarchy is assumed in which there are a number of root records, and at each level a parent can have multiple child records and a child can also have multiple parents. Each level in the hierarchy corresponds to an entity of a particular type. Each parent-child record is associated with a numerical factor, and the products of these propagate down the levels.

The problem considered is to report all root/leaf combinations with their associated products. There may of course be multiple paths between any root and leaf, and in a real world example one would likely want to aggregate. However, in order to keep it simple and focus on the traversal performance, I do not perform any aggregation.

Test Data Structure

Tables

CREATE TABLE orgs ( id              NUMBER NOT NULL, 
                    org_level       NUMBER NOT NULL, 
                    org_name        VARCHAR2(100) NOT NULL,
                    CONSTRAINT      org_pk PRIMARY KEY (id))
/
DROP TABLE org_structure
/
CREATE TABLE org_structure (
                    id              NUMBER NOT NULL, 
                    struct_level    NUMBER NOT NULL, 
                    org_id          NUMBER NOT NULL, 
                    child_org_id    NUMBER NOT NULL,
                    fact            NUMBER,
                    CONSTRAINT      ost_pk PRIMARY KEY (id))
/
CREATE INDEX ost_N1 ON org_structure (org_id)
/
CREATE INDEX ost_N2 ON org_structure (child_org_id)
/

Functional Test Data

To simplify functional validation a 3-level hierarchy was taken, with a relatively small number of records. The functional test data were generated by the same automated approach used for performance testing. The fact number was obtained as a random number betwee 0 and 1, and to keep it simple, duplicate pairs were permitted.

The test data were parametrised by width and depth as follows (the exact logic is a little complicated, but can be seen in the code itself):

  • Width corresponds to a percentage increase in the number of child entities relative to the number of parents
  • Depth corresponds to the proportion of the parent entity records a child is (randomly) assigned. Each child has a minimum of 1 parent (lowest depth), and a maximum of all parent entities (highest depth)
Test Data

orgs

        ID  ORG_LEVEL ORG_NAME
---------- ---------- ----------------------------------------------------------------------------------------------------
         1          1 L1 Org 1
         2            L1 Org 2
         3            L1 Org 3
         4          2 L2 Org 1
         5            L2 Org 2
         6            L2 Org 3
         7            L2 Org 4
         8            L2 Org 5
         9            L2 Org 6
        10          3 L3 Org 1
        11            L3 Org 2
        12            L3 Org 3
        13            L3 Org 4
        14            L3 Org 5
        15            L3 Org 6
        16            L3 Org 7
        17            L3 Org 8
        18            L3 Org 9
        19            L3 Org 10
        20            L3 Org 11
        21            L3 Org 12

21 rows selected.

org_structure

        ID STRUCT_LEVEL     ORG_ID CHILD_ORG_ID       FACT
---------- ------------ ---------- ------------ ----------
        25            1          2            4 .765337854
        26                       1            5 .157198428
        27                       2            6 .012739872
        28                       3            7  .75268798
        29                       2            8 .647269295
        30                       2            9 .972586624
         1            2          6           10 .290389829
         2                       7           10 .717844734
         3                       6           11 .909068079
         4                       7           11 .876644977
         5                       9           12  .93576597
         6                       6           12 .097462542
         7                       8           13 .316926046
         8                       8           13 .169842496
         9                       6           14 .765946795
        10                       4           14 .831552357
        11                       8           15 .110940017
        12                       7           15 .295163716
        13                       5           16 .171097557
        14                       5           16 .827432202
        15                       7           17 .339382023
        16                       7           17 .644889466
        17                       7           18 .955594058
        18                       5           18 .668546163
        19                       7           19 .785709973
        20                       6           19 .507321616
        21                       8           20 .511548918
        22                       7           20 .523510327
        23                       6           21 .242612715
        24                       5           21 .561006179

30 rows selected.

Result

ROOT_ORG   LEAF_ORG   FACT_PRODUCT
---------- ---------- ------------
L1 Org 1   L3 Org 12          0.09
L1 Org 1   L3 Org 7           0.03
L1 Org 1   L3 Org 7           0.13
L1 Org 1   L3 Org 9           0.11
L1 Org 2   L3 Org 1           0.00
L1 Org 2   L3 Org 10          0.01
L1 Org 2   L3 Org 11          0.33
L1 Org 2   L3 Org 12          0.00
L1 Org 2   L3 Org 2           0.01
L1 Org 2   L3 Org 3           0.00
L1 Org 2   L3 Org 3           0.91
L1 Org 2   L3 Org 4           0.11
L1 Org 2   L3 Org 4           0.21
L1 Org 2   L3 Org 5           0.01
L1 Org 2   L3 Org 5           0.64
L1 Org 2   L3 Org 6           0.07
L1 Org 3   L3 Org 1           0.54
L1 Org 3   L3 Org 10          0.59
L1 Org 3   L3 Org 11          0.39
L1 Org 3   L3 Org 2           0.66
L1 Org 3   L3 Org 6           0.22
L1 Org 3   L3 Org 8           0.26
L1 Org 3   L3 Org 8           0.49
L1 Org 3   L3 Org 9           0.72

24 rows selected.

All queries returned the expected results above.

Performance Test Data

The performance test data were created in the same way as the functional test data, but with 5 levels, and with 10 root organizations.

The test data sets used a grid of width and depth values of (100, 120, 140, 160, 180), which resulted in output records as below:

Sequence of joins (JNS_QRY)

SELECT o1.org_name root_org,
       o5.org_name leaf_org,
       s1.fact * s2.fact * s3.fact * s4.fact fact_product
  FROM org_structure s1
  JOIN org_structure s2
    ON s2.org_id = s1.child_org_id
  JOIN org_structure s3
    ON s3.org_id = s2.child_org_id
  JOIN org_structure s4
    ON s4.org_id = s3.child_org_id
  JOIN orgs o1
    ON o1.id = s1.org_id
  JOIN orgs o5
    ON o5.id = s4.child_org_id
 WHERE s1.struct_level = 1
 ORDER BY o1.org_name, o5.org_name, s1.fact * s2.fact * s3.fact * s4.fact

Plan hash value: 914261573

----------------------------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation               | Name          | Starts | E-Rows | A-Rows |   A-Time   | Buffers | Reads  | Writes |  OMem |  1Mem | Used-Mem | Used-Tmp|
----------------------------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT        |               |      1 |        |   3330K|00:00:11.12 |     718 |  51157 |  51157 |       |       |          |         |
|   1 |  SORT ORDER BY          |               |      1 |   3905K|   3330K|00:00:11.12 |     718 |  51157 |  51157 |   454M|  7031K|  163M (1)|     400K|
|*  2 |   HASH JOIN             |               |      1 |   3905K|   3330K|00:00:01.76 |     714 |      0 |      0 |  1483K|  1483K| 1524K (0)|         |
|   3 |    TABLE ACCESS FULL    | ORGS          |      1 |    944 |    944 |00:00:00.01 |       7 |      0 |      0 |       |       |          |         |
|*  4 |    HASH JOIN            |               |      1 |   3905K|   3330K|00:00:00.45 |     707 |      0 |      0 |  2733K|  1562K| 4103K (0)|         |
|   5 |     TABLE ACCESS FULL   | ORG_STRUCTURE |      1 |  27288 |  27288 |00:00:00.01 |     175 |      0 |      0 |       |       |          |         |
|*  6 |     HASH JOIN           |               |      1 |    133K|  30520 |00:00:00.02 |     532 |      0 |      0 |   917K|   917K| 3834K (0)|         |
|*  7 |      HASH JOIN          |               |      1 |   4575 |    780 |00:00:00.01 |     357 |      0 |      0 |  1062K|  1062K| 1260K (0)|         |
|*  8 |       HASH JOIN         |               |      1 |     56 |     56 |00:00:00.01 |     182 |      0 |      0 |  1185K|  1185K| 1184K (0)|         |
|*  9 |        TABLE ACCESS FULL| ORG_STRUCTURE |      1 |     56 |     56 |00:00:00.01 |     175 |      0 |      0 |       |       |          |         |
|  10 |        TABLE ACCESS FULL| ORGS          |      1 |    944 |    944 |00:00:00.01 |       7 |      0 |      0 |       |       |          |         |
|  11 |       TABLE ACCESS FULL | ORG_STRUCTURE |      1 |  27288 |  27288 |00:00:00.01 |     175 |      0 |      0 |       |       |          |         |
|  12 |      TABLE ACCESS FULL  | ORG_STRUCTURE |      1 |  27288 |  27288 |00:00:00.01 |     175 |      0 |      0 |       |       |          |         |
----------------------------------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("O5"."ID"="S4"."CHILD_ORG_ID")
   4 - access("S4"."ORG_ID"="S3"."CHILD_ORG_ID")
   6 - access("S3"."ORG_ID"="S2"."CHILD_ORG_ID")
   7 - access("S2"."ORG_ID"="S1"."CHILD_ORG_ID")
   8 - access("O1"."ID"="S1"."ORG_ID")
   9 - filter("S1"."STRUCT_LEVEL"=1)

Note
-----
   - this is an adaptive plan

Notes on JNS_QRY

It is interesting to note that all joins in the execution plan are hash joins, and in the sequence you would expect. The first three are in the default join 'sub-order' that defines whether the joined table or the prior rowset (the default) is used to form the hash table, while the last two are in the reverse order, corresponding to the swap_join_inputs hint. I wrote a short note on that subject, A Note on Oracle Join Orders and Hints, last year, and have now written an article using the largest data point in the current problem to explore performance variation across the possible sub-orders.

Recursive pipelined function (PLF_QRY)

CREATE OR REPLACE TYPE org_struct_rec_type IS OBJECT (struct_level NUMBER, org_id NUMBER, fact_product NUMBER);
/
CREATE TYPE org_struct_lis_type IS VARRAY(32767) OF org_struct_rec_type;
/
CREATE OR REPLACE FUNCTION Org_Products (p_org_id PLS_INTEGER, p_fact_product NUMBER) RETURN org_struct_lis_type PIPELINED IS
  l_org_struct_lis  org_struct_lis_type;
BEGIN

  FOR rec_org_struct IN (
      SELECT child_org_id,
             p_fact_product * fact fact_product,
             struct_level
      FROM org_structure
      WHERE org_id = p_org_id) LOOP

    PIPE ROW (org_struct_rec_type (rec_org_struct.struct_level, rec_org_struct.child_org_id, rec_org_struct.fact_product));

    FOR rec_org_struct_child IN (SELECT struct_level, org_id, fact_product FROM TABLE (Org_Products (rec_org_struct.child_org_id, rec_org_struct.fact_product))) LOOP

      PIPE ROW (org_struct_rec_type (rec_org_struct_child.struct_level, rec_org_struct_child.org_id, rec_org_struct_child.fact_product));

    END LOOP;

  END LOOP;

END  Org_Products;

SELECT o1.org_name root_org,
       o5.org_name leaf_org,
       t.fact_product fact_product
  FROM org_structure s
  CROSS APPLY TABLE (Org_Products (s.child_org_id, s.fact)) t
  JOIN orgs o1
    ON o1.id = s.org_id
  JOIN orgs o5
    ON o5.id = t.org_id
 WHERE s.struct_level = 1
   AND t.struct_level = 4
 ORDER BY o1.org_name, o5.org_name, t.fact_product

Plan hash value: 1216100769

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                            | Name          | Starts | E-Rows | A-Rows |   A-Time   | Buffers | Reads  | Writes |  OMem |  1Mem | Used-Mem | Used-Tmp|
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                     |               |      1 |        |   3330K|00:03:38.10 |    9072K|  51163 |  51163 |       |       |          |         |
|   1 |  SORT ORDER BY                       |               |      1 |   4574 |   3330K|00:03:38.10 |    9072K|  51163 |  51163 |   455M|  7037K|  163M (1)|     400K|
|*  2 |   HASH JOIN                          |               |      1 |   4574 |   3330K|00:03:15.00 |    9072K|      0 |      0 |  1483K|  1483K| 1489K (0)|         |
|   3 |    TABLE ACCESS FULL                 | ORGS          |      1 |    944 |    944 |00:00:00.01 |       7 |      0 |      0 |       |       |          |         |
|   4 |    NESTED LOOPS                      |               |      1 |   4574 |   3330K|00:03:13.28 |    9072K|      0 |      0 |       |       |          |         |
|*  5 |     HASH JOIN                        |               |      1 |     56 |     56 |00:00:00.01 |     182 |      0 |      0 |  1160K|  1160K| 1199K (0)|         |
|*  6 |      TABLE ACCESS FULL               | ORG_STRUCTURE |      1 |     56 |     56 |00:00:00.01 |     175 |      0 |      0 |       |       |          |         |
|   7 |      TABLE ACCESS FULL               | ORGS          |      1 |    944 |    944 |00:00:00.01 |       7 |      0 |      0 |       |       |          |         |
|*  8 |     COLLECTION ITERATOR PICKLER FETCH| ORG_PRODUCTS  |     56 |     82 |   3330K|00:03:12.84 |    9072K|      0 |      0 |       |       |          |         |
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("O5"."ID"=VALUE(KOKBF$))
   5 - access("O1"."ID"="S"."ORG_ID")
   6 - filter("S"."STRUCT_LEVEL"=1)
   8 - filter(VALUE(KOKBF$)=4)

Outer Loop Function Query - Explan Plan only

SELECT child_org_id,
       fact fact_product,
       struct_level
  FROM org_structure
  WHERE org_id = 1

Query Plan
---------------------------------------------------
SELECT STATEMENT   Cost = 41
  TABLE ACCESS BY INDEX ROWID BATCHED ORG_STRUCTURE
    INDEX RANGE SCAN OST_N1

Notes on PLF_QRY

For simplicity a stand-alone database function was used here. The query execution plan was obtained by the benchmarking framework and the highest data point plan listed. The query within the function was extracted and an explain Plan performed manually, which showed the expected index range scan.

Recursive subquery factors (RSF_QRY)

WITH rsf (root_org_id, child_org_id, fact_product, lev) AS
(
SELECT org_id, child_org_id, fact, 1
  FROM org_structure
 WHERE struct_level = 1
UNION ALL
SELECT r.root_org_id,
       s.child_org_id,
       r.fact_product * s.fact,
       r.lev + 1
  FROM rsf r
  JOIN org_structure s
    ON s.org_id = r.child_org_id
)
SELECT o1.org_name root_org,
       o5.org_name leaf_org,
       r.fact_product fact_product
  FROM rsf r
  JOIN orgs o1
    ON o1.id = r.root_org_id
  JOIN orgs o5
    ON o5.id = r.child_org_id
 WHERE r.lev = 4
 ORDER BY o1.org_name, o5.org_name, r.fact_product

Plan hash value: 248371385

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                                    | Name          | Starts | E-Rows | A-Rows |   A-Time   | Buffers | Reads  | Writes |  OMem |  1Mem | Used-Mem | Used-Tmp|
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                             |               |      1 |        |   3330K|00:00:55.92 |      39M|  73843 |  93808 |       |       |          |         |
|   1 |  SORT ORDER BY                               |               |      1 |   4631 |   3330K|00:00:55.92 |      39M|  73843 |  93808 |   454M|  7030K|  162M (1)|     400K|
|*  2 |   HASH JOIN                                  |               |      1 |   4631 |   3330K|00:00:45.06 |      39M|  22678 |  42643 |  1519K|  1519K| 1555K (0)|         |
|   3 |    TABLE ACCESS FULL                         | ORGS          |      1 |    944 |    944 |00:00:00.01 |       7 |      0 |      0 |       |       |          |         |
|*  4 |    HASH JOIN                                 |               |      1 |   4631 |   3330K|00:00:43.14 |      39M|  22678 |  42643 |  1519K|  1519K| 1546K (0)|         |
|   5 |     TABLE ACCESS FULL                        | ORGS          |      1 |    944 |    944 |00:00:00.01 |       7 |      0 |      0 |       |       |          |         |
|*  6 |     VIEW                                     |               |      1 |   4631 |   3330K|00:00:41.58 |      39M|  22678 |  42643 |       |       |          |         |
|   7 |      UNION ALL (RECURSIVE WITH) BREADTH FIRST|               |      1 |        |   3361K|00:00:40.72 |      39M|  22678 |  42643 |   173M|  4426K|   97M (0)|         |
|*  8 |       TABLE ACCESS FULL                      | ORG_STRUCTURE |      1 |     56 |     56 |00:00:00.01 |     175 |      0 |      0 |       |       |          |         |
|*  9 |       HASH JOIN                              |               |      4 |   4575 |   3361K|00:00:06.43 |     701 |  22678 |  22935 |   282M|    10M|   56M (1)|     191K|
|  10 |        RECURSIVE WITH PUMP                   |               |      4 |        |   3361K|00:00:00.56 |       1 |  19708 |      0 |       |       |          |         |
|  11 |        TABLE ACCESS FULL                     | ORG_STRUCTURE |      4 |  27288 |    109K|00:00:00.02 |     700 |      0 |      0 |       |       |          |         |
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("O5"."ID"="R"."CHILD_ORG_ID")
   4 - access("O1"."ID"="R"."ROOT_ORG_ID")
   6 - filter("R"."LEV"=4)
   8 - filter("STRUCT_LEVEL"=1)
   9 - access("S"."ORG_ID"="R"."CHILD_ORG_ID")

Note
-----
   - this is an adaptive plan

Notes on RSF_QRY

This uses a v11.2 feature.

Performance Testing Results

Deep Slice Elapsed Times [d=180, w=(100, 120, 140, 160, 180)]

  • JNS_QRY is faster than RSF_QRY, which is faster than PLF_QRY at all data points
  • PLF_QRY tracks the number of output records very closely. This is likely because the function executes a query at every node in the hierarchy that uses an indexed search.
  • The pure SQL methods scale better through being able to do full table scans, and avoiding multiple query executions

Deep Slice Elapsed - CPU Times

The elapsed time minus the CPU times are shown in the first graph below, followed by the disk writes. The disk writes (and reads) are computed as the maximum values across the explain plan at the given data point, and are obtained from the system view v$sql_plan_statistics_all. The benchmarking framework gathers these and other statistics automatically.

  • The graphs show how the elapsed time minus CPU times track the disk accesses reasonably well
  • RSF_QRY does nearly twice as much disk writes as the other two

Wide Slice Results [w=180, d=(100, 120, 140, 160, 180)]

The performance characteristics of the three methods across the wide slice data points are pretty similar to those across the deep slice. The graphs are shown below.

Conclusions

  • For the example problem taken, the most efficient way to traverse fixed-level hierarchies is by a sequence of joins
  • Recursive methods are significantly worse, and the recursive function is especially inefficient because it performs large numbers of query executions using indexed searches, instead of full scans
  • The execution plans for the join sequence query gives an example of a sequence of hash joins with different choices of 'join inputs'. It may be interesting to explore the different performance characteristics of the possible choices using hints in a subsequent article (Benchmarking of Hash Join Options in SQL for Fixed-Depth Hierarchies)
  • The output log is attached, and all code is on my GitHub project, GitHub: dim_bench_sql_oracle

Batch_Org






Leave a Reply

Your email address will not be published. Required fields are marked *