分类：
2008-10-15 16:27:06
1.层次查询环的判断
1.1 环的出现
层次查询中的环指的是作为某一行数据祖先结点的行又作为该行的子结点出现的情况。下面，我们通过一个例子来说明层次查询中环的出现，建立如下数据：
| create table t1(parent int,value int); insert into t1 values(1,2); insert into t1 values(2,3); insert into t1 values(2,4); insert into t1 values(3,5); insert into t1 values(3,6); insert into t1 values(5,2); |
按照如下层次查询语句的连接条件，表t1的数据可以组成如图1的结构。
| select * from t1 connect by prior value=parent start with value=2; |
图1 t1数据的层次结构
如图1所示，根据连接条件prior value = parent，作为(5，2)祖先结点的数据行(2，3)又作为其子结点出现，这样就形成了环;而(2，4)虽然与(2，3)同是(1，2)的子结点，但由于不是(5，2)的直接祖先，所以作为其子结点出现也并不能形成环。
利用上述层次查询语句进行查询，结果报错。
1.2 中判断环的标准分析
按照环的定义，逻辑上很容易进行环的判断，但是层次查询可以通过NOCYCLE关键字来屏蔽掉形成环的数据;CONNECT_BY_ISCYCLE伪列在当前行的祖先结点又出现在其子结点时返回1，所以我们需要进一步研究层次查询中形成环的标准。
下面通过NOCYCLE关键字和CONNECT_BY_ISCYCLE、LEVEL等伪列来研究层次查询出现环的判断。
对上一节表t1的数据，进行如下查询：
[NextPage]
| Select level, connect_by_iscycle,connect_by_isleaf,parent, value From t1 Connect by nocycle prior value = parent Start with parent =1; |
查询的结果为：
| LEVEL CONNECT_BY_ISCYCLE CONNECT_BY_ISLEAF PARENT VALUE ---------- ------------------ ----------------- ---------- ---------- 1 0 0 1 2 2 0 0 2 3 3 1 1 3 5 3 0 1 3 6 2 0 1 2 4 |
由结果来看，元组(3，5)的CONNECT_BY_ISCYCLE的值为1，屏蔽掉了其子结点(5，2)，而(5，2)并没有出现在其祖先结点中，但(5，2)的VALUE列的值2在其祖先结点(1，2)中已经出现过了。
由此推断，Oracle中层次查询的环的判断标准并不是判断子结点整个元组是否出现在祖先元组中，而是根据连接条件中表示父结点的PRIOR关键字标注的表达式的值是否在祖先结点中出现来进行判断的。
2.层次查询过滤条件的处理
层次查询语法中，使用WHERE语句来对层次查询的结果进行过滤，本节将就层次查询语句中的WHERE语句的处理进行分析。
2.1 单表层次查询过滤条件的处理
对单表进行层次查询时，WHERE语句只负责过滤数据，在得到层次查询的结果集进行判断，将满足WHERE语句指定的逻辑表达式的元组返回。
2.2 多表层次查询过滤条件的处理
对多表进行层次查询，层次查询的直接对象是多个表连接之后的数据集。而WHERE语句中的逻辑表达式如何处理是个问题。有两种合理的处理方式：
WHERE语句不进行特殊的处理，以所有表的笛卡儿集为层次查询的对象，然后将WHERE语句作为过滤层次查询后的过滤条件。
对WHERE语句中的逻辑表达式进行处理，根据相应的策略将where语句中的一部分逻辑表达式作为连接条件下放的层次查询下层的连接中去。这样的话层次查询的直接对象是以连接条件选择的笛卡儿集的一部分数据。而余下的逻辑表达式继续作为过滤条件对层次查询的结果集进行过滤。
也就是对例如 select * from t1,t2 where t1.f1=t2.c1 connect by prior t1.f1=t1.f2这样的语句。决定层次查询的直接对象到底是t1×t2 还是σt1.f1=t2.c1(t1×t2)的问题。下面利用如下数据就WHERE语句逻辑表达式的各种情况对Oracle的实现进行研究。
表t1:
| Drop table t1; Create table t1( a int, p int, c int); Insert into t1 values(0,0,1); Insert into t1 values(0,1,11); Insert into t1 values(0,11,111); Insert into t1 values(1,0,1); Insert into t1 values(1,1,11); Insert into t1 values(1,11,111); |
表t2:
[NextPage]
| Drop table t2; Create table t2( a int); Insert into t2 values(0); Insert into t2 values(1); |
简单情况1
利用如下语句来分析当WHERE所有子逻辑表达式都只涉及一个表的情况。
语句1：
| Select level, sys_connect_by_path(t2.a,'/') path_a2, sys_connect_by_path(t1.a,'/') path_a1, sys_connect_by_path(p,'/') path_p, sys_connect_by_path(c,'/') path_c,t2.a,t1.a,p,c from t1,t2 where t1.a=1 connect by prior c=p start with p=0 and t1.a=1 and t2.a=0; |
查询的结果为：
|
LEVEL |
PATH_A2 |
PATH_A1 |
PATH_P |
PATH_C |
A |
A |
P |
C |
|
1 |
/0 |
/1 |
/0 |
/1 |
0 |
1 |
0 |
1 |
|
3 |
/0/0/1 |
/1/0/1 |
/0/1/11 |
/1/11/111 |
1 |
1 |
11 |
111 |
|
3 |
/0/0/0 |
/1/0/1 |
/0/1/11 |
/1/11/111 |
0 |
1 |
11 |
111 |
|
3 |
/0/1/1 |
/1/0/1 |
/0/1/11 |
/1/11/111 |
1 |
1 |
11 |
111 |
|
3 |
/0/1/0 |
/1/0/1 |
/0/1/11 |
/1/11/111 |
0 |
1 |
11 |
111 |
|
2 |
/0/1 |
/1/1 |
/0/1 |
/1/11 |
1 |
1 |
1 |
11 |
|
3 |
/0/1/1 |
/1/1/1 |
/0/1/11 |
/1/11/111 |
1 |
1 |
11 |
111 |
|
3 |
/0/1/0 |
/1/1/1 |
/0/1/11 |
/1/11/111 |
0 |
1 |
11 |
111 |
|
2 |
/0/0 |
/1/1 |
/0/1 |
/1/11 |
0 |
1 |
1 |
11 |
|
3 |
/0/0/1 |
/1/1/1 |
/0/1/11 |
/1/11/111 |
1 |
1 |
11 |
111 |
|
3 |
/0/0/0 |
/1/1/1 |
/0/1/11 |
/1/11/111 |
0 |
1 |
11 |
111 |
为了方便分析，我会在查询结构之后将查询结果用图表示。框中数据的顺序为t2.a,t1.a,t1.p,t1.c。上述的结果的层次结构为如图2，图中虚线框的数据表示层次查询中在路径信息中出现但没有在结果中出现的数据，但是connect by查询之后被WHERE语句过滤掉的数据。
[NextPage]
从结果可以看出，层次查询结果的路径信息中有(0,0,1,11)元组，但是却没有出现在结果中，该元组在层次查询之后过滤掉了，也就是说该语句的采取的处理方式是和单表相同的层次查询的where语句的处理方式：层次查询的直接对象是t1×t2，connect by查询之后的数据集用条件t1.a=1进行过滤;而不是对σt1.a=1(t1×t2)的数据集进行connect by查询。
如果WHERE语句的所有子逻辑表达式都只涉及了一个表的话，这样的WHERE语句不会作为多个表的连接条件，它将作为过滤条件在层次查询得到结果之后将结果集中满足条件的元组返回。
简单情况2
下面利用如下语句来分析当WHERE所有子逻辑表达式都只涉及多个表的情况。
语句2：
| Select level, sys_connect_by_path(t2.a,'/') path_a2, sys_connect_by_path(t1.a,'/') path_a1, sys_connect_by_path(p,'/') path_p, sys_connect_by_path(c,'/') path_c,t2.a,t1.a,p,c from t1,t2 where t1.a=t2.a connect by prior c=p start with p=0 and t1.a=1; |
查询的结果为：
|
LEVEL |
PATH_A2 |
PATH_A1 |
PATH_P |
PATH_C |
A |
A |
P |
C |
|
1 |
/1 |
/1 |
/0 |
/1 |
1 |
1 |
0 |
1 |
|
2 |
/1/0 |
/1/0 |
/0/1 |
/1/11 |
0 |
0 |
1 |
11 |
|
3 |
/1/0/0 |
/1/0/0 |
/0/1/11 |
/1/11/111 |
0 |
0 |
11 |
111 |
|
3 |
/1/0/1 |
/1/0/1 |
/0/1/11 |
/1/11/111 |
1 |
1 |
11 |
111 |
|
2 |
/1/1 |
/1/1 |
/0/1 |
/1/11 |
1 |
1 |
1 |
11 |
|
3 |
/1/1/0 |
/1/1/0 |
/0/1/11 |
/1/11/111 |
0 |
0 |
11 |
111 |
|
3 |
/1/1/1 |
/1/1/1 |
/0/1/11 |
/1/11/111 |
1 |
1 |
11 |
111 |
如果语句2也是按照语句1相同的处理，以t1×t2作为connect by查询的直接对象，where语句被作为过滤器使用，那么在结果的路径信息中一定会出现t1.a<>t2.a的元组。但从上面的结果来看，层次查询的结果和路径中均没有出现t1.a<>t2.a的元组，我们可以肯定：语句2种的where语句不是作为connect by查询之后的过滤器，而是作为t1和t2的连接条件成为了connect by查询之前对其查询数据的过滤条件;也就是说，层次查询的不再是对t1×t2;而是对σt1.a=t2.a(t1×t2)的数据集进行connect by查询。
[NextPage]
对于其中所有的单个逻辑表达式都涉及多个表的where语句，是将整个where语句作为connect by查询前的多表的连接条件使用。
之前的两个WHERE语句都是单纯的由一类逻辑表达式(涉及表的个数)构成。但对于同时含有两种类型的WHERE语句，理论上有以下几种处理方式：
1. 全部作为过滤条件，在connect by查询之后进行;
2. 全部作为连接条件，在connect by查询之前进行;
3. 一部分作为连接条件，一部分作为过滤条件。
下面将探讨各种情况下由两种逻辑表达式构成的查询。
简单情况3
情况3讨论由AND连接的不同种类的逻辑表达式的WHERE语句的处理情况。
语句3：
| Select level, sys_connect_by_path(t2.a,'/') path_a2, sys_connect_by_path(t1.a,'/') path_a1, sys_connect_by_path(p,'/') path_p, sys_connect_by_path(c,'/') path_c,t2.a,t1.a,p,c from t1,t2 where t1.a=t2.a and t1.a=1 connect by prior c=p start with p=0; |
查询结果为：
|
LEVEL |
PATH_A2 |
PATH_A1 |
PATH_P |
PATH_C |
A |
A |
P |
C |
|
3 |
/0/0/1 |
/0/0/1 |
/0/1/11 |
/1/11/111 |
1 |
1 |
11 |
111 |
|
2 |
/0/1 |
/0/1 |
/0/1 |
/1/11 |
1 |
1 |
1 |
11 |
|
3 |
/0/1/1 |
/0/1/1 |
/0/1/11 |
/1/11/111 |
1 |
1 |
11 |
111 |
|
1 |
/1 |
/1 |
/0 |
/1 |
1 |
1 |
0 |
1 |
|
3 |
/1/0/1 |
/1/0/1 |
/0/1/11 |
/1/11/111 |
1 |
1 |
11 |
111 |
|
2 |
/1/1 |
/1/1 |
/0/1 |
/1/11 |
1 |
1 |
1 |
11 |
|
3 |
/1/1/1 |
/1/1/1 |
/0/1/11 |
/1/11/111 |
1 |
1 |
11 |
111 |
其层次结构图如图4所示。
[NextPage]
从结果的路径信息可以看出，connect by查询的直接数据集是都满足t1.a=t2.a的条件，但是路径中有t1.a=0的情况，也就是说，采用的是第3种处理方式：connect by查询的数据集不是σt1.a=t2.a and t1.a=1(t1×t2)也不是t1×t2，而是σt1.a=t2.a(t1×t2)。语句2可以等价于查询Select …… from (select …… from t1,t2 where t1.a=t2.a) where t1.a=1 connect by prior c=p start with p=0;
对于用and连接起来的单个逻辑表达式涉及到单表和多表的where语句，在层次查询时，将涉及多表的逻辑表达式作为connect by之前的连接条件使用，而余下的作为connect by查询之后的过滤条件使用。
简单情况4
情况4讨论由OR连接不同类型子逻辑表达式的WHERE语句的情况。
语句4：
| Select level, sys_connect_by_path(t2.a,'/') path_a2, sys_connect_by_path(t1.a,'/') path_a1, sys_connect_by_path(p,'/') path_p, sys_connect_by_path(c,'/') path_c,t2.a,t1.a,p,c from t1,t2 where t1.a=t2.a or t1.a=1 connect by prior c=p start with p=0 and t1.a=1 and t2.a=0; |
查询结果为：
|
LEVEL |
PATH_A2 |
PATH_A1 |
PATH_P |
PATH_C |
A |
A |
P |
C |
|
3 |
/0/0/1 |
/0/0/1 |
/0/1/11 |
/1/11/111 |
1 |
1 |
11 |
111 |
|
2 |
/0/1 |
/0/1 |
/0/1 |
/1/11 |
1 |
1 |
1 |
11 |
|
3 |
/0/1/1 |
/0/1/1 |
/0/1/11 |
/1/11/111 |
1 |
1 |
11 |
111 |
|
1 |
/1 |
/1 |
/0 |
/1 |
1 |
1 |
0 |
1 |
|
3 |
/1/0/1 |
/1/0/1 |
/0/1/11 |
/1/11/111 |
1 |
1 |
11 |
111 |
|
2 |
/1/1 |
/1/1 |
/0/1 |
/1/11 |
1 |
1 |
1 |
11 |
|
3 |
/1/1/1 |
/1/1/1 |
/0/1/11 |
/1/11/111 |
1 |
1 |
11 |
111 |
其层次结构图如图5所示。
[NextPage]
从语句4的结果的路径信息我们可以得到其层次结构图。我们可以看出，层次查询的结果集中出现了t1.a <> t2.a且t1.a=1的元组，而路径中t1.a=t2.a并且t1.a <> 1的元组却没有出现在结果集中。所以语句4中 connect by查询的数据集是σt1.a=t2.a or t1.a=1(t1×t2)。同时t1.a=1又作为connect by查询之后的过滤条件过滤掉了一部分元组。
语句4可以等价于查询：select …… from (select * from t1,t2 where t1.a=t2.a or t1.a =1) where t1.a=1 connect by prior c=p start with p=0 and t1.a=1 and t2.a=0。
由or将不同类型的单个逻辑表达式连接起来的where语句，其整个语句将会作为connect by查询前的连接条件使用，而其中的涉及单个表的逻辑表达式同时又作为connect by查询之后的过滤条件使用。
综上我们可以总结一下几种简单情况下WHERE语句的处理方式。
首先将单个布尔表达式定义为两种类型。
类型1：诸如a=1的情况，单个布尔表达式最多只涉及一个表;
类型2：诸如t1.a=t2.b的情况，布尔表达式涉及两个以上的表。
相应的，由and或or等连接起来的布尔表达式子句也分为两种类型。
类型A：connect by执行后的过滤条件;
类型B：connect by执行前的连接条件。
根据之前我们的分析，可以得出Oracle层次查询中对where语句进行以下处理：
1、全部由类型1布尔表达式构成的子句，整个子句为A类型子句;
2、全部由类型2布尔表达式构成的子句，整个子句是B类型子句;
3、由and连接多个A类型子句和B类型子句构成的子句，其中所有A类型子句用and连接后为一个新的A类型子句;所有的B类型子句式用and连接后为一个新的B类型子句;
4、由or连接的A类型和B类型子句，整个子句为B类型子句;而其中所有A类型子句用or连接后成为一个新的A类型子句。
复杂的情况
之前几节分析了4中简单的情况，但是在查询时会出现更加复杂的，诸如a=b and c=d or c=1 或((a=b or b=1)and c=d )or c=1之类的由and和or共同组成的，同时单个表达式有的涉及单表有的涉及多表的情况。下面我们就层次查询应对这样的WHERE语句其进行的处理进行分析。
首先需要说明一下逻辑表达树的结构，逻辑表达式可以转化为一个树结构，例如(a=b or b=1)and c=d and d=1这样的逻辑表达式，它转化之后的逻辑表达树应如图6所示。
之后就可以根据简单情况下的策略来决定各个分支的策略。我们根据得到的标准分析这个逻辑表达式(假设a、b属于不同的表，c、d属于不同的表)如图7所示。
[NextPage]
虚线：类型1布尔表达式 A类型子句
实线：类型2布尔表达式 B类型子句
可以根据得到的4条标准删除表达式中不需要作为过滤条件的单个逻辑表达式构成一个新的逻辑表达式，再对其进行一定的调整得到作为connect by查询之后的过滤条件的新的逻辑表达式。同样的，删除不能作为连接条件的单个逻辑表达式，调整之后得到新的作为连接条件的逻辑表达式。
对于上面的逻辑表达式，我们可以试着分析当其在层次查询的WHERE语句出现时的处理方式。删除一定的单个逻辑表达式之后，作为过滤条件的逻辑表达式的结构如图8所示：
调整之后
[NextPage]
调整之前
而作为连接条件的逻辑表达式的结构如图9所示：
这样作为connect by查询之前的连接条件是(a=b or b=1) and c=d，connect by查询之后的过滤条件是b=1 and d=1 and (a=1 or c=2)。
如果出现where (a=b or b=1)and c=d and d=1 and (a=1 or c=2)的层次查询语句就可以等价于查询 select …… from (select * from …. Where (a=b or b=1) and c=d) where b=1 and d=1 and (a=1 or c=2) connect by……。
利用逻辑表达式的逻辑树，再根据几种简单情况的结论，可以将复杂的WHERE语句中作为connect by语句执行前后的部分区分出来，从而减少一些不必要的操作。
3 层次查询性能优化
按照基础篇介绍的层次查询运行的算法，层次查询的性能可以说是线形的。本节将就层次查询性能的优化进行探讨。
3.1层次查询结果集的特点
利用如下数据来说明层次查询结果集的特点。
| Drop table t1; Create table t1 (p int, c int); Insert into t1 values(1,2); Insert into t1 values(2,3); Insert into t1 values(2,4); Insert into t1 values(3,5); Insert into t1 values(4,5); Insert into t1 values(5,6); Insert into t1 values(6,7); |
利用如下语句进行查询：
[NextPage]
| Select * from t1 connect by prior c=p start with p=1; |
查询的结果为：
| P C ---------- ---------- 1 2 2 3 3 5 5 6 6 7 2 4 4 5 5 6 6 7 |
从查询的结果我们会发现，在结果集中存在相同的部分。这是因为(2，3)(2，4)两个分支都有共同的子孙节点(5，6)。
在层次查询中，我们可以推断出以下两个特点。
特点1
对于相同的层次连接条件，以某结点为根的层次查询形成的树(图的话解开形成树)是确定不变的。
可以把整个查询对象的所有元组看作是一个数据集A，层次连接条件可以看作是A到A上的一个映射函数。
对于同一个映射函数f，对于结点p，其值域V是确定不变的;而对于p’∈V，p’的值域V’也是确定不变的。所以以p为根结点的子树是确定不变的。
特点2
如果一个结点已经在之前的层次查询中查询过，那么对于相同的层次连接条件，以该节点为根的子树在之前的层次查询中必定被查询遍历过。
由特点1知p为根节点形成的树是确定的，而层次查询是从根到叶结点的。如果p有子树，那么根据连接条件，必定可以扫描到p的子结点，进而遍历p为根的子树。
因此，如果p被层次查询查询到，以其为根的子树中所有的子结点必定被查询到。
由于以上两个特点，为层次查询性能优化提供了可能。
3.2加入结果重用的层次查询策略
如果层次数据中，多个不同的结点拥有共同的子孙节点，根据上一节的论述，以这个子孙节点为根节点的子树是相同的。我们可以不再从表中查询数据而是直接使用之前的查询结果。
要重用之前的部分查询结果，我们需要注意以下几点：
1、之前结果的缓存;
2、重用的结果是之前全部结果的一部分，如何在之前结果中快速的定位到需要重用的部分;
[NextPage]
3、如何正确的保证重用数据的结束。
之前结果集的缓存可以通过B树来实现，而且可以通过B树快速的实现数据的定位，因为层次查询的结果是先根遍历，所以在先前的结果集中，其所有子节点的LEVEL一定小于该元组的LEVEL，当我们发现其后某个元组的LEVEL不小于重用的根元组的LEVEL时，也就可以确定重用的结束。
另外，我们还需要考虑在重用的结果集中又出现重用的情况，以此，我们需要对结构进行一定的设计和修改。
利用如下的数据结构进行结果集的重用：
Reuse_tree
B树结构，用来保存结果集，其保存数据的结构为(c1,c2,…., id, level, type, ctree_location)。
其中c1, c2等是原始的数据;id是此B树中元组的标识，也是查询的关键字;level保存了在该数据出现时所在的层次;type表明该元组是否是之前已经出现的某个重用子树的根节点;如果是，ctree_location定位到子树的位置。
Reuse_ind_tree
B树结构，用来索引Reuse_tree，数据节点的结构为(c1,c2,….,id)。
其中c1, c2等是原始的数据，是查询的关键字;id是Reuse_tree中元组的标识，外键。
Reuse_info
一个在嵌套重用情况下保存原始信息的数据结构，其保存的内容有：(pbc, root_level, current_root_level)。
其中，pbc为B树中的游标位置，root_level为重用子树的根节点在Reuse_tree中的LEVEL值，current_root_level为重用子树的根节点在本次查询中的LEVEL值。
Reuse_info_lst
Reuse_info的列表。
如此，我们结果重用的策略为
1、根据层次查询连接条件查询得到一个元组;
2、根据元组的数据查询Reuse_ind_tree，如果查询到，进入步骤3;否则将元组加入到Reuse_tree和Reuse_ind_tree，进入步骤1;
3、根据Reuse_ind_tree中查询结果的id值查询定位Reuse_tree;
4、记录LEVEL;
5、将当前元组的数据返回给上层，如果type为重用子树，得到ctree_location，进入步骤6;否则进入步骤7;
[NextPage]
6、利用Reuse_info记录中断位置，加入到Reuse_info_lst中，根据ctree_location查询Reuse_tree，定位数据位置，记录得到新的LEVEL，进入步骤7;
7、B树游标向后移到，如果不是最大记录，进入步骤7，否则进入步骤9;
8、如果当前LEVEL’ < LEVEL，进入步骤5;否则进入步骤9;
9、如果Reuse_info_lst内有节点，得到最后一个节点，恢复到相应的位置，B树游标后移，如果不是最大记录，进入步骤5，否则结束。
3.3优化效果
环境
CPU：P4 2.20G
RAM：1GB
操作系统： 2000 SP4
测试数据
| Drop table t1; Create table t1 (p int, c int); Create or replace procedure p1 As I int; Begin For I in 1 .. 10000 loop Insert into t1 values(I, I+1); Insert into t1 values(I+10004,I+10005); End loop; End; Call p1; Create index ind_1 on t1(p); |
以下各个语句的执行结果
| 无结果重用的语句--------------------------------------------------------------- Select count(1) from t1 connect by prior c = p start with p=1 or p=10005; 结果：19999 时间：达梦：2.5s oracle：2.8s Select count(1) from t1 connect by prior c = p start with p=1; 结果：10000 时间：优化前：1.6s 优化后：1.7s oracle：1.8s 有结果重用的语句------------------------------------------------------------- Select count(1) from t1 connect by prior c = p start with p=1 or p=2; 结果：19999 时间：优化前：2.5s 优化后：2.3s oracle：2.1s Select count(1) from t1 connect by prior c = p start with p < 10; 结果：89964 时间：优化前：12s 优化后：2.5s oracle：2.2s Select count(1) from t1 connect by prior c = p start with p < 20; 结果：189829 时间：优化前：23s 优化后：2.7s oracle：2.4s Select count(1) from t1 connect by prior c = p start with p < 100; 结果：985149 时间：优化前：124s 优化后：5.3s oracle：4.2 |
从结果来看，优化前，对没有重用结果集的查询，我们和oracle的性能相同，但是，对于能重用结果集的查询，达梦的时间仍是线形增长，效率远远低于Oracle;优化后，在能够重用结果的查询中，达梦层次查询的性能与Oracle基本相同。
结论
以上是对层次查询中一些较复杂特性的探讨。依照环的判断标准，可以在查询中准确有效的判断与屏蔽数据形成的环;多表情况下WHERE语句的下放和结果集重用的优化都能有效的提高层次查询的效率。
