【IT168 专稿】随着信息化的普及，信息系统覆盖到各行各业，根据实际业务需求，对数据库的查询方式越来越复杂。子查询在复杂查询中的使用率较高，其性能直接影响到业务处理效率，因此，优化子查询对于DBA和开发人员是需要掌握的一项技术。如果数据库内部可以对子查询进行优化处理，则一方面大大减少了技术人员的工作量，另一方面也简化了SQL语句的复杂度。DM7对子查询进行了大量优化处理，提升了子查询的性能。下面以DM7在相关子查询的优化为例进行阐述。
概述
本文中对子查询的描述使用术语内表和外表。子查询内出现的表称之为内表;只在子查询之外出现的表称之为外表。
子查询包括相关子查询和非相关子查询。
(1)相关子查询
子查询中的过滤条件存在外表列和内表列的连接，会影响最终的查询结果。
例1：
create table t2(d1 int,d2 int);
select * from t1 where c1 in(select d1 from t2 where c2=d2);
例1中的子查询中条件为c2=d2，条件列分别属于t1和t2表。查询结果不仅要满足c1=d1，还要满足c2=d2。
(2)非相关子查询
子查询不包含外表的列，查询结果由内表决定。
例2：
create table t2(d1 int,d2 int);
select * from t1 where c1 in(select d1 from t2 where c2<10);
例2中的子查询条件为c2<10，最终结果需要满足条件c1=d1 and c2<10，查询结果不受t1表影响。
优化
1、优化前的处理方式
以外表驱动，从外表每取一条记录，遍历一遍内表，按照过滤条件判断
是否满足，如果满足则输出，否则不处理。相当于内表和外表做了一次笛卡尔集，在大数据量情况下，执行效率非常低。
例如，两张60万的数据表执行子查询，笛卡尔集会产生3600亿条记录，对这3600亿条记录进行过滤，计算量和IO量都是巨大的，执行时间是无法被用户接受的。
对于例1的查询语句，执行过程如图1所示。
▲图1 相关子查询优化前执行流程
2、优化后的处理方式
对于相关子查询的优化思想是转换为半连接进行处理，执行过程为：
(1) 读取外表的一批数据;
(2) 把满足连接条件的记录打上标记;
(3) 处理完本批数据，返回有标记(in/exists)或无标记(not in/not exists)的记录;
(4) 循环处理步骤1到步骤3，直到外表数据处理完。
把相关子查询中与内表关联的外表下放到子查询中，与内表进行连接，连接的结果包括外表的rowid，最后以rowid为连接条件与外表进行连接，根据规则进行优化处理，转换为半连接的方式，我们称这个过程为去相关性。
半连接的方式分非反半和反半两种。下面分别对相关子查询这两种优化过程进行介绍。
1. 非反半连接
非反半相关子查询的算法如下：
FOR EACH row1 IN outer table LOOP
FOR EACH row2 IN inner table LOOP
IF jc(row1, row2) == TRUE && ic(row1, row2) == TRUE THEN
row1 can return;
END IF;
END LOOP
END LOOP
算法中jc表示连接条件;ic表示in过滤条件。
从上述算法可以看出，只有同时满足jc和ic的情况下，记录才会被输出。因此，从算法中得出相关子查询可以转换为连接查询，连接条件为jc and ic。下面举例说明。
例3：
create table t2(d1 int, d2 int);
select c1,c2 from t1 where c1 in(select d1 from t2 where c2=d2);
对例3的去相关性优化过程分三步进行。
第一步：下放与子查询相关的外表到子查询中进行连接
子查询语句转换为：
执行过程如图2所示：
▲图2 下放外表执行过程图
第二步：子查询与外表以t1.rowid为条件进行半连接
原始查询改写为：select c1,c2 from t1 a,(select t1.rowid, d1 from t2 ,t1 where c2=d2) b where a.rowid=b.rowid and a.c1=b.d1;
执行过程如图3所示：
▲图3 子查询与外表半连接过程图
第三步：对于满足条件的半连接进行规则优化，条件如下：
a. 连接类型为半连接;
b. 父亲节点右孩子为cross join，其中cross join的左孩子存在于根节点左孩子列表中，则cross join节点的左孩子替换为根节点的左孩子，同时cross join变为semi join。
最终的执行过程如图4所示：
▲图4 半连接优化过程图
2. 反半连接
对于not in\not exists的相关子查询，可以转换为反半连接。算法如下所示：
FOR EACH row1 IN outer table LOOP
jc_flag = FALSE;
ic_flag = FALSE;
FOR EACH row2 IN inner table LOOP
IF jc(row1, row2) == TRUE THEN
jc_flag = TRUE; //表示存在满足join condition的记录
IF ic(row1, row2) != FALSE THEN
ic_flag = TRUE; //表示存在in contidion不为FALSE的记录
break;
END IF;
END IF;
END LOOP
//不存在满足join condition记录，也应该返回
IF jc_flag == FALSE || ic_flag == FALSE THEN
row1 can return;
END IF
END LOOP
算法中jc表示连接条件;ic表示in过滤条件。
从上述算法可以看出，连接过程中，返回记录的条件为：
a. 对于外表的任意一条记录，满足连接条件，并且不满足过滤条件;
b. 对于外表的任意一条记录，不满足连接条件。
条件a和b满足任意一个，即可返回该条记录。由于NULL值的特殊性(与任何值比较均为UNKNOWN)，需要对过滤条件进行改写，使得过滤表达式的判断结果为TRUE或者FALSE，避免出现UNKNOWN的情况。如例4所示。
例4：
create table t2(d1 int,d2 int);
select * from t1 where c1 not in(select d1 from t2 where c2=d2);
需要考虑c1列和d1列存在NULL值的情况，过滤条件改写为：
c1=d1 or c1 is null or d1 is null
这种扩展满足过滤表达式比较结果的确定性要求。语句的处理过程类似非反半子查询。
3、选择最优连接方式
相关子查询可以转换为四种半连接：哈希半连接、索引半连接、嵌套半连接、归并半连接。
相关子查询优化处理最后阶段会选择最优的连接方式。首先根据连接条件确定采用何种连接方式，等值连接条件会选择哈希\索引\归并半连接，非等值连接条件会选择嵌套半连接;然后，对各种连接方式根据代价算法进行代价计算;最后，比较各种连接方式代价，选择代价最小的连接方式，作为最终执行计划的连接方式。
下面介绍每种连接方式。
1. 哈希半连接
哈希半连接是以左表的连接列为key构造哈希表，右表的连接列进行探测来查找满足连接条件的记录。
2. 索引半连接
如果子查询的连接列为索引前导列，则可以转换相关子查询为索引半连接方式处理。处理过程为外表的数据对子查询使用索引查找，满足条件的记录返回。
3. 归并半连接
如果相关子查询的连接条件列均为索引列，则可采用归并半连接来实现。按照索引顺序，对外表、内表进行同步扫描，选择满足连接条件的记录，再根据过滤条件进行过滤得到最终结果。经过一趟归并即可完成。
4. 嵌套半连接
如果连接条件为非等值，则可转换为嵌套半连接方式处理。处理过程为外部表的单条记录去遍历内表，满足条件的记录返回。
除此之外，还包括一些优化，例如相关子查询可以转换为哈希左半连接和哈希右半连接。其中，当子查询的代价小于外表时，会采用哈希右半连接处理。处理过程类似哈希左半连接。
小结
DM7相关子查询的优化机制基于多种半连接方式和优化机制，覆盖了较多的可优化场景，极大地减少了应用开发人员对SQL语句等价改写的工作量。此优化机制在各种测试中均取得较好的效果，与优化前相比在性能上有数量级的提升。
