17. Mai 2010

Hierarchische Abfragen in Oracle11g Release 2: Recursive WITH clause

English title: Hierarchical Queries in Oracle11g Release 2

Sicherlich kennen fast alle die berühmte START WITH ... CONNECT BY-Syntax, mit der man hierarchische Abfragen machen kann. Das oft gebrauchte Beispiel ist die EMP-Tabelle.
I'm sure that most of you know about the Oracle hierarchical query syntax START WITH .. CONNECT BY. And this is best demonstrated with the good ol' EMP table.
SQL> select lpad (' ', level + 1) || ename from emp 
  2  start with mgr is null connect by prior empno = mgr

LPAD('',LEVEL+1)||ENAME
--------------------------------------------------------------------------------
  KING
   JONES
    SCOTT
     ADAMS
    FORD
     SMITH
   BLAKE
    ALLEN
    WARD
    :
Das wird vielfach verwendet und funktioniert seit Jahren völlig problemlos - allerdings sagen die Lehrbücher was anderes: Der SQL Standard sieht für hierarchische Abfragen eigentlich die sog. rekursive WITH-Klausel vor. Zur "normalen" WITH-Klausel gab es schonmal ein Blog-Posting, diese wurde in der Version 11.2 wie erweitert. Ein Beispiel:
This works very well and is being implemented in many, many projects. But it's not standard SQL! For hierarchical queries the SQL standard uses the recursive WITH clause. Some time ago I had a posting about "subquery factoring" using the WITH clause. But up to 11.1 this could not be used recursively. With version 11.2 these are supported. Here is an example:
with emp_rec (empno, ename, mgr) as (
  select empno, ename, mgr
  from emp where mgr is null
  union all (
    select c.empno, c.ename, c.mgr
    from emp_rec p, emp c
    where p.empno = c.mgr
  )
) 
select ename from emp_rec
/

ENAME
----------
KING
JONES
BLAKE
CLARK
ALLEN
WARD
:
In der mit der WITH-Klausel definierten Inline View werden zunächst die Wurzeln der Hierarchie bestimmt. Dies kann eine oder auch mehrere Tabellenzeilen sein. Anschließend wird der restliche Hierarchiebaum mit einem UNION ALL angehängt - und in diesem UNION ALL referenziert sich die Inline View selbst!. Allerdings ist die Sortierung der Ergebnisse eine andere - während START WITH .. CONNECT BY direkt eine Art "Baum" zurückgibt, kommen bei der rekursiven WITH-Klausel (wenn man nichts angibt) zunächst mal die Ebene 1, dann Ebene 2 und so fort. Das lässt sich aber ändern ...
The inline view EMP_REC, defined in the WITH clause, consists of two parts. The first part selects the hierarchy's root (which can be one or more rows). The second part selects the next hierarchy level and is connected to the first using an UNION ALL. Since the second part selects itself it is being executed recursively. But the result order seems to be different from the "traditional" syntax START WITH .. CONNECT BY. While the latter one returns a tree the former returns the first hierarchy level, followed by the second one, followed by the third one and so on ... But this can be changed.
with emp_rec (empno, ename, mgr) as (
  select empno, ename, mgr
  from emp where mgr is null
  union all (
    select c.empno, c.ename, c.mgr
    from emp_rec p, emp c
    where p.empno = c.mgr
  )
) 
SEARCH DEPTH FIRST BY ename SET sort1
select ename from emp_rec
order by sort1
/

ENAME
----------
KING
BLAKE
ALLEN
JAMES
MARTIN
TURNER
:
Mit der SEARCH-Klausel lässt sich festlegen, ob die hierarchische Abfrage zunächst "in die Breite" (BREADTH) oder "in die Tiefe" (DEPTH) navigieren soll - BREADTH ist der Default. Zusätzlich wird mit der BY-Klausel festgelegt, wie innerhalb einer Hierarchieebene sortiert werden soll - der Baum lässt sich hiermit also sehr gut steuern ...
The SEARCH clause determined the result set order. DEPTH FIRST lets the database first collect one hierarchy level completely and then move to the next sibling. BREADTH FIRST is the default which collects one hierarchy level after another. The BY keyword lets you determine the row order within one hierarchy level. The SET keyword finally lets you specify a pseudocolumn name which can be used in a final ORDER BY clause in the main SQL query.
Nun würde man als erstes gerne feststellen, auf welcher Hierarchieebene sich eine bestimmte Zeile befindet ... Die START WITH .. CONNECT BY-Syntax bietet hierfür und für andere Zwecke sog. Pseudospalten an. Diese sind LEVEL, SYS_CONNECT_BY_PATH und andere.
This is well understood. But the "traditional" syntax provides additional pseudocolumns the return the current hierarchy level (LEVEL), the complete path from the tree root to the current node (SYS_CONNECT_BY_PATH), whether the current row is a leaf node or not (CONNECT_BY_ISLEAF) and some more.
select 
  level, 
  sys_connect_by_path(ename, '/') ename_path, 
  ename
from emp
start with mgr is null connect by prior empno = mgr
/

     LEVEL ENAME_PATH                               ENAME
---------- ---------------------------------------- ----------
         1 /KING                                    KING
         2 /KING/JONES                              JONES
         3 /KING/JONES/SCOTT                        SCOTT
         4 /KING/JONES/SCOTT/ADAMS                  ADAMS
         3 /KING/JONES/FORD                         FORD
         4 /KING/JONES/FORD/SMITH                   SMITH
         2 /KING/BLAKE                              BLAKE
         3 /KING/BLAKE/ALLEN                        ALLEN
Diese Pseudospalten und -Funktionen werden mit der rekursiven WITH-Klausel nicht funktionieren ...
How can these functions be used in the new hierarchical WITH clause? Can they?
with emp_rec (ebene, empno, ename, mgr) as (
  select level ebene, empno, ename, mgr
  from emp where mgr is null
  union all (
    select level ebene, c.empno, c.ename, c.mgr
    from emp_rec p, emp c
    where p.empno = c.mgr
  )
) 
select ename from emp_rec
/

FEHLER in Zeile 10:
ORA-01788: Klausel CONNECT BY in diesem Abfrageblock erforderlich
Für SYS_CONNECT_BY_PATH, SYS_CONNECT_BY_ISCYCLE und SYS_CONNECT_BY_ISLEAF gilt dasselbe: sie funktionieren nur gemeinsam mit START WITH .. CONNECT BY. Bei der rekursiven WITH-Klausel geht das aber auch - man muss hier aber quasi "Standard-SQL" bemühen. Beginnen wir mit LEVEL ...
As you might have assumed: They can't. All these functions are only available or the "traditional syntax" and not for the recursive WITH clause. But here's the good news: You just don't need them! Let's start with the LEVEL pseudocolumn - getting the hierarchy level out of the recursive WITH clause is quite easy and straightforward.
with emp_rec (ebene, empno, ename, mgr) as (
  select 1 ebene, empno, ename, mgr
  from emp where mgr is null
  union all (
    select ebene + 1 ebene, c.empno, c.ename, c.mgr
    from emp_rec p, emp c
    where p.empno = c.mgr
  )
) 
select ebene, ename from emp_rec
/

     EBENE ENAME
---------- ----------
         1 KING
         2 JONES
         2 BLAKE
         2 CLARK
         3 ALLEN
         3 WARD
         : :
Im ersten Zeil selektieren wir mit "1" einfach die Wurzelebene als Literal - im rekursiv ausgeführten zweiten Zeil addieren wir immer nur eins drauf - das Ergebnis ist das gleiche wie die LEVEL-Pseudospalte in der "traditionellen" Syntax. Kommen wir danach zu SYS_CONNECT_BY_PATH - auch das ist recht einfach ...
We just add the literal "1" (one) to the first part (selecting the tree root(s)). The second (recursive) part just increments this - and so we get an incremented number for the hierarchy level - that's easy! The next hierarchical pseudocolumn SYS_CONNECT_BY_PATH is being solved in a similar manner.
with emp_rec (ebene, path, empno, ename, mgr) as (
  select 1 ebene, '/' || ename path, empno, ename, mgr
  from emp where mgr is null
  union all (
    select ebene + 1 ebene, path || '/' || c.ename path,  c.empno, c.ename, c.mgr
    from emp_rec p, emp c
    where p.empno = c.mgr
  )
) 
search depth first by ename set sort1
select ebene, path, ename from emp_rec
/

     EBENE PATH                              ENAME
---------- --------------------------------- ----------
         1 /KING                             KING
         2 /KING/BLAKE                       BLAKE
         3 /KING/BLAKE/ALLEN                 ALLEN
         3 /KING/BLAKE/JAMES                 JAMES
         3 /KING/BLAKE/MARTIN                MARTIN
         3 /KING/BLAKE/TURNER                TURNER
Auch hier wird einfach die normale Stringverkettung benutzt. Man muss zwar ein wenig was tun, aber strenggenommen hat man mit dieser Variante sogar mehr Freiheiten als mit START WITH .. CONNECT BY, denn man kann sich seinen Pfad quasi beliebig zusammensetzen. Als nächstes käme dann die Erkennung von Zyklen in der Hierarchie - die "alte" Syntax kannte dazu die Pseudospalte CONNECT_BY_ISCYCLE ...
Again a literal is being selected in the root part and in the recursive part we use plain string concatenation to get the full path for each row. This shows that recursive subqueries allow more "freedom" in constructing the path - all SQL functions can be used here. The next function to concentrate on is CONNECT_BY_ISCYLCE (which is about detection of cycles in the hierarchy).
select 
  level, 
  ename,
  sys_connect_by_path(ename, '/') ename_path, 
  connect_by_iscycle zyklus
from emp
start with mgr is null connect by nocycle prior empno = mgr 
/

     LEVEL ENAME      ENAME_PATH                         ZYKLUS
---------- ---------- ------------------------------ ----------
         1 KING       /KING                                   0
         2 JONES      /KING/JONES                             0
         3 SCOTT      /KING/JONES/SCOTT                       0
         4 ADAMS      /KING/JONES/SCOTT/ADAMS                 0
         3 FORD       /KING/JONES/FORD                        0
         4 SMITH      /KING/JONES/FORD/SMITH                  0
         2 BLAKE      /KING/BLAKE                             0
         3 ALLEN      /KING/BLAKE/ALLEN                       0
Die CONNECT_BY_ISCYCLE Funktion gibt "0" an, wenn kein und "1", wenn ein Zyklus vorliegt. Das geht mit den neuen Syntax dann so:
CONNECT_BY_ISCYLCE gives "1" if there is a cycle and "0" if not. The new hierarchical WITH clause has special syntax for this ...
with emp_rec (ebene, path, empno, ename, mgr) as (
  select 1 ebene, '/' || ename path, empno, ename, mgr
  from emp where mgr is null
  union all (
    select ebene + 1 ebene, path || '/' || c.ename path,  c.empno, c.ename, c.mgr
    from emp_rec p, emp c
    where p.empno = c.mgr
  )
) 
search depth first by ename set sort1
cycle ename set is_cycle to 'Y' default 'N'
select ebene, path, empno, ename, is_cycle from emp_rec
/

     EBENE PATH                                   EMPNO ENAME      I
---------- --------------------------------- ---------- ---------- -
         1 /KING                                   7839 KING       N
         2 /KING/BLAKE                             7698 BLAKE      N
         3 /KING/BLAKE/ALLEN                       7499 ALLEN      N
         3 /KING/BLAKE/JAMES                       7900 JAMES      N
         3 /KING/BLAKE/MARTIN                      7654 MARTIN     N
         3 /KING/BLAKE/TURNER                      7844 TURNER     N
Man erkennt keinen besonderen Unterschied zur alten Syntax - das Umwandeln des "1" und "0" in "Y" bzw. "N" kann man mit einem DECODE auch hinbekommen. Aber weiter im Text. Die nächste Funktion der alten Syntax wäre CONNECT_BY_ROOT, also die Funktion, die zu jedem Datensatz den jeweiligen Wurzelknoten angibt - das ist wichtig, wenn es mehrere Wurzeln gibt und man diese Information insofern braucht. Um das auszutesten, kann man bei der EMP-Tabelle erstmal eine zweite Wurzel einbauen ...
It's basically the same as in START WITH .. CONNECT BY. Here we can specify the values to return for cycle/nocycle - but a simple DECODE does the job in the old syntax. So let's go on the the next pseudocolumn: CONNECT_BY_ROOT is important when a tree has more than one root - say: when you have more then one tree. You need to know the root for each row. To test this we modify the EMP table in order to get two trees ...
update emp set mgr = null where ename = 'FORD'
Erstmal die alte Syntax ...
First the old syntax ...
select 
  level, 
  ename,
  sys_connect_by_path(ename, '/') ename_path, 
  connect_by_root(ename) wurzel,
  connect_by_iscycle zyklus
from emp
start with mgr is null connect by nocycle prior empno = mgr 
/

     LEVEL ENAME      ENAME_PATH                     WURZEL         ZYKLUS
---------- ---------- ------------------------------ ---------- ----------
         1 KING       /KING                          KING                0
         2 JONES      /KING/JONES                    KING                0
         : :          :                              :                   :
         1 FORD       /FORD                          FORD                0
         2 SMITH      /FORD/SMITH                    FORD                0
Das ist mit der neuen Syntax ebenfalls sehr einfach: Die Wurzel-Knoten werden ja im ersten Teil der WITH-Abfrage selektiert, stehen also stets über den Aliasnamen bereit ... Mit der neuen Syntax sieht das dann so aus:
then new new. As you can see - this was as easy as the hierarchy level. The column is being selected in the first part and then used as-is in the second, recursive part.
with emp_rec (ebene, path, empno, ename, wurzel, mgr) as (
  select 1 ebene, '/' || ename path, empno, ename, ename wurzel, mgr
  from emp where mgr is null
  union all (
    select ebene + 1 ebene, path || '/' || c.ename path,  c.empno, c.ename, p.wurzel, c.mgr
    from emp_rec p, emp c
    where p.empno = c.mgr
  )
) 
search depth first by ename set sort1
cycle ename set is_cycle to 'Y' default 'N'
select ebene, path, empno, ename, wurzel, is_cycle from emp_rec
/

     EBENE PATH                                   EMPNO ENAME      WURZEL     I
---------- --------------------------------- ---------- ---------- ---------- -
         1 /FORD                                   7902 FORD       FORD       N
         2 /FORD/SMITH                             7369 SMITH      FORD       N
         1 /KING                                   7839 KING       KING       N
         2 /KING/BLAKE                             7698 BLAKE      KING       N
         3 /KING/BLAKE/ALLEN                       7499 ALLEN      KING       N
         3 /KING/BLAKE/JAMES                       7900 JAMES      KING       N
Bleibt als letztes die CONNECT_BY_ISLEAF-Pseudospalte, die feststellt, ob die Tabellenzeile ein "Blattknoten" des Baums ist. Diese ist als einzige etwas schwieriger umzusetzen - es gibt keine mitgelieferte Funktion dafür. Schwieriger ist das, weil die Hierarchie von der Wurzel aus aufgebaut wird - bei den Funktionen bislang (Ebene, Pfad) wurde Information von der Wurzel bis zur fraglichen Tabellenzeile quasi "mitgezogen" (die Ebene wird stets um eins hochgezählt, beim Pfad wird konkateniert). Nun ist die Situation anders: Wenn man bei der Wurzel anfängt, weiss man in der konkreten Tabellenzeile niemals, ob sie ein Blattknoten ist, da sich das erst bei der nächsten Hierarchieebene ergibt; erst wenn ich im nächsten Schritt nichts finde, liegt ein Blattknoten vor. Man könnte also mit einem Subselect arbeiten, wir sollten aber eher nach einer performanten Lösung suchen - und Lucas Jellema hat auf dem AMIS Technology Corner eine sehr schöne Lösung mit analytischen Funktionen gefunden. Angewendet auf unser Beispiel sähe das so aus:
The last one is the CONNECT_BY_ISLEAF which determines whether the current row is a leaf node in the hierarchy or not. This one is a bit tricky: There is no out-of-the-box syntax as for CYCLE and since the hierarchy is being built starting from the root we can only know (for a given row) about everything from the root row to the current row. But the information whether the current row is a leaf node is in the next row - the next hierarchy level. A first approach would be a subquery which checked whether the current row is being referenced by other rows in higher hierarchy levels - but I'd expect a bad performance for this. Lucas Jellema published a very nice solution on the AMIS Technology Corner blog. The approach described in eine his posting is based on analytical functions and solves the problem very elegant. Applied to our example this would look as follows ...
with emp_rec (ebene, path, empno, ename, wurzel, mgr) as (
  select 1 ebene, '/' || ename path, empno, ename, ename wurzel, mgr
  from emp where mgr is null
  union all (
    select ebene + 1 ebene, path || '/' || c.ename path,  c.empno, c.ename, p.wurzel, c.mgr
    from emp_rec p, emp c
    where p.empno = c.mgr
  )
) 
search depth first by ename set sort1 
cycle ename set is_cycle to 'Y' default 'N'
select ebene, path, empno, ename, wurzel, is_cycle ,
 case when ebene - lead(ebene) over (order by sort1) <0
 then 0 else 1
 end as is_leaf
from emp_rec
/

    EBENE PATH                                   EMPNO ENAME      WURZEL     I    IS_LEAF
--------- --------------------------------- ---------- ---------- ---------- - ----------
        1 /FORD                                   7902 FORD       FORD       N          0
        2 /FORD/SMITH                             7369 SMITH      FORD       N          1
        1 /KING                                   7839 KING       KING       N          0
        2 /KING/BLAKE                             7698 BLAKE      KING       N          0
        3 /KING/BLAKE/ALLEN                       7499 ALLEN      KING       N          1
        3 /KING/BLAKE/JAMES                       7900 JAMES      KING       N          1
        3 /KING/BLAKE/MARTIN                      7654 MARTIN     KING       N          1


Die Lösung funktioniert nur, wenn die SEARCH-Klausel auf DEPTH FIRST gesetzt wird. Mit Hilfe der analytischen Funktion LEAD wird nun einfach festgestellt, ob die Ebene in der nächsten Zeile der Ergebnismenge höher ist (mit analytischen Funktionen geht das). Wenn ja, dann ist die aktuelle Zeile kein Blattknoten, denn sie hat ja Child-Knoten. Wenn nein, dann liegt ein Blattknoten vor. Dieser Ansatz sollte auch mit großen Datenmengen performant arbeiten.
This only works when the SEARCH clause is set to DEPTH FIRST. Using the analytical function LEAD we get access to the next row in the query result set. Now we can compare the hierarchy level and if this is higher we know that the current row is not a leaf node. If it is equal or lower we have found a leaf node. And this approach should perform well even for larger query results.
Zusammengefasst lässt sich feststellen, dass man mit der neuen Syntax alles machen kann, was auch mit der alten geht. Funktional hat man also die Wahl. Ich denke, dass man sich nach und nach mit der neuen Syntax anfreunden sollte - einerseits ist sie Teil des SQL-Standards, andererseits hat man doch auch mehr Freiheiten bspw. beim Zusammensetzen des Pfades oder beim Berechnen der Hierarchie ... Zum Abschluß hier noch Verweise auf die Dokumentation.
To summarize it up: The new syntax allows everything that the old syntax made possible. From the functional point of the there is freedom of choice. Regarding the fact the the new recursive WITH clauses are standatd SQL and that there are some areas with even more implementation freedom I'd recommend to get familiar with this (for Oracle) new SQL approach. Finally, here are some links to the documentation.

Kommentare:

jsieben hat gesagt…

Zum Thema connect_by_isleaf funktioniert folgende Variante stabiler, weil nicht vom Suchmechanismus und Sortierung abhängig:
with hierarchie (lvl, ename, empno, is_leaf) as (
select 1 lvl, ename, empno,
(select decode(count(*), 0, 1, 0)
from emp
where mgr = m.empno) is_leaf
from emp m
where mgr is null
union all
select h.lvl + 1, e.ename, e.empno,
(select decode(count(*), 0, 1, 0)
from emp
where mgr = e.empno) is_leaf
from hierarchie h, emp e
where h.empno = e.mgr)
search depth first by ename set sort_seq
select lvl, ename, is_leaf
from hierarchy;

Beste Grüße,

Jürgen Sieben

Anonym hat gesagt…

Ich habe den Code gerade auf einer 11.2.0.3.0 DB (64bit, Oracle Linux) ausprobiert und bin auf einen seltsamen Fehler gestossen.

Beim Beispiel für den Ersatz von SYS_CONNECT_BY_PATH bekam ich gleich einen "ORA-0189: Das Ergebnis der Zeichenfolgenverkettung ist zu lang".

Ich weiß nicht ob es sich dabei um eine "Spezialität" der .2.0.3 handelt, aber man kann den Fehler ganz einfach beheben, wenn man in dem ersten Teil des Views (vor dem UNION ALL) den Ausdruck gleich mit einem CAST() auf eine entsprechende Länge setzt:
"select 1 ebene, cast( '/' || ename as varchar2(20)) path, .....".

Gruß, Niels Hecker

Jack hat gesagt…

Hallo,

ich versuche mich gerade an dieser Syntax. Vielleicht können Sie mir weiterhelfen.
Wie bekomme ich mit einer gegebenen ID z.B. die von Jones heraus, welche anderen ID's (müssten glaube die von Blake und Clark sein) sich auf der selben Ebene befinden ohne Jones als Zeile mitzuerhalten? Desweiteren soll mir das Ergebnis alle zugehörigen Children zu Blake und Clark als Zeilen liefern?

Carsten Czarski hat gesagt…

Hallo Jack,

hilft das hier ...?

with root as (
select empno, mgr from emp where ename = 'JONES'
), emp_rec (ebene, path, empno, ename, mgr) as (
select 1 ebene, '/' || e.ename path, e.empno, e.ename, e.mgr
from emp e, root r where e.mgr = r.mgr
union all (
select ebene + 1 ebene, path || '/' || c.ename path, c.empno, c.ename, c.mgr
from emp_rec p, emp c
where p.empno = c.mgr
)
)
search depth first by ename set sort1
select ebene, path, empno, ename
from emp_rec
where not path like '/JONES%'
/


Beste Grüße

-Carsten

Beliebte Postings