WITH-Clause Reloaded: Hierarchie und Rekursion

Vor ein paar Jahren hatte ich schon einmal über die „WITH-Klausel“ geschrieben, als sie noch ein relativ unbekanntes SQL-Feature war.

Mittlerweile hat sich auch die Oracle-Welt weiter gedreht, und es sind neue Möglichkeiten seit 11g hinzugekommen — z.T. Features, die mit dem ISO-Standard SQL1999 schon etwa 10 Jahre zuvor verabschiedet wurden.

Zeit also, sich einmal wieder mit der Syntax der WITH-Clause zu beschäftigen und sie mit Oracles bisherigen, proprietären Lösungen zu vergleichen!

Vergleichsszenario

Schauen wir uns eine Abfrage aus dem SQL-Einsteigerkurs an, die eine hierarchisch sortierte Liste der Tabelle „scott.emp“ ausgibt:

set autotrace traceonly
SELECT empno
     , mgr
     , level
  FROM emp
CONNECT BY PRIOR empno = mgr
 START WITH mgr IS NULL
 ORDER BY level;

Der Interessantere Teil ist hier nicht die (den meisten wohl schon hinlänglich bekannte) Ergebnismenge sondern zum Vergleich der Ausführungsplan mit Statistiken (Oracle 11.2.0.3 unter OL6):

Execution Plan
----------------------------------------------------------
Plan hash value: 2173065311

--------------------------------------------------------------------------------------
| Id  | Operation                                | Name | Rows  | Bytes | Cost (%CPU)|
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                         |      |    14 |   364 |     4  (25)|
|   1 |  SORT ORDER BY                           |      |    14 |   364 |     4  (25)|
|*  2 |   CONNECT BY NO FILTERING WITH START-WITH|      |       |       |            |
|   3 |    TABLE ACCESS FULL                     | EMP  |    14 |   112 |     3   (0)|
--------------------------------------------------------------------------------------

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

   2 - access("MGR"=PRIOR "EMPNO")
       filter("MGR" IS NULL)

Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
          6  consistent gets
          0  physical reads
          0  redo size
        635  bytes sent via SQL*Net to client
        471  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          3  sorts (memory)
          0  sorts (disk)
         14  rows processed

ISO-konform können wir dasselbe mit einer WITH-Clause erreichen. Das Stichwort hierzu lautet „Common Table Expressions (CTE)“ bzw. im Oracle-Sprech: „Recursive Subquery Factoring„, d.h., dass die WITH-Clause auf sich selbst Bezug nehmen darf. Was in der Oracle-Syntax bislang durch das Schlüsselwort „PRIOR“ erreicht wurde, nämlich der Zugriff auf den übergeordneten Datensatz, wird hier durch die Rekursion erreicht:

WITH emp_tree
  (empno, ename, mgr, depth)
AS (
  -- Hier ist der Startpunkt ("Anker")
  SELECT e.empno, e.ename, e.mgr, 0 AS depth
    FROM emp e
   WHERE e.mgr IS NULL
  -- Ab hier folgt die Rekursionsmenge
  UNION ALL
  SELECT es.empno, es.ename, es.mgr, et.depth+1 AS depth
    FROM emp_tree et
    JOIN emp es ON (et.empno = es.mgr)
)
SELECT * FROM emp_tree;

• Rekursives Subquery Factoring setzt eine Liste der zu liefernden Spalten in der Ergebnismenge voraus. Diese muss mit den Spalten innerhalb des AS(…)-Blocks übereinstimmen.
• Das frühere START WITH ist nun das erste SELECT (der „Anker“) in der WITH-Clause.
• Das frühere CONNECT BY ist nun das zweite SELECT in der WITH-Clause, wobei das PRIOR durch den JOIN von „emp“ zur WITH-Clause selbst („emp_tree“) realisiert wird.
• Anker und Rekursionsmenge müssen mit UNION ALL verbunden werden.
• Das frühere LEVEL gibt es in diesem Konstrukt nicht, es kann aber nachgebaut werden (Spalte „depth“).

Das Autotrace für den Ansatz mit WITH zeigt andere Operationen bei der SQL-Ausführung an:

Execution Plan
----------------------------------------------------------
Plan hash value: 2042363665

---------------------------------------------------------------------------------------
| Id  | Operation                                 | Name | Rows  | Bytes | Cost (%CPU)|
---------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                          |      |     3 |   138 |    10  (10)|
|   1 |  VIEW                                     |      |     3 |   138 |    10  (10)|
|   2 |   UNION ALL (RECURSIVE WITH) BREADTH FIRST|      |       |       |            |
|*  3 |    TABLE ACCESS FULL                      | EMP  |     1 |    14 |     3   (0)|
|*  4 |    HASH JOIN                              |      |     2 |    80 |     7  (15)|
|   5 |     RECURSIVE WITH PUMP                   |      |       |       |            |
|*  6 |     TABLE ACCESS FULL                     | EMP  |    13 |   182 |     3   (0)|
---------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
 3 - filter("E"."MGR" IS NULL)
 4 - access("ET"."EMPNO"="ES"."MGR")
 6 - filter("ES"."MGR" IS NOT NULL)

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
         31  consistent gets
          0  physical reads
          0  redo size
        773  bytes sent via SQL*Net to client
        471  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          5  sorts (memory)
          0  sorts (disk)
         14  rows processed

Im Vergleich zwischen der alten und der neuen Version lässt sich feststellen:

• Es gibt eine eigene Operation „UNION ALL (RECURSIVE WITH)“
• Die rekursive Variante benötigt zwei Full Scans auf „emp“, die alte Variante nur einen (das war nicht immer so)
  • Der erste Scan in Zeile 3 liefert den Startknoten; hier muss nicht immer ein Full Scan stehen, wenn der Filter über einen Index erfüllt werden kann!
  • Der zweite Scan in Zeile 6 liefert alle weiteren Zeilen, die dann rekursiv abgearbeitet werden.
• Die rekursive Variante erzeugt mehr logischen I/O und ist „teurer“.

Performance-Statistiken

Autotrace sagt leider nichts über die CPU-Belastung aus. Um ein genaues Bild zum Vergleich der beiden Varianten zu bekommen, ist daher ein Extended SQL Trace unabdingbar.

Nach mehrfachem Ausführen der beiden SQLs (wobei die erste Ausführung noch nicht Bestandteil des Traces ist, um das initiale Hard Parse nicht mitzuzählen), zeigt sich im Tracefile Analyzer des SQL Developer folgendes Bild:

• Die summierte CPU-Last ist in der CTE-Variante mehr als zweimal so hoch!
• Die Laufzeit ist in der CTE-Variante mehr als dreimal so hoch.

Also alles gleich wieder vergessen und beim altbewährten CONNECT BY bleiben? Nicht unbedingt, denn CTEs sind flexibler! So müssen Anker und Rekursionsmenge nicht zwingend in derselben Tabelle liegen. Darüberhinaus kann auf die ganze Rekursionsmenge zugegriffen werden, nicht nur auf den vorherigen Datensatz (den PRIOR, eben). ANSI-/ISO-Konformität kann auch ein Argument sein, und nicht zuletzt kann der Code auch mal lesbarer sein als die CONNECT BY-Variante.

Beispiel 2

Dem oberen Beispiel soll noch eine Spalte hinzugefügt werden, in der der Pfad zum jeweiligen Topmanager aufgeführt ist. Außerdem sollen jeweils die zu einem Manager gehörenden Mitarbeiter zusammen aufgelistet werden, bevor der nächste Manager gelistet wird.

Dies kann direkt mit einer CTE gelöst werden, ohne Zuhilfenahme externer Funktionen:

WITH emp_tree
  (empno, ename, mgr, depth, mgr_list)
AS (
  SELECT e.empno, e.ename, e.mgr, 0 AS depth
       , CAST(e.mgr AS VARCHAR2(2000))
    FROM emp e
   WHERE e.mgr IS NULL
  UNION ALL
  SELECT es.empno, es.ename, es.mgr, et.depth+1 AS depth
       , CAST(et.mgr_list || NVL2(et.mgr_list, ' <= ', '') || es.mgr AS VARCHAR2(2000))
    FROM emp_tree et
    JOIN emp es ON (et.empno = es.mgr)
)
SEARCH DEPTH FIRST BY ename SET seq
SELECT empno, ename, mgr_list FROM emp_tree;

Ergebnis:

EMPNO ENAME      MGR_LIST
----- ---------- --------------------
 7839 KING
 7698 BLAKE      7839
 7499 ALLEN      7839 <= 7698
 7900 JAMES      7839 <= 7698
 7654 MARTIN     7839 <= 7698
 7844 TURNER     7839 <= 7698
 7521 WARD       7839 <= 7698
 7782 CLARK      7839
 7934 MILLER     7839 <= 7782
 7566 JONES      7839
 7902 FORD       7839 <= 7566
 7369 SMITH      7839 <= 7566 <= 7902
 7788 SCOTT      7839 <= 7566
 7876 ADAMS      7839 <= 7566 <= 7788

Das war noch ein sehr einfaches Beispiel; wer die volle Eleganz der CTE auskosten möchte, kann ja ein Sudoku mit SQL lösen!

Weblinks

• Oracle 12.1: Recursive Subquery Factoring
• Oracle 12.1: Recursive Subquery Factoring Examples
• Wikipedia (en): Common Table Expressions
• http://stackoverflow.com/questions/1731889/cycle-detection-with-recursive-subquery-factoring
• Christian Antognini: Related-Combine Operation „UNION ALL (RECURSIVE WITH)
• Als ich schon einen guten Teil des Artikels zusammen hatte, bin ich auf diesen ähnlichen und ausführlichen Artikel von Rob van Wijk gestoßen.