oracle递归with

朴灿烈づ我的快乐病毒、 2021-09-27 09:00 599阅读 0赞

*   *  简介
     *  基本语法
        
         *  结果集顺序
     *  与connect相关语法的等效替换
        
         *  LEVEL
         *  CONNECT\_BY\_ROOT
         *  SYS\_CONNECT\_BY\_PATH
         *  NOCYCLE and CONNECT\_BY\_ISCYCLE
 *  递归with语法对connect语法的改进
    
     *  参考资料

## 简介 ##

递归with（Recursive WITH Clauses）是一个主要用于层次查询（Hierarchical Queries）的语法。要使用它，需要oracle的版本为Oracle 11g Release 2及以上。这个语法可以看成是对connect语法的补充。

## 基本语法 ##

建立测试数据

DROP TABLE tab1 PURGE;
    
    CREATE TABLE tab1 ( id NUMBER, parent_id NUMBER, CONSTRAINT tab1_pk PRIMARY KEY (id), CONSTRAINT tab1_tab1_fk FOREIGN KEY (parent_id) REFERENCES tab1(id) );
    
    CREATE INDEX tab1_parent_id_idx ON tab1(parent_id);
    
    INSERT INTO tab1 VALUES (1, NULL);
    INSERT INTO tab1 VALUES (2, 1);
    INSERT INTO tab1 VALUES (3, 2);
    INSERT INTO tab1 VALUES (4, 2);
    INSERT INTO tab1 VALUES (5, 4);
    INSERT INTO tab1 VALUES (6, 4);
    INSERT INTO tab1 VALUES (7, 1);
    INSERT INTO tab1 VALUES (8, 7);
    INSERT INTO tab1 VALUES (9, 1);
    INSERT INTO tab1 VALUES (10, 9);
    INSERT INTO tab1 VALUES (11, 10);
    INSERT INTO tab1 VALUES (12, 9);
    COMMIT;

<table> 
 <thead> 
  <tr> 
   <th>ID</th> 
   <th>PARENT_ID</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td>7</td> 
  </tr> 
  <tr> 
   <td>9</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>10</td> 
   <td>9</td> 
  </tr> 
  <tr> 
   <td>11</td> 
   <td>10</td> 
  </tr> 
  <tr> 
   <td>12</td> 
   <td>9</td> 
  </tr> 
 </tbody> 
</table>

这是一个有父子关系的表。  
传统的写法是这样的

select * from tab1 t1 start with t1.parent_id is null connect by prior t1.id = t1.parent_id;

现在，我们有了一个新的写法。

with t1(id, parent_id) as (
    
    select*from tab1 t0 where t0.parent_id is null -- Anchor member. union all select t2.id, t2.parent_id from tab1 t2, t1 -- Recursive member. where t2.parent_id = t1.id ) select*from t1;

<table> 
 <thead> 
  <tr> 
   <th>ID</th> 
   <th>PARENT_ID</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>9</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td>7</td> 
  </tr> 
  <tr> 
   <td>10</td> 
   <td>9</td> 
  </tr> 
  <tr> 
   <td>12</td> 
   <td>9</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>11</td> 
   <td>10</td> 
  </tr> 
 </tbody> 
</table>

来自官方的解释

> Basic Hierarchical Query
> 
> A recursive subquery factoring clause must contain two query blocks combined by a UNION ALL set operator. The first block is known as the anchor member, which can not reference the query name. It can be made up of one or more query blocks combined by the UNION ALL, UNION, INTERSECT or MINUS set operators. The second query block is known as the recursive member, which must reference the query name once.
> 
> The following query uses a recursive WITH clause to perform a tree walk. The anchor member queries the root nodes by testing for records with no parents. The recursive member successively adds the children to the root nodes.

这真是个很奇葩的语法。union all不是一个合并结果集的语法，而是成为了一个构成语法的关键词。

with中的语句必须是由union all分开的两部分。第一部分的作用是确定根节点，这一部分不会参与到递归当中。它相当于start with。第二部分可以接收来自上一层级的数据。相当于connect之后的语句。

### 结果集顺序 ###

> The ordering of the rows is specified using the SEARCH clause, which can use two methods.
> 
> BREADTH FIRST BY : Sibling rows are returned before child rows are processed.  
> DEPTH FIRST BY : Child rows are returned before siblings are processed.

根据刚才的例子可以看出，默认的排序是广度优先的。如果要改成深度优先，需要这么写

WITH t1(id, parent_id) AS (
      -- Anchor member.
      SELECT id, parent_id FROM tab1 WHERE parent_id IS NULL UNION ALL -- Recursive member. SELECT t2.id, t2.parent_id FROM tab1 t2, t1 WHERE t2.parent_id = t1.id ) SEARCH DEPTH FIRST BY id SET order1 SELECT id, parent_id FROM t1 ORDER BY order1;

## 与connect相关语法的等效替换 ##

### LEVEL ###

WITH t1(id, parent_id, lvl) AS (
      -- Anchor member.
      SELECT id, parent_id, 1 AS lvl FROM tab1 WHERE parent_id IS NULL UNION ALL -- Recursive member. SELECT t2.id, t2.parent_id, lvl+1 FROM tab1 t2, t1 WHERE t2.parent_id = t1.id ) SEARCH DEPTH FIRST BY id SET order1 SELECT id, parent_id, RPAD('.', (lvl-1)*2, '.') || id AS tree, lvl FROM t1 ORDER BY order1;

<table> 
 <thead> 
  <tr> 
   <th>ID</th> 
   <th>PARENT_ID</th> 
   <th>TREE</th> 
   <th>LVL</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td></td> 
   <td>1</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>1</td> 
   <td>..2</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>2</td> 
   <td>….3</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>2</td> 
   <td>….4</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>4</td> 
   <td>……5</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>4</td> 
   <td>……6</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>1</td> 
   <td>..7</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td>7</td> 
   <td>….8</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>9</td> 
   <td>1</td> 
   <td>..9</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>10</td> 
   <td>9</td> 
   <td>….10</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>11</td> 
   <td>10</td> 
   <td>……11</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>12</td> 
   <td>9</td> 
   <td>….12</td> 
   <td>3</td> 
  </tr> 
 </tbody> 
</table>

### CONNECT\_BY\_ROOT ###

WITH t1(id, parent_id, lvl, root_id) AS (
      -- Anchor member.
      SELECT id, parent_id, 1 AS lvl, id AS root_id FROM tab1 WHERE parent_id IS NULL UNION ALL -- Recursive member. SELECT t2.id, t2.parent_id, lvl+1, t1.root_id FROM tab1 t2, t1 WHERE t2.parent_id = t1.id ) SEARCH DEPTH FIRST BY id SET order1 SELECT id, parent_id, RPAD('.', (lvl-1)*2, '.') || id AS tree, lvl, root_id FROM t1 ORDER BY order1;

<table> 
 <thead> 
  <tr> 
   <th>ID</th> 
   <th>PARENT_ID</th> 
   <th>TREE</th> 
   <th>LVL</th> 
   <th>ROOT_ID</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td></td> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>1</td> 
   <td>..2</td> 
   <td>2</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>2</td> 
   <td>….3</td> 
   <td>3</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>2</td> 
   <td>….4</td> 
   <td>3</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>4</td> 
   <td>……5</td> 
   <td>4</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>4</td> 
   <td>……6</td> 
   <td>4</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>1</td> 
   <td>..7</td> 
   <td>2</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td>7</td> 
   <td>….8</td> 
   <td>3</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>9</td> 
   <td>1</td> 
   <td>..9</td> 
   <td>2</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>10</td> 
   <td>9</td> 
   <td>….10</td> 
   <td>3</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>11</td> 
   <td>10</td> 
   <td>……11</td> 
   <td>4</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>12</td> 
   <td>9</td> 
   <td>….12</td> 
   <td>3</td> 
   <td>1</td> 
  </tr> 
 </tbody> 
</table>

### SYS\_CONNECT\_BY\_PATH ###

WITH t1(id, parent_id, lvl, root_id, path) AS (
      -- Anchor member.
      SELECT id, parent_id, 1 AS lvl, id AS root_id, TO_CHAR(id) AS path FROM tab1 WHERE parent_id IS NULL UNION ALL -- Recursive member. SELECT t2.id, t2.parent_id, lvl+1, t1.root_id, t1.path || '-' || t2.id AS path FROM tab1 t2, t1 WHERE t2.parent_id = t1.id ) SEARCH DEPTH FIRST BY id SET order1 SELECT id, parent_id, RPAD('.', (lvl-1)*2, '.') || id AS tree, lvl, root_id, path FROM t1 ORDER BY order1;

<table> 
 <thead> 
  <tr> 
   <th>ID</th> 
   <th>PARENT_ID</th> 
   <th>TREE</th> 
   <th>LVL</th> 
   <th>ROOT_ID</th> 
   <th>PATH</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td></td> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>1</td> 
   <td>..2</td> 
   <td>2</td> 
   <td>1</td> 
   <td>1-2</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>2</td> 
   <td>….3</td> 
   <td>3</td> 
   <td>1</td> 
   <td>1-2-3</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>2</td> 
   <td>….4</td> 
   <td>3</td> 
   <td>1</td> 
   <td>1-2-4</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>4</td> 
   <td>……5</td> 
   <td>4</td> 
   <td>1</td> 
   <td>1-2-4-5</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>4</td> 
   <td>……6</td> 
   <td>4</td> 
   <td>1</td> 
   <td>1-2-4-6</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>1</td> 
   <td>..7</td> 
   <td>2</td> 
   <td>1</td> 
   <td>1-7</td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td>7</td> 
   <td>….8</td> 
   <td>3</td> 
   <td>1</td> 
   <td>1-7-8</td> 
  </tr> 
  <tr> 
   <td>9</td> 
   <td>1</td> 
   <td>..9</td> 
   <td>2</td> 
   <td>1</td> 
   <td>1-9</td> 
  </tr> 
  <tr> 
   <td>10</td> 
   <td>9</td> 
   <td>….10</td> 
   <td>3</td> 
   <td>1</td> 
   <td>1-9-10</td> 
  </tr> 
  <tr> 
   <td>11</td> 
   <td>10</td> 
   <td>……11</td> 
   <td>4</td> 
   <td>1</td> 
   <td>1-9-10-11</td> 
  </tr> 
  <tr> 
   <td>12</td> 
   <td>9</td> 
   <td>….12</td> 
   <td>3</td> 
   <td>1</td> 
   <td>1-9-12</td> 
  </tr> 
 </tbody> 
</table>

### NOCYCLE and CONNECT\_BY\_ISCYCLE ###

UPDATE tab1 SET parent_id = 9 WHERE id = 1;
    COMMIT;
    
    
    WITH t1(id, parent_id, lvl, root_id, path) AS (
      -- Anchor member.
      SELECT id, parent_id, 1 AS lvl, id AS root_id, TO_CHAR(id) AS path FROM tab1 WHERE id = 1 UNION ALL -- Recursive member. SELECT t2.id, t2.parent_id, lvl+1, t1.root_id, t1.path || '-' || t2.id AS path FROM tab1 t2, t1 WHERE t2.parent_id = t1.id ) SEARCH DEPTH FIRST BY id SET order1 SELECT id, parent_id, RPAD('.', (lvl-1)*2, '.') || id AS tree, lvl, root_id, path FROM t1 ORDER BY order1;
         *
    ERROR at line 27:
    ORA-32044: cycle detected while executing recursive WITH query

如果不作处理的话，毫无疑问会报错。

WITH t1(id, parent_id, lvl, root_id, path) AS (
      -- Anchor member.
      SELECT id, parent_id, 1 AS lvl, id AS root_id, TO_CHAR(id) AS path FROM tab1 WHERE id = 1 UNION ALL -- Recursive member. SELECT t2.id, t2.parent_id, lvl+1, t1.root_id, t1.path || '-' || t2.id AS path FROM tab1 t2, t1 WHERE t2.parent_id = t1.id ) SEARCH DEPTH FIRST BY id SET order1 CYCLE id SET cycle TO 1 DEFAULT 0 SELECT id, parent_id, RPAD('.', (lvl-1)*2, '.') || id AS tree, lvl, root_id, path, cycle FROM t1 ORDER BY order1;

<table> 
 <thead> 
  <tr> 
   <th>ID</th> 
   <th>PARENT_ID</th> 
   <th>TREE</th> 
   <th>LVL</th> 
   <th>ROOT_ID</th> 
   <th>PATH</th> 
   <th>CYCLE</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>9</td> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>1</td> 
   <td>..2</td> 
   <td>2</td> 
   <td>1</td> 
   <td>1-2</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>2</td> 
   <td>….3</td> 
   <td>3</td> 
   <td>1</td> 
   <td>1-2-3</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>2</td> 
   <td>….4</td> 
   <td>3</td> 
   <td>1</td> 
   <td>1-2-4</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>4</td> 
   <td>……5</td> 
   <td>4</td> 
   <td>1</td> 
   <td>1-2-4-5</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>4</td> 
   <td>……6</td> 
   <td>4</td> 
   <td>1</td> 
   <td>1-2-4-6</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>1</td> 
   <td>..7</td> 
   <td>2</td> 
   <td>1</td> 
   <td>1-7</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td>7</td> 
   <td>….8</td> 
   <td>3</td> 
   <td>1</td> 
   <td>1-7-8</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>9</td> 
   <td>1</td> 
   <td>..9</td> 
   <td>2</td> 
   <td>1</td> 
   <td>1-9</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>9</td> 
   <td>….1</td> 
   <td>3</td> 
   <td>1</td> 
   <td>1-9-1</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>10</td> 
   <td>9</td> 
   <td>….10</td> 
   <td>3</td> 
   <td>1</td> 
   <td>1-9-10</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>11</td> 
   <td>10</td> 
   <td>……11</td> 
   <td>4</td> 
   <td>1</td> 
   <td>1-9-10-11</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>12</td> 
   <td>9</td> 
   <td>….12</td> 
   <td>3</td> 
   <td>1</td> 
   <td>1-9-12</td> 
   <td>0</td> 
  </tr> 
 </tbody> 
</table>

> The NOCYCLE and CONNECT\_BY\_ISCYCLE functionality is replicated using the CYCLE clause. By specifying this clause, the cycle is detected and the recursion stops, with the cycle column set to the specified value, to indicate the row where the cycle is detected. Unlike the CONNECT BY NOCYCLE method, which stops at the row before the cycle, this method stops at the row after the cycle.

需要注意的是，递归with语法在检测到循环后，依然会再向下递归一级，而connect语句则不会。

例子

select t1.*, level from tab1 t1 start with t1.id = 1 connect by nocycle prior t1.id = t1.parent_id;

<table> 
 <thead> 
  <tr> 
   <th>ID</th> 
   <th>PARENT_ID</th> 
   <th>LEVEL</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>9</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>1</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>2</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>2</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>4</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>4</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>1</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td>7</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>9</td> 
   <td>1</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>10</td> 
   <td>9</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>11</td> 
   <td>10</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>12</td> 
   <td>9</td> 
   <td>3</td> 
  </tr> 
 </tbody> 
</table>

# 递归with语法对connect语法的改进 #

很多人都喜欢把connect语法称为递归查询，然而严格来说这是一个错误的叫法。因为它无法把当前层所计算得到的值传递到下一层。就连官方对它的称呼都是`Hierarchical Queries in Oracle (CONNECT BY)` 。  
而递归with则彻底改变了这个情况。它的名字都带着递归 `Recursive WITH Clauses` 。

辗转相除法求最大公约数，我觉得这是最能验证递归能力的方法。它需要将两个值交换并做一个取余数的操作，再把这个结果传递到下一层中。  
先用java简单复习一下

public static int gcd(int a, int b){
            return a % b == 0 ? b : gcd(b, a % b);
        }

用sql则需要这么写

with t1(id, a1, a2) as (
    select 1, 176, 34
      from dual
    union all
    select id + 1, a2, mod(a1, a2)
      from t1
     where mod(a1, a2) > 0
    )
    select distinct first_value(t1.a2) over(order by t1.id desc) res from t1;
    
    --2

为了方便理解，我把每一步的结果输出一下

with t1(id, a1, a2) as (
    select 1, 176, 34
      from dual
    union all
    select id + 1, a2, mod(a1, a2)
      from t1
     where mod(a1, a2) > 0
    )
    select t1.* from t1;

这是一个大幅增加sql适用范围的语法，大牛们可以用这个来搞出不少骚操作。

## 参考资料 ##

[https://oracle-base.com/articles/11g/recursive-subquery-factoring-11gr2\#setup][https_oracle-base.com_articles_11g_recursive-subquery-factoring-11gr2_setup]

[https_oracle-base.com_articles_11g_recursive-subquery-factoring-11gr2_setup]: https://oracle-base.com/articles/11g/recursive-subquery-factoring-11gr2