There are three restrictions on indexing and partitioning: a unique index cannot be local non-prefixed; a global non-prefixed index is not possible; a bitmap index cannot be global. Why these limitations? I suspect that they are there to prevent us from doing something idiotic.

This is the table used for all examples that follow:

CREATE TABLE EMP
      (EMPNO NUMBER(4) CONSTRAINT PK_EMP PRIMARY KEY,
       ENAME VARCHAR2(10),
       JOB VARCHAR2(9),
       MGR NUMBER(4),
       HIREDATE DATE,
       SAL NUMBER(7,2),
       COMM NUMBER(7,2),
       DEPTNO NUMBER(2) )
PARTITION BY HASH (EMPNO) PARTITIONS 4;

the usual EMP table, with a partitioning clause appended. It is of course a contrived example. Perhaps I am recruiting so many employees concurrently that a non-partitioned table has problems with buffer contention that can be solved only with hash partitioning.

Why can't I have a local non-prefixed unique index?
A local non-unique index is no problem, but unique is not possible:

orclz> create index enamei on emp(ename) local;

Index created.

orclz> drop index enamei;

Index dropped.

orclz> create unique index enamei on emp(ename) local;
create unique index enamei on emp(ename) local
                              *
ERROR at line 1:
ORA-14039: partitioning columns must form a subset of key columns of a UNIQUE index

You cannot get a around the problem by separating the index from the constraint (which is always good practice):

orclz> create index enamei on emp(ename) local;

Index created.

orclz> alter table emp add constraint euk unique (ename);
alter table emp add constraint euk unique (ename)
*
ERROR at line 1:
ORA-01408: such column list already indexed


orclz>

So what is the issue? Clearly it is not a technical limitation. But if it were possible, consder the implications for performance. When inserting a row, a unique index (or a non-unique index enforcing a unique constraint) must be searched to see if the key value already exists. For my little four partition table, that would mean four index searches: one of each local index partition. Well, OK. But what if the table were range partitioned into a thousand partitions? Then every insert would have to make a thousand index lookups. This would be unbelievably slow. By restricting unique indexes to global or local prefixed, Uncle Oracle is ensuring that we cannot create such an awful situation.

Why can't I have a global non-prefixed index?
Well, why would you want one? In my example, perhaps you want a global index on deptno, partitioned by mgr. But you can't do it:

orclz> create index deptnoi on emp(deptno) global partition by hash(mgr) partitions 4;
create index deptnoi on emp(deptno) global partition by hash(mgr) partitions 4
                                                                *
ERROR at line 1:
ORA-14038: GLOBAL partitioned index must be prefixed


orclz>

This index, if it were possible, might assist a query with an equality predicate on mgr and a range predicate on deptno: prune off all the non-relevant mgr partitions, then a range scan. But exactly the same effect would be achieved by using global nonpartitioned concatenated index on mgr and deptno. If the query had only deptno in the predicate, it woud have to search each partition of the putative global partitioned index, a process which would be just about identical to a skip scan of the nonpartitioned index. And of course the concatenated index could be globally partitioned - on mgr. So there you have it: a global non-prefixed index would give you nothing that is not available in other ways.

Why can't I have a global partitioned bitmap index?
This came up on the Oracle forums recently, https://forums.oracle.com/thread/2575623
Global indexes must be prefixed. Bearing that in mind, the question needs to be re-phrased: why would anyone ever want a prefixed partitioned bitmap index? Something like this:

orclz>
orclz> create bitmap index bmi on emp(deptno) global partition by hash(deptno) partitions 4;
create bitmap index bmi on emp(deptno) global partition by hash(deptno) partitions 4
                                       *
ERROR at line 1:
ORA-25113: GLOBAL may not be used with a bitmap index

orclz>

If this were possible, what would it give you? Nothing. You would not get the usual benefit of reducing contention for concurrent inserts, because of the need to lock entire blocks of a bitmap index (and therefore ranges of rows) when doing DML. Range partitioning a bitmap index would be ludicrous, because of the need to use equality predicates to get real value from bitmaps. Even with hash partitions, you would not get any benefit from partition pruning, because using equality predicates on a bitmap index in effect prunes the index already: that is what a bitmap index is for. So it seems to me that a globally partitioned bitmap index would deliver no benefit, while adding complexity and problems of index maintenance. So I suspect that, once again, Uncle Oracle is protecting us from ourselves.

Is there a technology limitation?
I am of course open to correction, but I cannot see a technology limitation that enforces any of these three impossibilities. I'm sure they are all technically possible. But Oracle has decided that, for our own good, they will never be implemented.
--
John Watson
Oracle Certified Master DBA
http://skillbuilders.com

Finding gaps is classic problem in PL/SQL. The basic concept is that you have some sort of numbers (like these: 1, 2, 3, 5, 6, 8, 9, 10, 15, 20, 21, 22, 23, 25, 26), where there’s supposed to be a fixed interval between the entries, but some entries could be missing. The gaps problem involves identifying the ranges of missing values in the sequence. For these numbers, the solution will be as follows:
START_GAP END_GAP
4 4
7 7
11 14
16 19
24 24

First, run the following code, to create tab1 table:


CREATE TABLE tab1
(
col1 INTEGER
);


Then, insert a few rows:


INSERT INTO tab1 VALUES (1);
INSERT INTO tab1 VALUES (2);
INSERT INTO tab1 VALUES (3);
INSERT INTO tab1 VALUES (5);
INSERT INTO tab1 VALUES (6);
INSERT INTO tab1 VALUES (8);
INSERT INTO tab1 VALUES (9);
INSERT INTO tab1 VALUES (10);
INSERT INTO tab1 VALUES (15);
INSERT INTO tab1 VALUES (20);
INSERT INTO tab1 VALUES (21);
INSERT INTO tab1 VALUES (22);
INSERT INTO tab1 VALUES (23);
INSERT INTO tab1 VALUES (25);
INSERT INTO tab1 VALUES (26);

COMMIT;

With data, you can take care of solving the gaps problem…

One of the most efficient solutions to the gaps problem involves using analytic functions (also known as window functions)


WITH aa AS
(SELECT col1 AS cur_value, LEAD (col1) OVER (ORDER BY col1) AS next_value
FROM tab1)
SELECT cur_value + 1 AS start_gap, next_value - 1 AS end_gap
FROM aa
WHERE next_value - cur_value > 1
ORDER BY start_gap


Using the LEAD function, you can return for each current col1 value (call it cur_value) the next value in the sequence (call it next_value). Then you can filter only pairs where the difference between the two is greater than the one.

I recently had the opportunity to talk with Tom Kyte (!), and in the course of our conversation, he really made me face up to the fact that the SQL syntax I use every day is frozen in time: I’m not making much use of the analytic functions and other syntax that Oracle has introduced since 8i.

Here’s a brief history of these additions to Oracle SQL, from Keith Laker, Oracle’s Product Manager for Analytical SQL:

8i	Window functions
9i	Rollup, grouping sets, cube, enhanced window functions
10g	SQL Model clause, statistical functions, partition outer join
11g	SQL Pivot clause, Recursive WITH, Listagg, Nth value
12c	Pattern matching, Top N

Not only do these make complex queries much, much simpler and easier, they are also much faster for the same result than non-analytic SQL, as Tom Kyte has shown repeatedly on his blog and in his books.

So, I was sold and I wanted to jump in with Recursive WITH. The WITH clause lets you define inline views to use across an entire query, and the coolest thing about this is that you can define the subquery recursively – so that the inline view calls itself.

Recursive WITH basic syntax:

WITH Tablename (col1, col2, ...) AS
(SELECT A, B, C... FROM dual                   --anchor member
UNION ALL
SELECT A', B', C'... from Tablename where...   --recursive member
)
select ... from Tablename where ...

Refactoring the Factorial

One fun thing about recursive WITH, aka recursive subquery refactoring, is the ease with which we can implement a recursive algorithm in SQL. Let’s warm up with a classic example of recursion: finding the factorial of a number. Factorial(n) = n! = 1*2*3*…*n . It’s a classic example because Factorial(n) can be defined recursively as:

Factorial(0) = 1
Factorial(n) = Factorial(n-1) * n

Here’s a first pass at implementing that directly in SQL to find the factorial of 5, using a recursive WITH subquery:

WITH Factorial (operand,total_so_far) AS
(SELECT 5 operand, 5 total_so_far FROM dual    -- Using anchor member to pass in "5"
UNION ALL
SELECT operand-1, total_so_far * (operand-1) FROM Factorial
WHERE operand > 1)
SELECT * FROM Factorial;

   OPERAND TOTAL_SO_F
---------- ----------
         5          5
         4         20
         3         60
         2        120
         1        120

and to display just the result, we select it from Factorial:

WITH Factorial (operand,total_so_far) AS
(SELECT 5 operand, 5 total_so_far FROM dual    -- Find the factorial of 5
UNION ALL
SELECT operand-1, total_so_far * (operand-1) FROM Factorial
WHERE operand > 1)
SELECT MAX(operand) || '! = ' || MAX(total_so_far) AS RESULT FROM Factorial;

RESULT
-----------------
5! = 120

Ahem! I have cheated a little for simplicity here. The query doesn’t take into account that Factorial(0) = 1:

WITH Factorial (operand,total_so_far) AS
(SELECT 0 operand, 0 total_so_far FROM dual    -- Find the factorial of 0
UNION ALL
SELECT operand-1, total_so_far * (operand-1) FROM Factorial
WHERE operand > 1)                             -- This is going to get me nowhere fast...
SELECT * FROM Factorial;

  OPERAND TOTAL_SO_F
---------- ----------
         0          0

To do it properly, we need to include Factorial(0) = 1 in the recursive subquery:

WITH Factorial (operand,total_so_far) AS
(SELECT 0 operand, 0 total_so_far FROM dual    -- Find the factorial of 0
UNION ALL
SELECT operand-1, 
CASE                                           -- Factorial (0) = 1
  WHEN operand=0 THEN 1
  ELSE (total_so_far * (operand-1))
  END
FROM Factorial
WHERE operand >= 0)
SELECT MAX(operand) || '! = ' || MAX(total_so_far) AS RESULT FROM Factorial;

RESULT
------------------------------------------------------------------------------------
0! = 1

We can also reverse direction and recursively build a table of factorials, multiplying as we go.
That’s the approach Lucas Jellema takes in his excellent blog post on factorials in SQL.

WITH Factorial (operand,output) AS
(SELECT 0 operand, 1 output FROM dual
UNION ALL
SELECT operand+1, output * (operand+1) FROM Factorial
WHERE operand < 5)
SELECT * FROM Factorial;

   OPERAND     OUTPUT
---------- ----------
         0          1
         1          1
         2          2
         3          6
         4         24
         5        120

There are two nice things about this approach: first, every row of the subquery result contains n and n! , and second, the rule that 0! = 1 is elegantly captured in the anchor member.

denrael ev’ew tahw gniylppA

Now let’s do something more interesting – reversing a string. Here’s some sample code in C from the CS 211 course at Cornell:

 public String reverseString(String word) {
     if(word == null || word.equals(""))
        return word;
     else
        return reverseString(word.substring(1, word.length())) + 
            word.substring(0,1);
  }

Let’s run through an example word to see how it works. For simplicity I’ll write reverseString(“word”) as r(word). Using “cat” as the word, stepping through the algorithm gives:

r(cat) = r(r(at))+c = r(r(r(t))+a+c = r(r(r(r())+t+a+c = ''+t+a+c = tac

Now to rewrite the same function in SQL. Using the same example string, “cat,” I want my recursively defined table to look like this:

in   out
--------
cat 
at   c
t    ac
     tac

In C, the initial letter in the word is the 0th letter, and in SQL, it’s the 1st letter. So the C expression word.substring(1,N) corresponds to SQL expression substr(word,2,N-1) . With that in mind, it’s easy to rewrite the C algorithm in SQL:

WITH WordReverse (INPUT, output) AS
  (SELECT 'CAT' INPUT, NULL output FROM dual
   UNION ALL
   SELECT substr(INPUT,2,LENGTH(INPUT)-1), substr(INPUT,1,1) || output
   FROM wordReverse
   WHERE LENGTH(INPUT) > 0
  )
SELECT * FROM wordReverse;

INPUT    OUTP
-------- ----
CAT
AT       C
T        AC
         TAC

NOTE: if using 11.2.0.3 or earlier, you might get “ORA-01489: result of string concatenation is too long” when reversing anything longer than a few letters. This is due to Bug 13876895: False ora-01489 on recursive WITH clause when concatenating columns. The bug is fixed in 11.2.0.4 and 12.1.0.1, and there’s an easy workaround: Cast one of the inputs to the concatenation as a varchar2(4000).

We could make this query user-friendlier by using a sql*plus variable to hold the input string. Another approach is to add an additional subquery to the with block to “pass in” parameters. I picked this up from Lucas Jellema’s post mentioned above, and wanted to give it a try, so I’ll add it in to my WordReverse query here.

Let’s use this to reverse a word that’s really quite atrocious:

WITH
params AS
  (SELECT 'supercalifragilisticexpialidocious' phrase FROM dual),
WordReverse (inpt, outpt) AS
  (SELECT phrase inpt, CAST(NULL AS varchar2(4000)) outpt FROM params
   UNION ALL
   SELECT substr(inpt,2,LENGTH(inpt)-1), substr(inpt,1,1) || outpt
   FROM wordReverse
   WHERE LENGTH(inpt) > 0
  )
SELECT phrase,outpt AS reversed FROM wordReverse, params
WHERE LENGTH(outpt) = LENGTH(phrase) ;

PHRASE                             REVERSED
---------------------------------- ----------------------------------------
supercalifragilisticexpialidocious suoicodilaipxecitsiligarfilacrepus

Now you might not have needed to know how to spell “supercalifragilisticexpialidocious” backwards, but one recursive requirement that does come up often is querying hierarchical data. I wrote a series of posts on hierarchical data recently, using Oracle’s CONNECT BY syntax. But recursive WITH can also be used to query hierarchical data. That’ll be the subject of my next post.

---

Republished with permission. Original URL: http://rdbms-insight.com/wp/?p=94

---

In my last post, I looked at using recursive WITH to implement simple recursive algorithms in SQL. One very common use of recursion is to traverse hierarchical data. I recently wrote a series of posts on hierarchical data, using Oracle’s CONNECT BY syntax and a fun example. In this post, I’ll be revisiting the same data using recursive WITH.

There are dozens of examples of hierarchical data, from the EMP table to the Windows Registry to binary trees, but I went with something more fun: the skeleton from the old song “Dem Dry Bones”.

Since every bone has only one ancestor, and there is a root bone with no ancestor, this is hierarchical data and we can stick it in a table and query it.

SELECT * FROM skeleton;
BONE                                     CONNECTED_TO_THE
---------------------------------------- ----------------------------------------
shoulder                                 neck
back                                     shoulder
hip                                      back
thigh                                    hip
knee                                     thigh
leg                                      knee
foot                                     heel
head
neck                                     head
toe                                      foot
arm                                      shoulder
wrist                                    arm
ankle                                    leg
heel                                     ankle
finger                                   wrist
a rib                                    back
b rib                                    back
c rib                                    back

You can see that I added some ribs and an arm to make the skeleton more complete!

Using Oracle’s CONNECT BY syntax:

SQL> col bone FOR a10
SQL> col connected_to_the FOR a9
SQL> col level FOR 99
SQL> col bone_tree FOR a27
SQL> col path FOR a65
 
SELECT bone, connected_to_the, level, 
lpad(' ',2*level, ' ') || bone AS bone_tree , 
ltrim(sys_connect_by_path(bone,'>'),'>') AS path
FROM skeleton
START WITH connected_to_the IS NULL
CONNECT BY prior bone=connected_to_the 
ORDER siblings BY 1

BONE       CONNECTED LEVEL BONE_TREE                   PATH
---------- --------- ----- --------------------------- -----------------------------------------------------------------
head                     1   head                      head
neck       head          2     neck                    head>neck
shoulder   neck          3       shoulder              head>neck>shoulder
arm        shoulder      4         arm                 head>neck>shoulder>arm
wrist      arm           5           wrist             head>neck>shoulder>arm>wrist
finger     wrist         6             finger          head>neck>shoulder>arm>wrist>finger
back       shoulder      4         back                head>neck>shoulder>back
a rib      back          5           a rib             head>neck>shoulder>back>a rib
b rib      back          5           b rib             head>neck>shoulder>back>b rib
c rib      back          5           c rib             head>neck>shoulder>back>c rib
hip        back          5           hip               head>neck>shoulder>back>hip
thigh      hip           6             thigh           head>neck>shoulder>back>hip>thigh
knee       thigh         7               knee          head>neck>shoulder>back>hip>thigh>knee
leg        knee          8                 leg         head>neck>shoulder>back>hip>thigh>knee>leg
ankle      leg           9                   ankle     head>neck>shoulder>back>hip>thigh>knee>leg>ankle
heel       ankle        10                     heel    head>neck>shoulder>back>hip>thigh>knee>leg>ankle>heel
foot       heel         11                       foot  head>neck>shoulder>back>hip>thigh>knee>leg>ankle>heel>foot
toe        foot         12                         toe head>neck>shoulder>back>hip>thigh>knee>leg>ankle>heel>foot>toe

The above CONNECT BY query uses the LEVEL pseudocolumn and the SYS_CONNECT_BY_PATH function. With recursive WITH, there’s no need for these built-ins because these values fall naturally out of the recursion.

Let’s start with the basic hierarchical query rewritten in recursive WITH.
The hierarchical relationship in our table is:
Parent(row.bone) = row.connected_to_the

WITH skellarchy (bone, parent) AS
 ( SELECT bone, connected_to_the FROM skeleton 
   WHERE bone = 'head'                         -- Start with the root
 UNION ALL
   SELECT s.bone, s.connected_to_the 
   FROM skeleton s, skellarchy r
   WHERE r.bone = s.connected_to_the           -- Parent(row.bone) = row.connected_to_the
 )
SELECT * FROM skellarchy;

BONE       PARENT
---------- ----------------------------------------
head
neck       head
shoulder   neck
back       shoulder
arm        shoulder
hip        back
wrist      arm
a rib      back
b rib      back
c rib      back
thigh      hip
finger     wrist
knee       thigh
leg        knee
ankle      leg
heel       ankle
foot       heel
toe        foot

Because we built up the SKELLARCHY table recursively, it’s easy to make an equivalent to the LEVEL pseudocolumn; it falls right out of the recursion:

WITH skellarchy (bone, parent, the_level) AS
 ( SELECT bone, connected_to_the, 0 FROM skeleton 
   WHERE bone = 'head'                         
 UNION ALL
   SELECT s.bone, s.connected_to_the , r.the_level + 1
   FROM skeleton s, skellarchy r
   WHERE r.bone = s.connected_to_the           
 )
SELECT * FROM skellarchy;

BONE       PARENT      THE_LEVEL
---------- ---------- ----------
head                           0
neck       head                1
shoulder   neck                2
back       shoulder            3
arm        shoulder            3
hip        back                4
wrist      arm                 4
a rib      back                4
b rib      back                4
c rib      back                4
thigh      hip                 5
finger     wrist               5
knee       thigh               6
leg        knee                7
ankle      leg                 8
heel       ankle               9
foot       heel               10
toe        foot               11

and it’s also easy to build up a path from root to the current node like the “SYS_CONNECT_BY_PATH” function does for CONNECT BY queries:

WITH skellarchy (bone, parent, the_level, the_path) AS
 ( SELECT bone, connected_to_the, 0, CAST(bone AS varchar2(4000)) FROM skeleton 
   WHERE bone = 'head'                         
 UNION ALL
   SELECT s.bone, s.connected_to_the , r.the_level + 1, r.the_path || '->' || s.bone
   FROM skeleton s, skellarchy r
   WHERE r.bone = s.connected_to_the           
 )
SELECT * FROM skellarchy;

BONE       PARENT     THE_LEVEL THE_PATH
---------- ---------- --------- --------------------------------------------------------------------------------
head                          0 head
neck       head               1 head->neck
shoulder   neck               2 head->neck->shoulder
back       shoulder           3 head->neck->shoulder->back
arm        shoulder           3 head->neck->shoulder->arm
hip        back               4 head->neck->shoulder->back->hip
wrist      arm                4 head->neck->shoulder->arm->wrist
a rib      back               4 head->neck->shoulder->back->a rib
b rib      back               4 head->neck->shoulder->back->b rib
c rib      back               4 head->neck->shoulder->back->c rib
thigh      hip                5 head->neck->shoulder->back->hip->thigh
finger     wrist              5 head->neck->shoulder->arm->wrist->finger
knee       thigh              6 head->neck->shoulder->back->hip->thigh->knee
leg        knee               7 head->neck->shoulder->back->hip->thigh->knee->leg
ankle      leg                8 head->neck->shoulder->back->hip->thigh->knee->leg->ankle
heel       ankle              9 head->neck->shoulder->back->hip->thigh->knee->leg->ankle->heel
foot       heel              10 head->neck->shoulder->back->hip->thigh->knee->leg->ankle->heel->foot
toe        foot              11 head->neck->shoulder->back->hip->thigh->knee->leg->ankle->heel->foot->toe

and we can use our generated the_level column to make a nice display just as we used the level pseudocolumn with CONNECT BY:

WITH skellarchy (bone, parent, the_level) AS
 ( SELECT bone, connected_to_the, 0  FROM skeleton 
   WHERE bone = 'head'                         
 UNION ALL
   SELECT s.bone, s.connected_to_the , r.the_level + 1
   FROM skeleton s, skellarchy r
   WHERE r.bone = s.connected_to_the           
 )
SELECT lpad(' ',2*the_level, ' ') || bone AS bone_tree FROM skellarchy;

BONE_TREE
---------------------------
head
  neck
    shoulder
      back
      arm
        hip
        wrist
        a rib
        b rib
        c rib
          thigh
          finger
            knee
              leg
                ankle
                  heel
                    foot
                      toe

Now, the bones are coming out in a bit of a funny order for a skeleton. Instead of this:

    shoulder
      back
      arm
        hip
        wrist
        a rib
        b rib
        c rib
          thigh
          finger

I want to see this:

    shoulder
      arm
        wrist
          finger
      back
        a rib
        b rib
        c rib
        hip
          thigh

The rows are coming out in BREADTH FIRST ordering – meaning all siblings of ‘shoulder’ are printed before any children of ‘shoulder’. But I want to see them in DEPTH FIRST: going from shoulder to finger before we start on the backbone.

WITH skellarchy (bone, parent, the_level) AS
 ( SELECT bone, connected_to_the, 0  FROM skeleton 
   WHERE bone = 'head'                         
 UNION ALL
   SELECT s.bone, s.connected_to_the , r.the_level + 1
   FROM skeleton s, skellarchy r
   WHERE r.bone = s.connected_to_the           
 )
SEARCH DEPTH FIRST BY bone SET bone_order
SELECT lpad(' ',2*the_level, ' ') || bone AS bone_tree FROM skellarchy
ORDER BY bone_order;

BONE_TREE
---------------------------
head
  neck
    shoulder
      arm
        wrist
          finger
      back
        a rib
        b rib
        c rib
        hip
          thigh
            knee
              leg
                ankle
                  heel
                    foot
                      toe

And now the result looks more like a proper skeleton.

Now on to cycles. A cycle is a loop in the hierarchical data: a row is its own ancestor. To put a cycle in the example data, I made the skeleton bend over and connect the head to the toe:

UPDATE skeleton SET connected_to_the='toe' WHERE bone='head';

And now if we try to run the query:

ERROR at line 2:
ORA-32044: cycle detected while executing recursive WITH query

With the CONNECT BY syntax, we can use CONNECT BY NOCYCLE to run a query even when cycles exist, and the pseudocolumn CONNECT_BY_IS_CYCLE to help detect cycles. For recursive WITH, Oracle provides a CYCLE clause, which is a bit more powerful as it allows us to name the column which is cycling.

WITH skellarchy (bone, parent, the_level) AS
 ( SELECT bone, connected_to_the, 0  FROM skeleton 
   WHERE bone = 'head'                         
 UNION ALL
   SELECT s.bone, s.connected_to_the , r.the_level + 1
   FROM skeleton s, skellarchy r
   WHERE r.bone = s.connected_to_the           
 )
SEARCH DEPTH FIRST BY bone SET bone_order
CYCLE bone SET is_a_cycle TO 'Y' DEFAULT 'N'
SELECT lpad(' ',2*the_level, ' ') || bone AS bone_tree, is_a_cycle FROM skellarchy
--where is_a_cycle='N'
ORDER BY bone_order;

BONE_TREE                                                    I
------------------------------------------------------------ -
head                                                         N
  neck                                                       N
    shoulder                                                 N
      arm                                                    N
        wrist                                                N
          finger                                             N
      back                                                   N
        a rib                                                N
        b rib                                                N
        c rib                                                N
        hip                                                  N
          thigh                                              N
            knee                                             N
              leg                                            N
                ankle                                        N
                  heel                                       N
                    foot                                     N
                      toe                                    N
                        head                                 Y

The query runs until the first cycle is detected, then stops.

The CONNECT BY syntax does provide a nice pseudocolumn, CONNECT_BY_ISLEAF, which is 1 when a row has no further children, 0 otherwise. In my next post, I’ll look at emulating this pseudocolumn with recursive WITH.

---

Republished with permission. Original URL: http://rdbms-insight.com/wp/?p=103

---

The CONNECT BY syntax provides a useful pseudocolumn, CONNECT_BY_ISLEAF, which identifies leaf nodes in the data: it’s 1 when a row has no further children, 0 otherwise. In this post, I’ll look at emulating this pseudocolumn using recursive WITH.

Let’s continue with the example from my previous posts about hierarchical data: the skeleton from the old song “Dem Dry Bones”.

UPDATE skeleton SET connected_to_the=NULL WHERE bone='head';
SELECT * FROM skeleton;

BONE                                     CONNECTED_TO_THE
---------------------------------------- ----------------------------------------
shoulder                                 neck
back                                     shoulder
hip                                      back
thigh                                    hip
knee                                     thigh
leg                                      knee
foot                                     heel
head
neck                                     head
toe                                      foot
arm                                      shoulder
wrist                                    arm
ankle                                    leg
heel                                     ankle
finger                                   wrist
a rib                                    back
b rib                                    back
c rib                                    back

With CONNECT BY, we can use the CONNECT_BY_ISLEAF pseudocolumn to identify leaf nodes:

SELECT bone, level, 
ltrim(sys_connect_by_path(bone,' -> '),' -> ') AS path
FROM skeleton
WHERE connect_by_isleaf=1
START WITH connected_to_the IS NULL
CONNECT BY prior bone=connected_to_the 
ORDER siblings BY 1;

BONE      LEVEL PATH                                                                                            
--------- ----- ----------------------------------------------------------------------------------------------- 
finger        6 head -> neck -> shoulder -> arm -> wrist -> finger                                              
a rib         5 head -> neck -> shoulder -> back -> a rib                                                       
b rib         5 head -> neck -> shoulder -> back -> b rib                                                       
c rib         5 head -> neck -> shoulder -> back -> c rib                                                       
toe          12 head -> neck -> shoulder -> back -> hip -> thigh -> knee -> leg -> ankle -> heel -> foot -> toe

This pseudocolumn takes a little more thought to replicate using recursive WITH than the LEVEL pseudocolumn and the SYS_CONNECT_BY_PATH, which, as we saw in my last post, fall naturally out of the recursion.

We can imitate CONNECT_BY_ISLEAF by searching DEPTH FIRST and using the LEAD function to peek at the next row’s the_level value. If the next row’s level is higher than the current row, then it’s a child of the current row; otherwise, it’s not a child. Since, with DEPTH FIRST, all the children of a row come out before any siblings, if the next row isn’t a child, then the current row is a leaf.

WITH skellarchy (bone, parent, the_level) AS
 ( SELECT bone, connected_to_the, 0  FROM skeleton 
   WHERE bone = 'head'                         
 UNION ALL
   SELECT s.bone, s.connected_to_the , r.the_level + 1
   FROM skeleton s, skellarchy r
   WHERE r.bone = s.connected_to_the           
 )
SEARCH DEPTH FIRST BY bone SET bone_order
CYCLE bone SET is_a_cycle TO 'Y' DEFAULT 'N'
SELECT lpad(' ',2*the_level, ' ') || bone AS bone_tree , the_level,
  lead(the_level) OVER (ORDER BY bone_order) AS next_level,
  CASE 
    WHEN the_level < lead(the_level) OVER (ORDER BY bone_order) THEN NULL
    ELSE 'LEAF'
  END is_leaf
FROM skellarchy
ORDER BY bone_order;

BONE_TREE                                      THE_LEVEL NEXT_LEVEL IS_L
--------------------------------------------- ---------- ---------- ----
head                                                   0          1
  neck                                                 1          2
    shoulder                                           2          3
      arm                                              3          4
        wrist                                          4          5
          finger                                       5          3 LEAF
      back                                             3          4
        a rib                                          4          4 LEAF
        b rib                                          4          4 LEAF
        c rib                                          4          4 LEAF
        hip                                            4          5
          thigh                                        5          6
            knee                                       6          7
              leg                                      7          8
                ankle                                  8          9
                  heel                                 9         10
                    foot                              10         11
                      toe                             11            LEAF

Watch out for Cycles

The first point of caution about this solution concerns cycles. In my last post, I had created a cycle by making the ‘head’ node’s parent the ‘toe’ node. If I’d left the cycle in the data, the toe node wouldn’t be a leaf any more, but this query would falsely identify the head as a leaf:

UPDATE skeleton SET connected_to_the='toe' WHERE bone='head';

BONE_TREE                                      THE_LEVEL NEXT_LEVEL IS_L
--------------------------------------------- ---------- ---------- ----
head                                                   0          1
  neck                                                 1          2
    shoulder                                           2          3
      arm                                              3          4
        wrist                                          4          5
          finger                                       5          3 LEAF
      back                                             3          4
        a rib                                          4          4 LEAF
        b rib                                          4          4 LEAF
        c rib                                          4          4 LEAF
        hip                                            4          5
          thigh                                        5          6
            knee                                       6          7
              leg                                      7          8
                ankle                                  8          9
                  heel                                 9         10
                    foot                              10         11
                      toe                             11         12
                        head                          12            LEAF
 
19 rows selected.

This can be corrected for by adding WHERE IS_A_CYCLE=’N’ to the query.

Respect the order of evaluation…

A second point of caution: if I add a WHERE clause to the query that limits the number of levels, the last line of the resultset will always be identified as a leaf.

WITH skellarchy (bone, parent, the_level) AS
 ( SELECT bone, connected_to_the, 0  FROM skeleton 
   WHERE bone = 'head'                         
 UNION ALL
   SELECT s.bone, s.connected_to_the , r.the_level + 1
   FROM skeleton s, skellarchy r
   WHERE r.bone = s.connected_to_the           
 )
SEARCH DEPTH FIRST BY bone SET bone_order
CYCLE bone SET is_a_cycle TO 'Y' DEFAULT 'N'
SELECT lpad(' ',2*the_level, ' ') || bone AS bone_tree , the_level,
  lead(the_level) OVER (ORDER BY bone_order) AS next_level,
  CASE 
    WHEN the_level < lead(the_level) OVER (ORDER BY bone_order) THEN NULL
    ELSE 'LEAF'
  END is_leaf
FROM skellarchy
WHERE the_level < 8 
ORDER BY bone_order;

BONE_TREE                                                     THE_LEVEL NEXT_LEVEL IS_L
------------------------------------------------------------ ---------- ---------- ----
head                                                                  0          1
  neck                                                                1          2
    shoulder                                                          2          3
      arm                                                             3          4
        wrist                                                         4          5
          finger                                                      5          3 LEAF
      back                                                            3          4
        a rib                                                         4          4 LEAF
        b rib                                                         4          4 LEAF
        c rib                                                         4          4 LEAF
        hip                                                           4          5
          thigh                                                       5          6
            knee                                                      6          7
              leg                                                     7            LEAF      <<<=====

The leg is falsely identified as a leaf, and NEXT_LEVEL comes out as NULL, even though the ‘leg’ row has a child row. Why is that? It’s because this solution uses the LEAD analytic function. With analytic functions, WHERE clauses are evaluated before the analytic functions.

Highlighting the relevant bits from the query:

WITH skellarchy AS ...[recursive WITH subquery]...
SELECT ... LEAD(the_level) OVER (ORDER BY bone_order) AS next_level ... --analytic function
FROM skellarchy
WHERE the_level < 8 ...                                                 --where clause

To quote the documentation:

Analytic functions compute an aggregate value based on a group of rows…. The group of rows is called a window and is defined by the analytic_clause. For each row, a sliding window of rows is defined. The window determines the range of rows used to perform the calculations for the current row…. Analytic functions are the last set of operations performed in a query except for the final ORDER BY clause. All joins and all WHERE, GROUP BY, and HAVING clauses are completed before the analytic functions are processed.

In the query above, “where the_level < 8" will be evaluated before LEAD(the_level). The EXPLAIN PLAN shows this very clearly:

-----------------------------------------------------------------------------------------------------
| Id  | Operation                                | Name     | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                         |          |     2 |    76 |     8  (25)| 00:00:01 |
|   1 |  WINDOW BUFFER                           |          |     2 |    76 |     8  (25)| 00:00:01 |  <<=== LEAD
|*  2 |   VIEW                                   |          |     2 |    76 |     8  (25)| 00:00:01 |  <<=== filter("THE_LEVEL"<8)
|   3 |    UNION ALL (RECURSIVE WITH) DEPTH FIRST|          |       |       |            |          |
|*  4 |     TABLE ACCESS FULL                    | SKELETON |     1 |    24 |     2   (0)| 00:00:01 |
|*  5 |     HASH JOIN                            |          |     1 |    49 |     5  (20)| 00:00:01 |
|   6 |      RECURSIVE WITH PUMP                 |          |       |       |            |          |
|   7 |      TABLE ACCESS FULL                   | SKELETON |    18 |   432 |     2   (0)| 00:00:01 |
-----------------------------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   2 - filter("THE_LEVEL"<8)
   4 - filter("BONE"='head')
   5 - access("R"."BONE"="S"."CONNECTED_TO_THE")

The WINDOW BUFFER (analytic window) is evaluated after the VIEW which filters on “THE_LEVEL”<8. So, "lead(the_level) over (order by bone_order)" will be null where the_level=7, and the 'leg' wrongly identified as a leaf node. What we actually want is for the analytic function LEAD to run over the whole resultset, and only then limit the results to show the levels 0-7. The obvious way to do this is to wrap the query in a second SELECT statement:

SELECT * FROM (
  WITH skellarchy (bone, parent, the_level) AS
   ( SELECT bone, connected_to_the, 0  FROM skeleton 
     WHERE bone = 'head'                         
   UNION ALL
     SELECT s.bone, s.connected_to_the , r.the_level + 1
     FROM skeleton s, skellarchy r
     WHERE r.bone = s.connected_to_the           
   )
  SEARCH DEPTH FIRST BY bone SET bone_order
  CYCLE bone SET is_a_cycle TO 'Y' DEFAULT 'N'
  SELECT lpad(' ',2*the_level, ' ') || bone AS bone_tree , the_level,
    lead(the_level) OVER (ORDER BY bone_order) AS next_level,
    CASE 
      WHEN the_level < lead(the_level) OVER (ORDER BY bone_order) THEN NULL
      ELSE 'LEAF'
    END is_leaf
  FROM skellarchy
  ORDER BY bone_order
) WHERE the_level < 8;

BONE_TREE                                                     THE_LEVEL NEXT_LEVEL IS_L
------------------------------------------------------------ ---------- ---------- ----
head                                                                  0          1
  neck                                                                1          2
    shoulder                                                          2          3
      arm                                                             3          4
        wrist                                                         4          5
          finger                                                      5          3 LEAF
      back                                                            3          4
        a rib                                                         4          4 LEAF
        b rib                                                         4          4 LEAF
        c rib                                                         4          4 LEAF
        hip                                                           4          5
          thigh                                                       5          6
            knee                                                      6          7
              leg                                                     7          8

Now, the analytic function in the inner query is evaluated first, before the WHERE clause in the outer query. We can see this in the EXPLAIN PLAN too, of course. Now the WINDOW BUFFER (analytic window) is evaluated before the VIEW with filter(“THE_LEVEL”<8) :

------------------------------------------------------------------------------------------------------
| Id  | Operation                                 | Name     | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                          |          |     2 |  4068 |     8  (25)| 00:00:01 |
|*  1 |  VIEW                                     |          |     2 |  4068 |     8  (25)| 00:00:01 |  <<=== filter("THE_LEVEL"<8)
|   2 |   WINDOW BUFFER                           |          |     2 |    76 |     8  (25)| 00:00:01 |  <<=== LEAD
|   3 |    VIEW                                   |          |     2 |    76 |     8  (25)| 00:00:01 |
|   4 |     UNION ALL (RECURSIVE WITH) DEPTH FIRST|          |       |       |            |          |
|*  5 |      TABLE ACCESS FULL                    | SKELETON |     1 |    24 |     2   (0)| 00:00:01 |
|*  6 |      HASH JOIN                            |          |     1 |    49 |     5  (20)| 00:00:01 |
|   7 |       RECURSIVE WITH PUMP                 |          |       |       |            |          |
|   8 |       TABLE ACCESS FULL                   | SKELETON |    18 |   432 |     2   (0)| 00:00:01 |
------------------------------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   1 - filter("THE_LEVEL"<8)
   5 - filter("BONE"='head')
   6 - access("R"."BONE"="S"."CONNECTED_TO_THE")

This is one case of the general point that, as Tom Kyte explains in this Ask Tom answer,“select analytic_function from t where CONDITION” is NOT THE SAME AS “select * from (select analytic_function from t) where CONDITION”.

So, to sum up my last few posts, we can do everything that CONNECT BY can do with the 11g recursive WITH syntax. Plus, the recursive WITH syntax makes it easy to express simple recursive algorithms in SQL.

---

Republished with permission. Original URL: http://rdbms-insight.com/wp/?p=135

---