I presented this at the Ireland Oracle User Group Conference on 24 March 2017 in Dublin.
I presented this at the Ireland Oracle User Group Conference on 24 March 2017 in Dublin.
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:
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):
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)]
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.
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
I noticed an interesting thread on OTN recently, Matching ( in a string. It’s about using SQL to find matching bracket pairs (technically ‘parentheses’ but ‘brackets’ is shorter, and it makes no difference to the SQL). Incidentally, I found recently that nested bracket expressions are a nice way of compactly representing the structure of complex hash join execution plans, A Note on Oracle Join Orders and Hints.
I thought it would be interesting to run some of the solution queries through my benchmarking package to test performance (A Framework for Dimensional Benchmarking of SQL Performance). I decided to consider only the queries that addressed multiple records, and the form of the problem that requires returning record uid, opening and closing bracket positions, plus the substring enclosed. These were by ‘mathguy’ and ‘Peter vd Zwan’, and I made very minor tweaks for consistency. I also wrote a query myself using PL/SQL in an inline SQL function using the new (v12.1) ‘WITH Function’ functionality, and copied this to a version using a pipelined database function to check for any performance differences. The four queries tested were then:
Bracket Pair Definition
Consider a function (BrDiff) defined at each character position as the difference between the number of opening and closing brackets to the left of, or at, that position.
A closing bracket closes an opening bracket if it is the first closing bracket where BrDiff is 1 less than BrDiff at the opening bracket. If all brackets are in some pair, then the expression can be considered well-formed.
This can be illustrated with a diagram for the fourth functional example below.
Test Problem
BRACKET_STRINGS Table
CREATE TABLE bracket_strings (id NUMBER, str VARCHAR2(4000)) /
Functional Test Data
I took four of mathguy’s test records, excluding the (deliberately) badly-formed strings, and which included some embedded returns:
Test Data ID STR ------- ---------------------------------------- 1 ((Hello ( Hi Hi hi ( A B C ( D)) (EF) why Whwy whyhhh ) ) ) 2 (1+3*(3-1) + 3*(2+1)) 3 ()()*(())a()(()) 4 b0(b1(b2(b3(x))(xy)))
Result
ID O_POS C_POS STR ------- ---------- ---------- ---------------------------------------- 1 2 60 ((Hello ( Hi Hi hi ( A B C ( D)) (EF) why Whwy whyhhh ) ) ) 1 3 58 (Hello ( Hi Hi hi ( A B C ( D)) (EF) why Whwy whyhhh ) ) 1 10 56 ( Hi Hi hi ( A B C ( D)) (EF) why Whwy whyhhh ) 1 21 33 ( A B C ( D)) 1 29 32 ( D) 1 35 38 (EF) 2 1 21 (1+3*(3-1) + 3*(2+1)) 2 6 10 (3-1) 2 16 20 (2+1) 3 1 2 () 3 3 4 () 3 6 9 (()) 3 7 8 () 3 11 12 () 3 13 16 (()) 3 14 15 () 4 3 21 (b1(b2(b3(x))(xy))) 4 6 20 (b2(b3(x))(xy)) 4 9 15 (b3(x)) 4 12 14 (x) 4 16 19 (xy) 21 rows selected.
All queries returned the expected results above.
Performance Test Data
Each test set consisted of 100 records with the str column containing the brackets expression dependent on width (w) and depth (d) parameters, as follows:
When w=d the pairs are fully nested, and when d=0 there is no nesting, just a sequence of ‘(123)’ stringss.
This choice of test data sets allows us to see if both number of brackets, and bracket nesting have any effect on performance.
The output from the test queries therefore consists of 100*w records with a record identifier and a bracketed string. For performance testing purposes the benchmarking framework writes the results to a file in csv format, while counting only the query steps in the query timing results.
All the queries showed strong time correlation with width, with smaller correlation with depth.
Connect By, Analytics, Regex Query (CBL_QRY)
WITH d ( id, str, pos ) as ( select id, str, regexp_instr(str, '\(|\)', 1, level) from bracket_strings connect by level <= length(str) - length(translate(str, 'x()', 'x')) and prior id = id and prior sys_guid() is not null ), p ( id, str, pos, flag, l_ct, ct ) as ( select id, str, pos, case substr(str, pos, 1) when '(' then 1 else -1 end, sum(case substr(str, pos, 1) when '(' then 1 end) over (partition by id order by pos), sum(case substr(str, pos, 1) when '(' then 1 else -1 end) over (partition by id order by pos) from d ), f ( id, str, pos, flag, l_ct, ct, o_ct ) as ( select id, str, pos, flag, l_ct, ct + case flag when 1 then 0 else 1 end as ct, row_number() over (partition by id, flag, ct order by pos) from p ) select /*+ CBL_QRY gather_plan_statistics */ id, min(case when flag = 1 then pos end) as o_pos, min(case when flag = -1 then pos end) as c_pos, Substr (str, min(case when flag = 1 then pos end), min(case when flag = -1 then pos end) - min(case when flag = 1 then pos end) + 1) str from f group by id, str, ct, o_ct order by 1, 2 Plan hash value: 2736674058 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------ | Id | Operation | Name | Starts | E-Rows | A-Rows | A-Time | Buffers | Reads | Writes | OMem | 1Mem | Used-Mem | Used-Tmp| ------------------------------------------------------------------------------------------------------------------------------------------------------------------------ | 0 | SELECT STATEMENT | | 1 | | 40000 |00:00:16.30 | 43 | 40000 | 40000 | | | | | | 1 | SORT ORDER BY | | 1 | 100 | 40000 |00:00:16.30 | 43 | 40000 | 40000 | 21M| 1702K| 19M (0)| | | 2 | HASH GROUP BY | | 1 | 100 | 40000 |00:00:16.24 | 43 | 40000 | 40000 | 85M| 7293K| 85M (0)| | | 3 | VIEW | | 1 | 100 | 80000 |00:01:19.35 | 43 | 40000 | 40000 | | | | | | 4 | WINDOW SORT | | 1 | 100 | 80000 |00:01:19.27 | 43 | 40000 | 40000 | 175M| 4458K| 97M (1)| 157K| | 5 | VIEW | | 1 | 100 | 80000 |00:01:05.90 | 40 | 20000 | 20000 | | | | | | 6 | WINDOW SORT | | 1 | 100 | 80000 |00:01:05.86 | 40 | 20000 | 20000 | 175M| 4457K| 97M (0)| 157K| | 7 | VIEW | | 1 | 100 | 80000 |00:00:09.77 | 38 | 0 | 0 | | | | | |* 8 | CONNECT BY WITHOUT FILTERING| | 1 | | 80000 |00:00:02.26 | 38 | 0 | 0 | 267K| 267K| 237K (0)| | | 9 | TABLE ACCESS FULL | BRACKET_STRINGS | 1 | 100 | 100 |00:00:00.01 | 38 | 0 | 0 | | | | | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Predicate Information (identified by operation id): --------------------------------------------------- 8 - access("ID"=PRIOR NULL)
Notes on CBL_QRY
Subquery d uses regexp_instr with connect by to generate rows for each bracket.
Connect By, Match_Recognize Query (MRB_QRY)
WITH b as ( select substr(str,level,1) s ,level n ,id ,str from bracket_strings connect by id = prior id and substr(str,level,1) is not null and prior sys_guid() is not null ) select /*+ MRB_QRY gather_plan_statistics */ id ,o_pos ,c_pos ,substr(str,o_pos,c_pos - o_pos + 1) str from b MATCH_RECOGNIZE ( partition by id ORDER BY n MEASURES str as str ,FIRST( N) AS o_pos ,LAST( N) AS c_pos one ROW PER MATCH AFTER MATCH SKIP to next row PATTERN (ob (ob | nb | cb)*? lcb) DEFINE ob as ob.s = '(' ,cb as cb.s = ')' ,nb as nb.s not in ('(',')') ,lcb as lcb.s = ')' and (count(ob.s) = count(cb.s) + 1) ) MR Plan hash value: 2214599770 ----------------------------------------------------------------------------------------------------------------------------------------------------------- | Id | Operation | Name | Starts | E-Rows | A-Rows | A-Time | Buffers | Reads | Writes | OMem | 1Mem | Used-Mem | ----------------------------------------------------------------------------------------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 1 | | 40000 |00:03:38.26 | 40 | 4473K| 50075 | | | | | 1 | SORT ORDER BY | | 1 | 100 | 40000 |00:03:38.26 | 40 | 4473K| 50075 | 21M| 1702K| 19M (0)| | 2 | VIEW | | 1 | 100 | 40000 |00:04:48.17 | 40 | 4473K| 50075 | | | | | 3 | MATCH RECOGNIZE SORT | | 1 | 100 | 40000 |00:04:48.16 | 40 | 4473K| 50075 | 440M| 6922K| 163M (0)| | 4 | VIEW | | 1 | 100 | 200K|00:00:04.65 | 38 | 0 | 0 | | | | |* 5 | CONNECT BY WITHOUT FILTERING| | 1 | | 200K|00:00:04.54 | 38 | 0 | 0 | 267K| 267K| 237K (0)| | 6 | TABLE ACCESS FULL | BRACKET_STRINGS | 1 | 100 | 100 |00:00:00.01 | 38 | 0 | 0 | | | | ----------------------------------------------------------------------------------------------------------------------------------------------------------- Predicate Information (identified by operation id): --------------------------------------------------- 5 - access("ID"=PRIOR NULL)
Notes on MRB_QRY
This uses the v12.1 feature Match_Recognize operating on the charcaters in the string after conversion to rows.
With PL/SQL Function, Arrays Query (WFB_QRY)
WITH FUNCTION Parse_Brackets (p_str VARCHAR2) RETURN bra_lis_type IS /* WFB_QRY */ c_n_ob CONSTANT PLS_INTEGER := Length (p_str) - Length (Replace (p_str, '(', '')); l_ob_lis SYS.ODCINumberList := SYS.ODCINumberList(); l_cb_lis SYS.ODCINumberList := SYS.ODCINumberList(); TYPE b_rec_type IS RECORD (pos INTEGER, diff INTEGER); TYPE b_lis_type IS VARRAY(32767) OF b_rec_type; l_b_lis b_lis_type := b_lis_type(NULL); l_bra_lis bra_lis_type := bra_lis_type(); n_b PLS_INTEGER := 0; n_ob PLS_INTEGER := 0; n_cb PLS_INTEGER := 0; l_chr VARCHAR2(1); l_o_diff PLS_INTEGER; BEGIN IF c_n_ob = 0 THEN RETURN NULL; END IF; l_ob_lis.EXTEND (c_n_ob); l_bra_lis.EXTEND (c_n_ob); l_cb_lis.EXTEND (c_n_ob); l_b_lis.EXTEND (c_n_ob + c_n_ob); FOR i IN 1..Length (p_str) LOOP l_chr := Substr (p_str, i, 1); IF l_chr NOT IN ('(', ')') THEN CONTINUE; END IF; n_b := n_b + 1; l_b_lis(n_b).pos := i; IF l_chr = '(' THEN n_ob := n_ob + 1; l_ob_lis(n_ob) := n_b; ELSE n_cb := n_cb + 1; l_cb_lis(n_cb) := n_b; END IF; l_b_lis(n_b).diff := n_ob - n_cb; END LOOP; FOR i IN 1..n_ob LOOP l_o_diff := l_b_lis (l_ob_lis(i)).diff; FOR j IN 1..n_cb LOOP IF l_b_lis (l_cb_lis(j)).pos < l_b_lis (l_ob_lis(i)).pos THEN CONTINUE; END IF; IF l_o_diff = l_b_lis (l_cb_lis(j)).diff + 1 THEN l_bra_lis(i) := bra_rec_type (l_b_lis(l_ob_lis(i)).pos, l_b_lis(l_cb_lis(j)).pos, Substr (p_str, l_b_lis(l_ob_lis(i)).pos, l_b_lis(l_cb_lis(j)).pos - l_b_lis(l_ob_lis(i)).pos + 1)); EXIT; END IF; END LOOP; END LOOP; RETURN l_bra_lis; END; SELECT b.id, t.o_pos, t.c_pos, t.str FROM bracket_strings b OUTER APPLY TABLE (Parse_Brackets (b.str)) t ORDER BY 1, 2
Notes on WFB_QRY
This uses the v12.1 feature whereby a PL/SQL function can be included directly in a query.
Pipelined PL/SQL Function, Arrays Query (PFB_QRY)
WFB_QRY – Pipelined Function
CREATE OR REPLACE TYPE bra_rec_type IS OBJECT (o_pos INTEGER, c_pos INTEGER, str VARCHAR2(4000)); / CREATE TYPE bra_lis_type IS VARRAY(4000) OF bra_rec_type; / FUNCTION Parse_Brackets (p_str VARCHAR2) RETURN bra_lis_type PIPELINED IS c_n_ob CONSTANT PLS_INTEGER := Length (p_str) - Length (Replace (p_str, '(', '')); l_ob_lis SYS.ODCINumberList := SYS.ODCINumberList(); l_cb_lis SYS.ODCINumberList := SYS.ODCINumberList(); TYPE b_rec_type IS RECORD (pos INTEGER, diff INTEGER); TYPE b_lis_type IS VARRAY(32767) OF b_rec_type; l_b_lis b_lis_type := b_lis_type(NULL); l_bra_lis bra_lis_type := bra_lis_type(); n_b PLS_INTEGER := 0; n_ob PLS_INTEGER := 0; n_cb PLS_INTEGER := 0; l_chr VARCHAR2(1); l_o_diff PLS_INTEGER; BEGIN IF c_n_ob = 0 THEN RETURN; END IF; l_ob_lis.EXTEND (c_n_ob); l_bra_lis.EXTEND (c_n_ob); l_cb_lis.EXTEND (c_n_ob); l_b_lis.EXTEND (c_n_ob + c_n_ob); FOR i IN 1..Length (p_str) LOOP l_chr := Substr (p_str, i, 1); IF l_chr NOT IN ('(', ')') THEN CONTINUE; END IF; n_b := n_b + 1; l_b_lis(n_b).pos := i; IF l_chr = '(' THEN n_ob := n_ob + 1; l_ob_lis(n_ob) := n_b; ELSE n_cb := n_cb + 1; l_cb_lis(n_cb) := n_b; END IF; l_b_lis(n_b).diff := n_ob - n_cb; END LOOP; FOR i IN 1..n_ob LOOP l_o_diff := l_b_lis (l_ob_lis(i)).diff; FOR j IN 1..n_cb LOOP IF l_b_lis (l_cb_lis(j)).pos < l_b_lis (l_ob_lis(i)).pos THEN CONTINUE; END IF; IF l_o_diff = l_b_lis (l_cb_lis(j)).diff + 1 THEN PIPE ROW (bra_rec_type (l_b_lis(l_ob_lis(i)).pos, l_b_lis(l_cb_lis(j)).pos, Substr (p_str, l_b_lis(l_ob_lis(i)).pos, l_b_lis(l_cb_lis(j)).pos - l_b_lis(l_ob_lis(i)).pos + 1))); EXIT; END IF; END LOOP; END LOOP; END Parse_Brackets; Plan hash value: 3367347570 --------------------------------------------------------------------------------------------------------------------------------------------- | Id | Operation | Name | Starts | E-Rows | A-Rows | A-Time | Buffers | OMem | 1Mem | Used-Mem | --------------------------------------------------------------------------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 1 | | 40000 |00:00:01.17 | 38 | | | | | 1 | SORT ORDER BY | | 1 | 816K| 40000 |00:00:01.17 | 38 | 21M| 1702K| 19M (0)| | 2 | NESTED LOOPS OUTER | | 1 | 816K| 40000 |00:00:16.80 | 38 | | | | | 3 | TABLE ACCESS FULL | BRACKET_STRINGS | 1 | 100 | 100 |00:00:00.01 | 38 | | | | | 4 | VIEW | VW_LAT_D4FD8C38 | 100 | 8168 | 40000 |00:00:01.13 | 0 | | | | | 5 | COLLECTION ITERATOR PICKLER FETCH| PARSE_BRACKETS | 100 | 8168 | 40000 |00:00:01.10 | 0 | | | | ---------------------------------------------------------------------------------------------------------------------------------------------
PFB_QRY – Query
SELECT /*+ PFB_QRY gather_plan_statistics */ b.id id, t.o_pos o_pos, t.c_pos c_pos, t.str str FROM bracket_strings b OUTER APPLY TABLE (Strings.Parse_Brackets (b.str)) t ORDER BY b.id, t.o_pos Plan hash value: 3367347570 --------------------------------------------------------------------------------------------------------------------------------------------- | Id | Operation | Name | Starts | E-Rows | A-Rows | A-Time | Buffers | OMem | 1Mem | Used-Mem | --------------------------------------------------------------------------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 1 | | 40000 |00:00:01.15 | 38 | | | | | 1 | SORT ORDER BY | | 1 | 816K| 40000 |00:00:01.15 | 38 | 21M| 1702K| 19M (0)| | 2 | NESTED LOOPS OUTER | | 1 | 816K| 40000 |00:00:01.95 | 38 | | | | | 3 | TABLE ACCESS FULL | BRACKET_STRINGS | 1 | 100 | 100 |00:00:00.01 | 38 | | | | | 4 | VIEW | VW_LAT_D4FD8C38 | 100 | 8168 | 40000 |00:00:01.51 | 0 | | | | | 5 | COLLECTION ITERATOR PICKLER FETCH| PARSE_BRACKETS | 100 | 8168 | 40000 |00:00:01.50 | 0 | | | | ---------------------------------------------------------------------------------------------------------------------------------------------
Notes on PFB_QRY
This uses PL/SQL pipelined database function which is called in the query.
Performance Testing Results
Key
If CPU time (y) is proportional to the varying dimension (x), for data points 1 and 2, we would have:
y = kx
and so, for any two data points 1 and 2:
y2.x1/(y1.x2) = 1
We can take the actual value of the linear ratio as a marker for linear proportionality or not.
If CPU time (y) is proportional to the varying dimension (x), for data points 1 and 2, we would have:
y = kx.x
and so, for any two data points 1 and 2:
y2.x1.x1/(y1.x2.x2) = 1
We can take the actual value of the quadratic ratio as a marker for quadratic proportionality or not.
Depth fixed, at small width point; width varies: d=100, w=(100, 200, 300, 400)
Notes on Results for Fixed Depth
Width fixed at high depth point; depth varies: w=400, d=(0, 100, 200, 300, 400)
Notes on Results for Fixed Width