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