Skip to Main Content

SQL & PL/SQL

Announcement

For appeals, questions and feedback about Oracle Forums, please email oracle-forums-moderators_us@oracle.com. Technical questions should be asked in the appropriate category. Thank you!

Head scratcher (bug?) - seesaw recursive CTE

mathguyAug 30 2016 — edited Aug 31 2016

Hi all,

I spent (wasted?) a couple of hours on a little project today, trying to figure out where I have a cycle in a recursive CTE. I expanded it step by step, watching what each step does, trying to find my mistake. Then I gave up and used the CYCLE clause - and I think I am seeing another bug related to recursive CTEs (I rediscovered another one just last week). This time it's the same in 11.2 XE and in 12.1 EE (the one from last week was an 11.2 bug that was fixed in version 12).

This is a method I don't recall seeing before - I call it "seesaw" recursive CTE, it could also be "two-cylinder" recursive CTE or whatever. The idea is that I want to alternate between doing "one thing" and "another thing", over and over, until the exit condition is met.

In this particular project, suppose we are given a dictionary of "placeholders" and "values", and a set of input strings that may (or may not) contain one or more placeholders. The assignment is to replace each placeholder with its corresponding value. To make it more interesting, suppose that the "values" may themselves contain placeholders, so the assignment itself is recursive. Of course, this means there may be true cycles in the whole thing; I am not attempting to check for that, at least not for now - I am just looking to make the solution work when the inputs are consistent and do not themselves lead to infinite loops.

I know you'll ask, so let me answer: I don't care about this problem, I only care about the method for solving it. Someone posted a similar question on SO, which I was able to solve with a different method; but I think this seesaw recursive CTE method may be more efficient, and it may be helpful in other problems. For example, I believe it may lead to a pure SQL implementation of the proper Eratosthenes algorithm for finding primes, which we discussed several months ago.

Here is the requirement: Given input strings and a dictionary like below, perform all substitutions in each input string so that the result no longer contains any placeholders. A placeholder is a dollar sign followed by one or more digits, whatever matches '\$\d+' in a regular expression. We assume that all placeholders found in the input strings are actually present in the mappings table, and the data itself does not cause infinite loops. Placeholders are to be replaced from left to right at each step.

The strategy is to find the leftmost placeholder, replace it, and repeat. This is circular, so it must be unwound - in the recursive query I use a flag, 1 or -1, to indicate whether the next step is to identify the next placeholder or to substitute its value into the string.

As you shall see, the query below uses the CYCLE clause, and with it I get the correct answer. I am showing all the rows and columns from the result, to show that the "cycle" column is always 0, never 1 - meaning no cycles were found. Yet with the CYCLE line commented out, the runtime throws a "cycle detected" error. (The actual solution to the problem is to select only  input_str  and  new_str,  and only  where next_placeholder is null.) I added a counter (last column) only so that I can order the output so it can be read easily; in the actual solution I don't need this counter. I could have used the SEARCH clause for this, but I remembered that only after I was done...

Questions:

- Is this a bug? (Meaning, is it a known bug?) Or is there actually something wrong with my code?

- Is this seesaw recursive CTE method OK? Is it well-known? Or does it have some flaws which means it should only be used when nothing else works?            Thank you,   -   mathguy-ro

with
     inputs ( input_str ) as (
       select 'Hello, World' from dual union all
       select '$1 = True'    from dual union all
       select '$2 > $3'      from dual union all
       select '$1 = $4'      from dual
     ),
     mappings ( placeholder, val ) as (
       select '$1', 'Example 1' from dual union all
       select '$2', 'Example 2' from dual union all
       select '$3', 'Example 3' from dual union all
       select '$4', '$2 + $3'   from dual
     ),
     rec ( input_str, new_str, next_placeholder, flag, ct ) as (
       select  input_str, input_str, regexp_substr(input_str, '\$\d+'), 1, 1
         from  inputs
       union all
       select  r.input_str,
               case r.flag when -1 then r.new_str
                           else replace(r.new_str, r.next_placeholder, m.val) end,
               case r.flag when  1 then r.next_placeholder
                           else regexp_substr(r.new_str, '\$\d+') end,
               - r.flag,
               ct + 1
         from  rec r inner join mappings m
                     on r.next_placeholder = m.placeholder                    
         where r.next_placeholder is not null
     )
     CYCLE input_str, new_str, next_placeholder, flag SET cycle TO 1 DEFAULT 0
select * from rec
order by input_str, ct;

INPUT_STR    NEW_STR                            NEXT_PLACEHOLDER FLAG CT  CYCLE
------------ ---------------------------------- ---------------- ---- --  -----
$1 = $4      $1 = $4                            $1                  1  1  0    
$1 = $4      Example 1 = $4                     $1                 -1  2  0    
$1 = $4      Example 1 = $4                     $4                  1  3  0    
$1 = $4      Example 1 = $2 + $3                $4                 -1  4  0    
$1 = $4      Example 1 = $2 + $3                $2                  1  5  0    
$1 = $4      Example 1 = Example 2 + $3         $2                 -1  6  0    
$1 = $4      Example 1 = Example 2 + $3         $3                  1  7  0    
$1 = $4      Example 1 = Example 2 + Example 3  $3                 -1  8  0    
$1 = $4      Example 1 = Example 2 + Example 3                      1  9  0    
$1 = True    $1 = True                          $1                  1  1  0    
$1 = True    Example 1 = True                   $1                 -1  2  0    
$1 = True    Example 1 = True                                       1  3  0    
$2 > $3      $2 > $3                            $2                  1  1  0    
$2 > $3      Example 2 > $3                     $2                 -1  2  0    
$2 > $3      Example 2 > $3                     $3                  1  3  0    
$2 > $3      Example 2 > Example 3              $3                 -1  4  0    
$2 > $3      Example 2 > Example 3                                  1  5  0    
Hello, World Hello, World                                           1  1  0    

18 rows selected

Comments
Locked Post
New comments cannot be posted to this locked post.
Post Details
Locked on Sep 28 2016
Added on Aug 30 2016
7 comments
1,564 views