Dimensional Benchmarking of String Splitting SQL

I noticed a question on AskTom last November concerning SQL for splitting delimited strings, Extract domain names from a column having multiple email addresses, a kind of question that arises frequently on the forums. There was some debate between reviewers Rajeshwaran Jeyabal, Stew Ashton and the AskTom guys on whether an XML-based solution performs better or worse than a more ‘classic’ solution based on the Substr and Instr functions and collections. AskTom’s Chris Saxon noted:

For me this just highlights the importance of testing in your own environment with your own data. Just because someone produced a benchmark showing X is faster, doesn’t mean it will be for you.

For me, relative performance is indeed frequently dependent on the size and ‘shape’ of the data used for testing. As I have my own ‘dimensional’ benchmarking framework, A Framework for Dimensional Benchmarking of SQL Performance, I was able to very quickly adapt Rajesh’s test data to benchmark across numbers of records and numbers of delimiters, and I put the results on the thread. I then decided to take the time to expand the scope to include other solutions, and to use more general data sets, where the token lengths vary as well as the number of tokens per record.

In fact the scope expanded quite a bit, as I found more and more ways to solve the problem, and I have only now found the time to write it up. Here is a list of all the queries considered:

Queries using Connect By for row generation

  • MUL_QRY – Cast/Multiset to correlate Connect By
  • LAT_QRY – v12 Lateral correlated Connect By
  • UNH_QRY – Uncorrelated Connect By unhinted
  • RGN_QRY – Uncorrelated Connect By with leading hint
  • GUI_QRY – Connect By in main query using sys_guid trick
  • RGX_QRY – Regular expression function, Regexp_Substr

Queries not using Connect By for row generation

  • XML_QRY – XMLTABLE
  • MOD_QRY – Model clause
  • PLF_QRY – database pipelined function
  • WFN_QRY – ‘WITH’ PL/SQL function directly in query
  • RSF_QRY – Recursive Subquery Factor
  • RMR_QRY – Match_Recognize

Test Problem

DELIMITED_LISTS Table

CREATE TABLE delimited_lists(id INT, list_col VARCHAR2(4000))
/

Functional Test Data

The test data consist of pipe-delimited tokens (‘|’) in a VARCHAR2(4000) column in a table with a separate integer unique identifier. For functional testing we will add a single ‘normal’ record with two tokens, plus four more records designed to validate null-token edge cases as follows:

  1. Normal case, two tokens
  2. Leading null token, then two not null tokens
  3. Trailing null token, after two not null tokens
  4. Two not null tokens, with a null token in the middle
  5. Two null tokens only
     ID LIST_COL
------- ------------------------------------------------------------
      1 token_11|token_12
      2 |token_21|token_22
      3 token_31|token_32|
      4 token_41||token_42
      5 |

Functional Test Results

     ID TOKEN
------- ----------
      1 token_11
      1 token_12
      2
      2 token_21
      2 token_22
      3 token_31
      3 token_32
      3
      4 token_41
      4
      4 token_42
      5
      5

13 rows selected.

All queries returned the expected results above, except that the XML query returned 12 rows with only a single null token returned for record 5. In the performance testing, no null tokens were included, and all queries returned the same results.

Performance Test Data

Each test set consisted of 3,000 records with the list_col column containing the delimited string dependent on width (w) and depth (d) parameters, as follows:

  • Each record contains w tokens
  • Each token contains d characters from the sequence 1234567890 repeated as necessary

The output from the test queries therefore consists of 3,000*w records with a unique identifier and a token of length d. 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.

In Oracle upto version 11.2 VARCHAR2 expressions cannot be longer than 4,000 characters, so I decided to run the framework for four sets of parameters, as follows:

  • Depth fixed, high; width range low: d=18, w=(50,100,150,200)
  • Depth fixed, low; width range high: d=1, w=(450,900,1350,1800)
  • Width fixed, low; depth range high: w=5, d=(195,390,585,780)
  • Width fixed, high; depth range low: w=150, d=(6,12,18,24)

All the queries showed strong time correlation with width, while a few also showed strong correlation with depth.

Queries

All execution plans are from the data point with Width=1800, Depth=1, which has the largest number of tokens per record.

Multiset Query (MUL_QRY)

SELECT d.id   id,
       Substr (d.list_col, Instr ('|' || d.list_col, '|', 1, t.COLUMN_VALUE), Instr (d.list_col || '|', '|', 1, t.COLUMN_VALUE) - Instr ('|' || d.list_col, '|', 1, t.COLUMN_VALUE)) token
  FROM delimited_lists d, 
       TABLE (CAST (MULTISET (SELECT LEVEL FROM DUAL CONNECT BY LEVEL <= Nvl (Length(d.list_col), 0) - Nvl (Length (Replace (d.list_col, '|')), 0) + 1) AS SYS.ODCINumberlist)) t

Plan hash value: 462687286

--------------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                           | Name            | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
--------------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |                 |      1 |        |   5400K|00:01:52.86 |    3009 |       |       |          |
|   1 |  NESTED LOOPS                       |                 |      1 |     24M|   5400K|00:01:52.86 |    3009 |       |       |          |
|   2 |   TABLE ACCESS FULL                 | DELIMITED_LISTS |      1 |   3000 |   3000 |00:00:00.01 |    3009 |       |       |          |
|   3 |   COLLECTION ITERATOR SUBQUERY FETCH|                 |   3000 |   8168 |   5400K|00:01:49.96 |       0 |       |       |          |
|   4 |    CONNECT BY WITHOUT FILTERING     |                 |   3000 |        |   5400K|00:01:48.83 |       0 |  2048 |  2048 | 2048  (0)|
|   5 |     FAST DUAL                       |                 |   3000 |      1 |   3000 |00:00:00.01 |       0 |       |       |          |
--------------------------------------------------------------------------------------------------------------------------------------------

Notes on MUL_QRY

This is the ‘classic’ CONNECT BY solution referred to above, which appears frequently on AskTom and elsewhere, and I copied the version used by Jayesh. The somewhat convoluted casting between subquery and array and back to SQL record via multiset allows the prior table in the from list to be referenced within the inline view, which is otherwise not permitted in versions earlier than 12.1, where the LATERAL keyword was introduced.

Despite this query being regarded as the ‘classic’ CONNECT BY solution to string-splitting, we will find that it is inferior in performance to a query I wrote myself across all data points considered. The new query is also simpler, but is not the most efficient of all methods, as we see later.

Lateral Query (LAT_QRY)

SELECT d.id                id,
       l.subs              token
FROM delimited_lists d
CROSS APPLY (
  SELECT Substr (d.list_col, pos + 1, Lead (pos, 1, 4000) OVER (ORDER BY pos) - pos - 1) subs, pos
    FROM (
    SELECT Instr (d.list_col, '|', 1, LEVEL) pos
      FROM DUAL
    CONNECT BY
      LEVEL <= Length (d.list_col) - Nvl (Length (Replace (d.list_col, '|')), 0) + 1
    )
) l

Plan hash value: 631504984

-----------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                        | Name            | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
-----------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                 |                 |      1 |        |   5400K|00:15:41.97 |    3009 |       |       |          |
|   1 |  NESTED LOOPS                    |                 |      1 |   3000 |   5400K|00:15:41.97 |    3009 |       |       |          |
|   2 |   TABLE ACCESS FULL              | DELIMITED_LISTS |      1 |   3000 |   3000 |00:00:00.01 |    3009 |       |       |          |
|   3 |   VIEW                           | VW_LAT_2D0B8FC8 |   3000 |      1 |   5400K|00:02:02.67 |       0 |       |       |          |
|   4 |    WINDOW SORT                   |                 |   3000 |      1 |   5400K|00:02:00.59 |       0 | 43008 | 43008 |38912  (0)|
|   5 |     VIEW                         |                 |   3000 |      1 |   5400K|00:01:58.78 |       0 |       |       |          |
|   6 |      CONNECT BY WITHOUT FILTERING|                 |   3000 |        |   5400K|00:01:48.53 |       0 |  2048 |  2048 | 2048  (0)|
|   7 |       FAST DUAL                  |                 |   3000 |      1 |   3000 |00:00:00.01 |       0 |       |       |          |
-----------------------------------------------------------------------------------------------------------------------------------------

Notes on LAT_QRY

This query is taken from Splitting Strings: Proof!, and uses a v12.1 new feature, described with examples in LATERAL Inline Views. The new feature allows you to correlate an inline view directly without the convoluted Multiset code, and can also be used with the keywords CROSS APPLY instead of LATERAL. It’s sometimes regarded as having peformance advantages, but in this context we will see that avoiding this correlation altogether is best for performance.

Row-generator Query, Unhinted and Hinted (UNH_QRY and RGN_QRY)

Unhinted Query

WITH row_gen AS (
        SELECT LEVEL rn FROM DUAL CONNECT BY LEVEL <= 
            (SELECT Max (Nvl (Length(list_col), 0) - Nvl (Length (Replace (list_col,'|')), 0) + 1)
               FROM delimited_lists)
)
SELECT d.id   id,
       Substr (d.list_col, Instr ('|' || d.list_col, '|', 1, r.rn), Instr (d.list_col || '|', '|', 1, r.rn) - Instr ('|' || d.list_col, '|', 1, r.rn)) token
  FROM delimited_lists d
  JOIN row_gen r
    ON r.rn <= Nvl (Length(d.list_col), 0) - Nvl (Length (Replace (d.list_col,'|')), 0) + 1

Plan hash value: 747926158

---------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                      | Name            | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
---------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT               |                 |      1 |        |   5400K|00:01:55.35 |    2717K|       |       |          |
|   1 |  NESTED LOOPS                  |                 |      1 |    150 |   5400K|00:01:55.35 |    2717K|       |       |          |
|   2 |   VIEW                         |                 |      1 |      1 |   1800 |00:00:07.39 |    1509 |       |       |          |
|   3 |    CONNECT BY WITHOUT FILTERING|                 |      1 |        |   1800 |00:00:07.39 |    1509 |  2048 |  2048 | 2048  (0)|
|   4 |     FAST DUAL                  |                 |      1 |      1 |      1 |00:00:00.01 |       0 |       |       |          |
|   5 |     SORT AGGREGATE             |                 |      1 |      1 |      1 |00:00:00.06 |    1509 |       |       |          |
|   6 |      TABLE ACCESS FULL         | DELIMITED_LISTS |      1 |   3000 |   3000 |00:00:00.01 |    1509 |       |       |          |
|*  7 |   TABLE ACCESS FULL            | DELIMITED_LISTS |   1800 |    150 |   5400K|00:01:53.61 |    2716K|       |       |          |
---------------------------------------------------------------------------------------------------------------------------------------

Execution Plan with Hint /*+ leading (d) */

Plan hash value: 1241630378

----------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                       | Name            | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
----------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                |                 |      1 |        |   5400K|00:00:02.37 |    3018 |       |       |          |
|   1 |  MERGE JOIN                     |                 |      1 |    150 |   5400K|00:00:02.37 |    3018 |       |       |          |
|   2 |   SORT JOIN                     |                 |      1 |   3000 |   3000 |00:00:00.07 |    1509 |    11M|  1318K|   10M (0)|
|   3 |    TABLE ACCESS FULL            | DELIMITED_LISTS |      1 |   3000 |   3000 |00:00:00.01 |    1509 |       |       |          |
|*  4 |   SORT JOIN                     |                 |   3000 |      1 |   5400K|00:00:01.42 |    1509 |   160K|   160K|  142K (0)|
|   5 |    VIEW                         |                 |      1 |      1 |   1800 |00:00:07.37 |    1509 |       |       |          |
|   6 |     CONNECT BY WITHOUT FILTERING|                 |      1 |        |   1800 |00:00:07.37 |    1509 |  2048 |  2048 | 2048  (0)|
|   7 |      FAST DUAL                  |                 |      1 |      1 |      1 |00:00:00.01 |       0 |       |       |          |
|   8 |      SORT AGGREGATE             |                 |      1 |      1 |      1 |00:00:00.06 |    1509 |       |       |          |
|   9 |       TABLE ACCESS FULL         | DELIMITED_LISTS |      1 |   3000 |   3000 |00:00:00.01 |    1509 |       |       |          |
----------------------------------------------------------------------------------------------------------------------------------------

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

   4 - access(INTERNAL_FUNCTION("R"."RN")<=NVL(LENGTH("D"."LIST_COL"),0)-NVL(LENGTH(REPLACE("D"."LIST_COL",'|')),0)+1)
       filter(INTERNAL_FUNCTION("R"."RN")<=NVL(LENGTH("D"."LIST_COL"),0)-NVL(LENGTH(REPLACE("D"."LIST_COL",'|')),0)+1)

Notes on UNH_QRY and RGN_QRY

I wrote the UNH_QRY query in an attempt to avoid the convoluted Multiset approach of the ‘classic’ solution. The reason for the use of arrays and Multiset seems to be that, while we need to ‘generate’ multiple rows for each source row, the number of rows generated has to vary by source record and so the row-generating inline view computes the number of tokens for each record in its where clause.

The use of row-generating subqueries is quite common, but in other cases one often has a fixed number of rows to generate, as in data densification scenarios for example. It occurred to me that, although we don’t know the number to generate, we do have an upper bound, dependent on the maximum number of characters, and we could generate that many in a subquery, then join only as many as are required to the source record.

This approach resulted in a simpler and more straightforward query, but it turned out in its initial form to be very slow. The execution plan above shows that the row generator is driving a nested loops join within which a full scan is performed on the table. The CBO is not designed to optimise this type of algorithmic query, so I added a leading hint to reverse the join order, and this resulted in much better performance. In fact, as we see later the hinted query outperforms the other CONNECT BY queries, including the v12.1 LAT_QRY query at all data points considered.

sys_guid Query (GUI_QRY)

WITH guid_cby AS (
  SELECT id, level rn, list_col,Instr ('|' || d.list_col, '|', 1, LEVEL) pos
    FROM delimited_lists d
  CONNECT BY prior id = id and prior sys_guid() is not null and
    LEVEL <= Length (d.list_col) - Nvl (Length (Replace (d.list_col, '|')), 0) + 1
)
SELECT id  id, 
       Substr (list_col, pos, Lead (pos, 1, 4000) OVER (partition by id ORDER BY pos) - pos - 1) token
  FROM guid_cby

Plan hash value: 240527573

-------------------------------------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                      | Name            | Starts | E-Rows | A-Rows |   A-Time   | Buffers | Reads  | Writes |  OMem |  1Mem | Used-Mem | Used-Tmp|
-------------------------------------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT               |                 |      1 |        |   5400K|00:14:12.07 |   77412 |   2404K|   2404K|       |       |          |         |
|   1 |  WINDOW SORT                   |                 |      1 |   3000 |   5400K|00:14:12.07 |   77412 |   2404K|   2404K|    20G|    45M|  163M (0)|      18M|
|   2 |   VIEW                         |                 |      1 |   3000 |   5400K|00:04:07.47 |    1509 |      0 |      0 |       |       |          |         |
|*  3 |    CONNECT BY WITHOUT FILTERING|                 |      1 |        |   5400K|00:03:55.99 |    1509 |      0 |      0 |    12M|  1343K|   10M (0)|         |
|   4 |     TABLE ACCESS FULL          | DELIMITED_LISTS |      1 |   3000 |   3000 |00:00:00.01 |    1509 |      0 |      0 |       |       |          |         |
-------------------------------------------------------------------------------------------------------------------------------------------------------------------

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

   3 - access("ID"=PRIOR NULL)

Notes on GUI_QRY

This query also generates rows using CONNECT BY, but differs from the others shown by integrating the row-generation code with the main rowset and avoiding a separate subquery against DUAL. This seems to be a more recent approach than the traditional Multiset solution. It uses a trick involving the system function sys_guid() to avoid the ‘connect by cycle’ error that you would otherwise get, as explained in this OTN thread: Reg : sys_guid()
.

Unfortunately, and despite its current popularity on OTN, it turns out to be even less efficient than the earlier approaches, by quite a margin.

Regex Query (RGX_QRY)

WITH row_gen AS (
        SELECT LEVEL rn FROM DUAL CONNECT BY LEVEL < 2000
)
SELECT d.id   id,
       RTrim (Regexp_Substr (d.list_col || '|', '(.*?)\|', 1, r.rn), '|') token
  FROM delimited_lists d
  JOIN row_gen r
    ON r.rn <= Nvl (Length(d.list_col), 0) - Nvl (Length (Replace (d.list_col,'|')), 0) + 1

Plan hash value: 1537360357

----------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                       | Name            | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
----------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                |                 |      1 |        |   5400K|00:00:03.35 |    1509 |       |       |          |
|   1 |  MERGE JOIN                     |                 |      1 |    150 |   5400K|00:00:03.35 |    1509 |       |       |          |
|   2 |   SORT JOIN                     |                 |      1 |   3000 |   3000 |00:00:00.07 |    1509 |    11M|  1318K|   10M (0)|
|   3 |    TABLE ACCESS FULL            | DELIMITED_LISTS |      1 |   3000 |   3000 |00:00:00.01 |    1509 |       |       |          |
|*  4 |   SORT JOIN                     |                 |   3000 |      1 |   5400K|00:00:01.75 |       0 |   160K|   160K|  142K (0)|
|   5 |    VIEW                         |                 |      1 |      1 |   1999 |00:00:00.01 |       0 |       |       |          |
|   6 |     CONNECT BY WITHOUT FILTERING|                 |      1 |        |   1999 |00:00:00.01 |       0 |  2048 |  2048 | 2048  (0)|
|   7 |      FAST DUAL                  |                 |      1 |      1 |      1 |00:00:00.01 |       0 |       |       |          |
----------------------------------------------------------------------------------------------------------------------------------------

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

   4 - access(INTERNAL_FUNCTION("R"."RN")<=NVL(LENGTH("D"."LIST_COL"),0)-NVL(LENGTH(REPLACE("D"."LIST_COL",'|')),0)+1)
       filter(INTERNAL_FUNCTION("R"."RN")<=NVL(LENGTH("D"."LIST_COL"),0)-NVL(LENGTH(REPLACE("D"."LIST_COL",'|')),0)+1)

Notes on RGX_QRY

This query also generates rows using CONNECT BY, but differs from the others shown by using regular expressions to do the token parsing, which is simpler than the Substr/Instr approaches.

This seems to be quite popular, but it’s well known that regular expression processing can be bad for performance, and so it proves here, with CPU time increasing quadratically with number of tokens.

XML Query (XML_QRY)

SELECT id   id,
       x2   token
  FROM delimited_lists, XMLTable(
    'if (contains($X2,"|")) then ora:tokenize($X2,"\|") else $X2'
  PASSING list_col AS x2
  COLUMNS x2 VARCHAR2(4000) PATH '.'
)

Plan hash value: 2423482301

----------------------------------------------------------------------------------------------------------------------
| Id  | Operation                          | Name                  | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
----------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                   |                       |      1 |        |   5400K|00:00:10.85 |    3009 |
|   1 |  NESTED LOOPS                      |                       |      1 |     24M|   5400K|00:00:10.85 |    3009 |
|   2 |   TABLE ACCESS FULL                | DELIMITED_LISTS       |      1 |   3000 |   3000 |00:00:00.01 |    3009 |
|   3 |   COLLECTION ITERATOR PICKLER FETCH| XQSEQUENCEFROMXMLTYPE |   3000 |   8168 |   5400K|00:00:03.49 |       0 |
----------------------------------------------------------------------------------------------------------------------

Notes on XML_QRY

This query using XMLTable is copied from the version used by Jayesh in the AskTom thread above.

Model Query (MOD_QRY)

SELECT id      id,
       token   token
  FROM delimited_lists
 MODEL
    PARTITION BY (id)
    DIMENSION BY (1 rn)
    MEASURES (CAST('' AS VARCHAR2(4000)) AS token, '|' || list_col || '|' list_col, 2 pos, 0 nxtpos, Length(list_col) + 2 len)
    RULES ITERATE (2000) UNTIL pos[1] > len[1] (
       nxtpos[1] = Instr (list_col[1], '|', pos[1], 1),
       token[iteration_number+1] = Substr (list_col[1], pos[1], nxtpos[1] - pos[1]),
       pos[1] = nxtpos[1] + 1
    )

Plan hash value: 1656081500

-------------------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation              | Name            | Starts | E-Rows | A-Rows |   A-Time   | Buffers | Reads  | Writes |  OMem |  1Mem | Used-Mem |
-------------------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT       |                 |      1 |        |   5400K|03:10:43.97 |    1509 |   2883 |   2883 |       |       |          |
|   1 |  SQL MODEL ORDERED FAST|                 |      1 |   3000 |   5400K|03:10:43.97 |    1509 |   2883 |   2883 |  2047M|   112M| 2844M (1)|
|   2 |   TABLE ACCESS FULL    | DELIMITED_LISTS |      1 |   3000 |   3000 |00:00:00.01 |    1509 |      0 |      0 |       |       |          |
-------------------------------------------------------------------------------------------------------------------------------------------------

Notes on MOD_QRY

I wrote this query using the Model clause, available since Oracle Database version 10, for this article.

The Model clause has something of a reputation for poor performance, and this was one of the slower methods, with CPU time increasing quadratically with number of tokens.

Pipelined Function Query (PLF_QRY)

Pipelined Function Strings.Split

FUNCTION Split (p_string VARCHAR2, p_delim VARCHAR2) RETURN L1_chr_db_arr PIPELINED IS

  c_delim_len   CONSTANT SIMPLE_INTEGER := Length(p_delim);
  l_token_start          SIMPLE_INTEGER := 1;
  l_next_delim           SIMPLE_INTEGER := Instr (p_string, p_delim, l_token_start, 1);

BEGIN

  WHILE l_next_delim > 0 LOOP
    PIPE ROW (Substr (p_string, l_token_start, l_next_delim - l_token_start));
    l_token_start := l_next_delim + c_delim_len;
    l_next_delim := Instr (p_string || p_delim, p_delim, l_token_start, 1);
  END LOOP;

END Split;

Query Using Pipelined Function

SELECT d.id                id,
       s.COLUMN_VALUE      token
  FROM delimited_lists d
 CROSS JOIN TABLE (Strings.Split(d.list_col, '|')) s
Plan hash value: 2608399241

----------------------------------------------------------------------------------------------------------------
| Id  | Operation                          | Name            | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
----------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                   |                 |      1 |        |   5400K|00:00:03.08 |    3009 |
|   1 |  NESTED LOOPS                      |                 |      1 |     24M|   5400K|00:00:03.08 |    3009 |
|   2 |   TABLE ACCESS FULL                | DELIMITED_LISTS |      1 |   3000 |   3000 |00:00:00.01 |    3009 |
|   3 |   COLLECTION ITERATOR PICKLER FETCH| SPLIT           |   3000 |   8168 |   5400K|00:00:01.87 |       0 |
----------------------------------------------------------------------------------------------------------------

Notes on PLF_QRY

This is a fairly well known approach to the problem that involves doing the string splitting within a pipelined database function that is passed the delimited string as a parameter. I wrote my own version for this article, taking care to make only one call to each of the oracle functions Instr and Substr within a loop over the tokens.

The results confirm that it is in fact the fastest approach over all data points considered, and CPU time increased approximately linearly with number of tokens.

With Function v12.1 Query (WFN_QRY)

WITH FUNCTION Split (p_string VARCHAR2, p_delim VARCHAR2) RETURN L1_chr_db_arr IS
  c_delim_len   CONSTANT SIMPLE_INTEGER := Length(p_delim);
  l_token_start          SIMPLE_INTEGER := 1;
  l_next_delim           SIMPLE_INTEGER := Instr (p_string, p_delim, l_token_start, 1);
  l_ret_arr              L1_chr_db_arr := L1_chr_db_arr();

BEGIN

  WHILE l_next_delim > 0 LOOP
    l_ret_arr.EXTEND;
    l_ret_arr(l_ret_arr.COUNT) := Substr (p_string, l_token_start, l_next_delim - l_token_start);
    l_token_start := l_next_delim + c_delim_len;
    l_next_delim := Instr (p_string || p_delim, p_delim, l_token_start, 1);
  END LOOP;
  RETURN l_ret_arr;

END Split;
SELECT d.id                id,
       s.COLUMN_VALUE      token
  FROM delimited_lists d
 CROSS JOIN TABLE (Split(d.list_col, '|')) s

Plan hash value: 2608399241

----------------------------------------------------------------------------------------------------------------
| Id  | Operation                          | Name            | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
----------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                   |                 |      1 |        |   5400K|00:00:17.56 |    3009 |
|   1 |  NESTED LOOPS                      |                 |      1 |     24M|   5400K|00:00:17.56 |    3009 |
|   2 |   TABLE ACCESS FULL                | DELIMITED_LISTS |      1 |   3000 |   3000 |00:00:00.01 |    3009 |
|   3 |   COLLECTION ITERATOR PICKLER FETCH| SPLIT           |   3000 |   8168 |   5400K|00:00:02.57 |       0 |
----------------------------------------------------------------------------------------------------------------

Notes on WFN_QRY

Oracle introduced the ability to include a PL/SQL function definition directly in a query in version 12.1. I converted my pipelined function into a function within a query, returning an array of character strings.

As we would expect from the results of the similar pipelined function approach, this also turns out to be a very efficient solution. However, it may be surprising to many that it is significantly slower (20-30%) than using the separate database function, given the prominence that is usually assigned to context-switching.

Recursive Subquery Factor Query (RSF_QRY)

WITH rsf (id, token, nxtpos, nxtpos2, list_col, len, iter) AS
(
SELECT id,
       Substr (list_col, 1, Instr (list_col || '|', '|', 1, 1) - 1),
       Instr (list_col || '|', '|', 1, 1) + 1,
       Instr (list_col || '|', '|', 1, 2),
       list_col || '|',
       Length (list_col) + 1,
       1
  FROM delimited_lists
UNION ALL
SELECT id,
       Substr (list_col, nxtpos, nxtpos2 - nxtpos),
       nxtpos2 + 1,
       Instr (list_col, '|', nxtpos2 + 1, 1),
       list_col,
       len,
       iter + 1
  FROM rsf r
 WHERE nxtpos <= len
)
SELECT
       id       id,
       token    token
  FROM rsf

Plan hash value: 2159872273

--------------------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                                 | Name            | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
--------------------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                          |                 |      1 |        |   5400K|03:27:56.79 |    1434M|       |       |          |
|   1 |  VIEW                                     |                 |      1 |   6000 |   5400K|03:27:56.79 |    1434M|       |       |          |
|   2 |   UNION ALL (RECURSIVE WITH) BREADTH FIRST|                 |      1 |        |   5400K|03:27:45.02 |    1434M|    12M|  1343K|   10M (0)|
|   3 |    TABLE ACCESS FULL                      | DELIMITED_LISTS |      1 |   3000 |   3000 |00:00:00.01 |    1509 |       |       |          |
|   4 |    RECURSIVE WITH PUMP                    |                 |   1800 |        |   5397K|00:00:04.48 |       0 |       |       |          |
--------------------------------------------------------------------------------------------------------------------------------------------------

Notes on RSF_QRY

Oracle introduced recursive subquery factoring in v11.2, as an Ansi standard approach to SQL recursion, and with greater power than the older CONNECT BY recursion. I wrote the query for this article.

The query turned out to be surprisingly simple in structure, but for large numbers of tokens it was by far the slowest, and CPU time increased quadratically with number of tokens.

Match Recognize Query (RMR_QRY)

WITH row_gen AS (
        SELECT LEVEL rn FROM DUAL CONNECT BY LEVEL <= 4000
), char_streams AS (
SELECT d.id, r.rn, Substr (d.list_col || '|', r.rn, 1) chr
  FROM delimited_lists d
  JOIN row_gen r
    ON r.rn <= Nvl (Length(d.list_col), 0) + 2
), chars_grouped AS (
SELECT *
  FROM char_streams
 MATCH_RECOGNIZE (
   PARTITION BY id
   ORDER BY rn
   MEASURES chr mchr,
            FINAL COUNT(*) n_chrs,
            MATCH_NUMBER() mno
      ALL ROWS PER MATCH
  PATTERN (c*? d)
   DEFINE d AS d.chr = '|'
  ) m
)
SELECT id   id, 
       RTrim (Listagg (chr, '') WITHIN GROUP (ORDER BY rn), '|') token
  FROM chars_grouped
GROUP BY id, mno

Plan hash value: 2782416907

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                          | Name            | Starts | E-Rows | A-Rows |   A-Time   | Buffers | Reads  | Writes |  OMem |  1Mem | Used-Mem | Used-Tmp|
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                   |                 |      1 |        |   5400K|00:00:52.53 |    6036K|    103K|    103K|       |       |          |         |
|   1 |  SORT GROUP BY                     |                 |      1 |    150 |   5400K|00:00:52.53 |    6036K|    103K|    103K|   330M|  6949K|   97M (1)|     395K|
|   2 |   VIEW                             |                 |      1 |    150 |     10M|00:00:53.55 |    6036K|  52539 |  52539 |       |       |          |         |
|   3 |    MATCH RECOGNIZE SORT            |                 |      1 |    150 |     10M|00:00:51.47 |    6036K|  52539 |  52539 |   231M|  5084K|  163M (1)|         |
|   4 |     VIEW                           |                 |      1 |    150 |     10M|00:00:18.75 |    6036K|      0 |      0 |       |       |          |         |
|   5 |      NESTED LOOPS                  |                 |      1 |    150 |     10M|00:00:11.76 |    6036K|      0 |      0 |       |       |          |         |
|   6 |       VIEW                         |                 |      1 |      1 |   4000 |00:00:00.01 |       0 |      0 |      0 |       |       |          |         |
|   7 |        CONNECT BY WITHOUT FILTERING|                 |      1 |        |   4000 |00:00:00.01 |       0 |      0 |      0 |  2048 |  2048 | 2048  (0)|         |
|   8 |         FAST DUAL                  |                 |      1 |      1 |      1 |00:00:00.01 |       0 |      0 |      0 |       |       |          |         |
|*  9 |       TABLE ACCESS FULL            | DELIMITED_LISTS |   4000 |    150 |     10M|00:00:10.12 |    6036K|      0 |      0 |       |       |          |         |
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------

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

   9 - filter("R"."RN"<=NVL(LENGTH("D"."LIST_COL"),0)+2)

Notes on RMR_QRY

Oracle introduced Match_Recognize in v12.1, as a mechanism for pattern matching along the lines of regular expressions for strings, but for matching patterns across records. I wrote the query for this article, converting each character in the input strings into a separate record to allow for its use.

This approach might seems somewhat convoluted, and one might expect it to be correspondingly slow. As it turns out though, for most datasets it is faster than many of the other methods, the ones with very long tokens being the exception, and CPU time increased linearly with both number of tokens and number of characters per token. It is notable that, apart from the exception mentioned, it outperformed the regular expression query.

Performance Results

In the tables below, we will include some expressions used in Dimensional Benchmarking of Bracket Parsing SQL:

  • LRTB = Ratio to best time at high data point
  • RTP_L = Linear ratio as defined in the link above, averaged over successive data points
  • RTP_Q = Quadratic ratio as defined in the link above, averaged over successive data points

The CPU times are listed but elapsed times are much the same. Each table has columns in order of increasing last CPU time by query.

Depth fixed, high; width range low: d=18, w=(50,100,150,200)

Depth fixed, low; width range high: d=1, w=(450,900,1350,1800)

Width fixed, low; depth range high: w=5, d=(195,390,585,780)


Width fixed, high; depth range low: w=150, d=(6,12,18,24)

A Note on the Row Generation by Connect By Results

It is interesting to observe that the ‘classical’ mechanism for row-generation in string-splitting and similar scenarios turns out to be much slower than a simpler approach that removes the correlation of the row-generating subquery. This ‘classical’ mechanism has been proposed on Oracle forums over many years, while a simpler and faster approach seems to have gone undiscovered. The reason for its performance deficit is simply that running a Connect By query for every master row is unsurprisingly inefficient. The Use of the v12.1 LATERAL correlation syntax simplifies but doesn’t improve performance by much.

The more recent approach to Connect By row-generation is to use the sys_guid ‘trick’ to embed the Connect By in the main query rather than in a correlated subquery, and this has become very popular on forums such as OTN. As we have seen, although simpler, this is even worse for performance: Turning the whole query into a tree-walk isn’t good for performance either. It’s better to isolate the tree-walk, execute it once, and then just join its result set as in RGN_QRY.

Conclusions

  • The database pipelined function solution (PLF_QRY) is generally the fastest across all data points
  • Using the v12.1 feature of a PL/SQL function embedded within the query is almost always next best, although slower by up to about a third; its being slower than a database function may surprise some
  • Times generally increased uniformly with numbers of tokens, usually either linearly or quadratically
  • Times did not seem to increase so uniformly with token size, except for XML (XML_QRY), Match_Recognize (RMR_QRY) and regular expression (RGX_QRY)
  • For larger numbers of tokens, three methods all showed quadratic variation and were very inefficient: Model (MOD_QRY), regular expression (RGX_QRY), and recursive subquery factors (RSF_QRY)
  • We have highlighted two inefficient but widespread approaches to row-generation by Connect By SQL, and pointed out a better method

These conclusions are based on the string-splitting problem considered, but no doubt would apply to other scenarios involving requirements to split rows into multiple rows based on some form of string-parsing.

Database VersionOracle Database 12c 12.1.0.2.0
OutputBatch_Str
GitHubA Framework for Dimensional Benchmarking of SQL Query Performance
Overview ArticleA Framework for Dimensional Benchmarking of SQL Performance






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






Dimensional Benchmarking of Bracket Parsing SQL

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:

  • CBL_QRY, mathguy: Connect By, Analytics, Regex
  • MRB_QRY, Peter vd Zwan: Connect By, Match_Recognize
  • WFB_QRY, me: With PL/SQL Function, Arrays
  • PFB_QRY, me: Pipelined PL/SQL Function, Arrays

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:

  • Each str column contains w bracket pairs
  • The str column begins with a 3-character record number
  • After the record number, the str column begins with d opening brackets with 3 characters of text, like: ‘(001’, etc., followed by the d closing brackets, then the remaining wd pairs in an unnested sequence, like ‘(001)’

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.

  • Depth fixed, at small width point; width varies: d=100, w=(100, 200, 300, 400)
  • Width fixed at high depth point; depth varies: w=400, d=(0, 100, 200, 300, 400)

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.

  • LRTB = Ratio to best time at high data point
  • RTP_L = Linear ratio as defined above, averaged over successive data points
  • RTP_Q = Quadratic ratio as defined above, averaged over successive data points

Depth fixed, at small width point; width varies: d=100, w=(100, 200, 300, 400)

Notes on Results for Fixed Depth

  • CPU time increases with width for all queries at above a linear rate
  • CBL_QRY is significantly faster than MRB_QRY, which appears to be rising quadratically
  • Both WFB_QRY and PFB_QRY are much faster than the non-PL/SQL queries
  • PFB_QRY is slightly faster than WFB_QRY. This could be regarded as too small a difference to be significant, but is consistent across the data points, despite the context switching with database function calls

Width fixed at high depth point; depth varies: w=400, d=(0, 100, 200, 300, 400)

Notes on Results for Fixed Width

  • CPU time increases with depth for all queries although at a sublinear rate
  • CBL_QRY has a big jump in CPU time between 0 and 100, where nesting starts to come in, and was actually faster than CBL_QRY without nesting