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