第2章 逻辑查询优化

查询优化器在逻辑优化阶段主要解决的问题是：如何找出SQL语句等价的变换形式，使得SQL执行更高效。

一条SQL查询语句结构复杂，包含多种类型的子句，优化操作依赖于表的一些属性信息（如索引和约束等）。可用于优化的思路包括：

❏子句局部优化。每种类型子句都可能存在优化方式，这是子句局部的优化，如等价谓词重写、WHERE和HAVING条件化简中的大部分情况，都属于这种子句范围内的局部优化。

❏子句间关联优化。子句与子句之间关联的语义存在优化的可能，如外连接消除、连接消除、子查询优化、视图重写等都属于子句间的关联优化，因为它们的优化都需要借助其他子句、表定义或列属性等信息进行。

❏局部与整体的优化。需要协同考虑局部表达式和整体的关系，如OR重写并集规则需要考虑UNION操作（UNION是变换后的整体的形式）的花费和OR操作（OR是局部表达式）的花费。

❏形式变化优化。多个子句存在嵌套，可以通过形式的变化完成优化，如嵌套连接消除。

❏语义优化。根据完整性约束、SQL表达的含义等信息对语句进行语义优化。

❏其他优化。根据一些规则对非SPJ做的其他优化、根据硬件环境进行的并行查询优化等。

各种逻辑优化技术依据关系代数和启发式规则进行。

2.1 查询优化技术的理论基础

查询优化技术的理论基础是关系代数。本节就关系代数的最基本内容进行介绍，目的是引出关系代数对查询优化的指导意义。

2.1.1 关系代数

1970年，E.F.Codd在题为《A Relational Model of Data for Shared Data Banks》的论文中提出了数据的关系模型的概念。Codd提议将关系代数作为数据库查询语言的基础。关系数据库基于关系代数。关系数据库的对外接口是SQL语句，所以SQL语句中的DML、DQL基于关系代数实现了关系的运算。

作为数据库查询语言的基础，关系模型由关系数据结构、关系操作集合和关系完整性约束三部分组成。以下是几个和关系模型有关的概念：

❏关系模型的数据结构就是我们在关系数据库中提到的二维结构，是一个横纵结合的二维表。在关系模型中，现实世界的实体以及实体间的各种联系均用关系来表示。

❏关系是一种对象。

❏关系的另外一个常用词是表，在本书中，关系和表混用，因为它们基本表达同一含义，只是关系更偏向于理论，表更偏向于实际数据库中可进行增、删、改、查等操作的表对象。

❏关系的元数据，即表的结构，通常称为列或属性。数据库实现中，有的用field表示，有的用Item表示。

❏关系的数据，即表的行数据，通常称为元组（tuple），也称为记录（record）。一个表可有多行元组。

❏对关系进行的操作就是关系运算。关系运算是将一定的运算符作用于一定的关系对象上，得到预期的运算结果（预期就是用户语义，用户语义通过运算符表达基本语义，通过对不同对象上的各种运算进行组合表达其对关系操作的真实语义）。运算对象、运算符、运算结果是运算的三大要素，所以关系运算就是关系运算符作用在关系上、得到的结果形式也是关系形式的操作。

关系代数的运算符包括以下4类：

❏传统集合运算符。并（UNION）、交（INTERSECTION）、差（DIFFERENCE）、积（EXTENDED CARTESIAN PRODUCT）。

❏专门的关系运算符。选择（SELECT）、投影（PROJECT）、连接（JOIN）、除（DIVIDE）。

❏辅助运算符。用来辅助专门的关系运算符进行操作的，包括算术比较符和逻辑运算符。

❏Codd定义了8个基本关系运算符后，许多人提出了新的代数操作符——关系扩展运算符，如半连接（SEMIJOIN）、半差（SEMIDIFFERENCE）、扩展（EXTEND）、合计（COMPOSITION）、传递闭包（TCLOSE）等，这些操作符增强了关系代数的表达能力，但不常用。

关系代数基本关系运算如表2-1所示，各种连接运算的语义如表2-2所示。

表2-1 基本关系运算与对应的SQL表

表2-2 各种连接运算的语义表

2.1.2 关系代数等价变换规则对优化的指导意义

关系代数表达式的等价：也就是说用相同的关系代替两个表达式中相应的关系，所得到的结果是相同的。两个关系表达式El和E2是等价的，记为E1≡E2。

查询语句可以表示为一棵二叉树，其中：

❏叶子是关系。

❏内部结点是运算符（或称算子、操作符，如LEFT OUT JOIN），表示左右子树的运算方式。

❏子树是子表达式或SQL片段。

❏根结点是最后运算的操作符。

❏根结点运算之后，得到的是SQL查询优化后的结果。

❏这样一棵树就是一个查询的路径。

❏多个关系连接，连接顺序不同，可以得出多个类似的二叉树。

❏查询优化就是找出代价最小的二叉树，即最优的查询路径。每条路径的生成，包括了单表扫描、两表连接、多表连接顺序、多表连接搜索空间等技术。

❏基于代价估算的查询优化就是通过计算和比较，找出花费最少的最优二叉树。

上述的最后两项，主要依据本章查询重写规则和第3章物理查询优化中涉及的技术，对查询优化引擎做关系代数和启发式规则的逻辑查询优化、基于代价估算模型择优的物理查询优化，从而帮助数据库查询优化器实现查询优化。

1.从运算符的角度考虑优化

不同运算符根据其特点，可以对查询语句做不同的优化，优化可以减少中间生成物的大小和数量，节约IO、内存等，从而提高了执行速度。但优化的前提是：优化前和优化后的语义必须等价。不同运算符的优化规则和可优化的原因如表2-3所示。

表2-3 运算符主导的优化

表2-4 选择下推到集合的运算

表2-5 投影下推到集合的运算

对于表2-4和表2-5，我们以“σA(R×S)”为例，表明它们可做优化的共同意义。

初始式是σA(R×S)，条件A可分解为“B∧C∧D”，条件B只与关系R有关，条件C只与关系S有关，则初始式可以变形为：σB∧C∧D(R×S)，表示为查询树的结构如图2-1所示。

图2-2所示为第一层做完选择后，每个叶子结点对应的元组数“可能”比图2-1中的R和S少，如果B条件和C条件至少有一个能够大量减少R或S的元组，则中间结果大量减少，优化的效果会更好（B条件和C条件对元组过滤程度依赖于“选择率”）。如果R和S上有B条件、C条件可以使用的索引，则利用索引可加快元组的获取，优化的效果会更好。

如果索引是唯一索引或主键（主键不允许重复，不允许为NULL值，多数数据库为主键实现了一个唯一索引）之类，条件表达式是等值表达式（=运算非范围运算），定位元组的速度更快（可直接利用索引而不用扫描数据）、满足条件的元组更少，所以优化的效果会更佳。

图2-1中在连接后进行选择操作，一是中间结果的元组数量大，二是需要对中间结果的每条元组都进行B、C、D3个条件的判断，增加了条件判断的成本，效率很低。

经过等价变换优化带来的好处，再加上避免了原始方式引入的坏处，使得查询效率明显获得提升。

2.从运算规则的角度考虑优化

前面我们从运算符的角度出发考虑了优化。因为运算符中考虑的子类型（见表2-3中的“子类型”列）实则是部分考虑了运算符间的关系、运算符和操作数间的关系，其本质是运算规则在起作用。所以前节考虑过关系代数运算规则对优化的作用，但不完整，这里补充余下的对优化有作用的主要关系代数运算规则。下面的运算规则是查询重写技术作等价转换的基础，如表2-6所示。

表2-6 运算规则主导的优化

2.2 查询重写规则

传统的联机事务处理（On-line Transaction Processing，OLTP）使用基于选择（SELECT）、投影（PROJECT）、连接（JOIN）3种基本操作相结合的查询，这种查询称为SPJ查询。

数据库在查询优化的过程中，会对这3种基本操作进行优化。优化的方式如下：

❏选择操作。对应的是限制条件（格式类似field＜op＞consant，field表示列对象，op是操作符，如=、＞等），优化方式是选择操作下推，目的是尽量减少连接操作前的元组数，使得中间临时关系尽量少（元组数少，连接得到的元组数就少），这样可减少IO和CPU的消耗，节约内存空间。

❏投影操作。对应的SELECT查询的目的列对象，优化方式是投影操作下推，目的是尽量减少连接操作前的列数，使得中间临时关系尽量小（特别注意差别：选择操作是使元组的个数“尽量少”，投影操作是使一条元组“尽量小”），这样虽然不能减少IO（多数数据库存储方式是行存储，元组是读取的最基本单位，所以要想操作列则必须读取一行数据），但可以各减少连接后的中间关系的元组大小，节约内存空间。

❏连接操作。对应的是连接条件（格式类似field_1＜op＞field_2，field_1和field_2表示不同表上的列对象，op是操作符，如=、＞等），表示两个表连接的条件。这里涉及以下两个子问题。

○多表连接中每个表被连接的顺序决定着效率。如果一个查询语句只有一个表，则这样的语句很简单；但如果有多个表，则会涉及表之间以什么样的顺序连接效率最高效（如A、B、C三表连接，如果ABC、ACB、BCA等连接后的结果集一样，则计算哪种连接次序的效率最高，是需要考虑的问题）。

○多表连接每个表被连接的顺序由用户语义决定。查询语句多表连接有着不同的语义（如是笛卡儿集、内连接，还是外连接中的左外连接等），这决定着表之间的前后连接次序是不能随意更换的，否则，结果集中数据是不同的。因此，表的前后连接次序是不能随意交换的。

另外，根据SQL语句的形式特点，还可以做如下区分：

❏针对SPJ的查询优化。基于选择、投影、连接3种基本操作相结合的查询。

❏针对非SPJ的查询优化。在SPJ的基础上存在GROUPBY操作的查询，这是一种较为复杂的查询。

所以，针对SPJ和非SPJ的查询优化，其实是对以上多种操作的优化。“选择”和“投影”操作，可以在关系代数规则的指导下进行优化。表连接，需要多表连接的相关算法完成优化。其他操作的优化多是基于索引和代价估算完成的。

2.2.1 子查询的优化

子查询是查询语句中经常出现的一种类型，是比较耗时的操作。优化子查询对查询效率的提升有着直接的影响，所以子查询优化技术，是数据库查询优化引擎的重要研究内容。

从子查询出现在SQL语句的位置看，它可以出现在目标列、FROM子句、WHERE子句、JOIN/ON子句、GROUPBY子句、HAVING子句、ORDERBY子句等位置。子查询出现在不同位置对优化的影响如下：

❏目标列位置。子查询如果位于目标列，则只能是标量子查询，否则数据库可能返回类似“错误：子查询必须只能返回一个字段”的提示。

❏FROM子句位置。相关子查询出现在FROM子句中，数据库可能返回类似“在FROM子句中的子查询无法参考相同查询级别中的关系”的提示，所以相关子查询不能出现在FROM子句中；非相关子查询出现在FROM子句中，可上拉子查询到父层，在多表连接时统一考虑连接代价后择优。

❏WHERE子句位置。出现在WHERE子句中的子查询是一个条件表达式的一部分，而表达式可以分解为操作符和操作数；根据参与运算的数据类型的不同，操作符也不尽相同，如INT型有＞、＜、=、＜＞等操作，这对子查询均有一定的要求（如INT型的等值操作，要求子查询必须是标量子查询）。另外，子查询出现在WHERE子句中的格式也有用谓词指定的一些操作，如IN、BETWEEN、EXISTS等。

❏JOIN/ON子句位置。JOIN/ON子句可以拆分为两部分，一是JOIN块类似于FROM子句，二是ON子句块类似于WHERE子句，这两部分都可以出现子查询。子查询的处理方式同FROM子句和WHERE子句。2010-10-12

❏GROUPBY子句位置。目标列必须和GROUPBY关联。可将子查询写在GROUPBY位置处，但子查询用在GROUPBY处没有实用意义。

❏ORDERBY子句位置。可将子查询写在ORDERBY位置处。但ORDERBY操作是作用在整条SQL语句上的，子查询用在ORDERBY处没有实用意义。

1.子查询的分类

根据子查询中涉及的关系对象与外层关系对象间的关系，子查询可以分为以下两类：

❏相关子查询。子查询的执行依赖于外层父查询的一些属性值。子查询因依赖于父查询的参数，当父查询的参数改变时，子查询需要根据新参数值重新执行（查询优化器对相关子查询进行优化有一定意义），如：

SELECT * FROM t1 WHERE col_1 = ANY
   (SELECT col_1 FROM t2 WHERE t2.col_2 = t1.col_2);/* 子查询语句中存在父查询的t1表的col_2列 */

❏非相关子查询。子查询的执行不依赖于外层父查询的任何属性值，这样的子查询具有独立性，可独自求解，形成一个子查询计划先于外层的查询求解，如：

SELECT * FROM t1 WHERE col_1 = ANY
   (SELECT col_1 FROM t2 WHERE t2.col_2 = 10);//子查询语句中(t2)不存在父查询(t1)的属性

从特定谓词看，子查询可分为以下3类：

❏[NOT]IN/ALL/ANY/SOME子查询。语义相近，表示“[取反]存在/所有/任何/任何”，左面是操作数，右面是子查询，是最常见的子查询类型之一。

❏[NOT]EXISTS子查询。半连接语义，表示“[取反]存在”，没有左操作数，右面是子查询，也是最常见的子查询类型之一。

❏其他子查询。除了上述两种外的所有子查询。

从语句的构成复杂程度看，子查询可分为以下3类：

❏SPJ子查询。由选择、连接、投影操作组成的查询。

❏GROUPBY子查询。SPJ子查询加上分组、聚集操作组成的查询。

❏其他子查询。GROUPBY子查询中加上其他子句如Top-N、LIMIT/OFFSET、集合、排序等操作。后两种子查询有时合称非SPJ子查询。

从结果集的角度看，子查询分为以下4类：

❏标量子查询。子查询返回的结果集类型是一个单一值（return a scalar，a single value）。

❏列子查询。子查询返回的结果集类型是一条单一元组（return a single row）。

❏行子查询。子查询返回的结果集类型是一个单一列（return a single column）。

❏表子查询。子查询返回的结果集类型是一个表（多行多列）（return a table，one or more rows of one or more columns）。

2.子查询的优化思路

通过上面的介绍，我们知道了都有哪些类型的子查询及每类子查询的特点，下面就讲一下子查询的优化思路。要明白子查询是如何优化的，就要先明白为什么要做子查询优化。

（1）做子查询优化的原因

为什么要做子查询优化呢？

在数据库实现早期，查询优化器对子查询一般采用嵌套执行的方式，即对父查询中的每一行，都执行一次子查询，这样子查询会执行很多次。这种执行方式效率很低。

而对子查询进行优化，可能带来几个数量级的查询效率的提高。子查询转变成为连接操作之后，会得到如下好处：

❏子查询不用执行很多次。

❏优化器可以根据统计信息来选择不同的连接方法和不同的连接顺序。

❏子查询中的连接条件、过滤条件分别变成了父查询的连接条件、过滤条件，优化器可以对这些条件进行下推，以提高执行效率。

（2）子查询优化技术

子查询优化技术的思路如下：

❏子查询合并（Subquery Coalescing）。在某些条件下（语义等价：两个查询块产生同样的结果集），多个子查询能够合并成一个子查询（合并后还是子查询，以后可以通过其他技术消除子查询）。这样可以把多次表扫描、多次连接减少为单次表扫描和单次连接，如：

SELECT * FROM t1 WHERE a1＜10 AND (
    EXISTS (SELECT a2 FROM t2 WHERE t2.a2＜5 AND t2.b2=1) OR
    EXISTS (SELECT a2 FROM t2 WHERE t2.a2＜5 AND t2.b2=2)
);

可优化为：

SELECT * FROM t1 WHERE a1＜10 AND (
     EXISTS (SELECT a2 FROM t2 WHERE t2.a2＜5 AND (t2.b2=1 OR t2.b2=2) /*两个EXISTS子句合并为一个,条件也进行了合并 */
);

❏子查询展开（Subquery Unnesting）。又称子查询反嵌套，又称为子查询上拉。把一些子查询置于外层的父查询中，作为连接关系与外层父查询并列，其实质是把某些子查询重写为等价的多表连接操作（展开后，子查询不存在了，外层查询变成了多表连接）。带来的好处是，有关的访问路径、连接方法和连接顺序可能被有效使用，使得查询语句的层次尽可能地减少。常见的IN/ANY/SOME/ALL/EXISTS依据情况转换为半连接（SEMI JOIN）、普通类型的子查询消除等情况属于此类，如：

SELECT * FROM t1, (SELECT * FROM t2 WHERE t2.a2 ＞10) v_t2
WHERE t1.a1＜10 AND v_t2.a2＜20;

可优化为：

SELECT * FROM t1, t2 WHERE t1.a1＜10 AND t2.a2＜20 AND t2.a2 ＞10; /* 子查询变为了t1、t2表的连接操作,相当于把t2表从子查询中上拉了一层 */

❏聚集子查询消除（Aggregate Subquery Elimination）。聚集函数上推，将子查询转变为一个新的不包含聚集函数的子查询，并与父查询的部分或者全部表做左外连接。通常，一些系统支持的是标量聚集子查询消除，如：

SELECT * FROM t1 WHERE t1.a1＞(SELECT avg(t2.a2) FROM t2);

❏其他。利用窗口函数消除子查询的技术（Remove Subquery using Window functions，RSW）、子查询推进（Push Subquery）等技术可用于子查询的优化，这里不展开讨论。

（3）子查询展开

子查询展开是一种最为常用的子查询优化技术，子查询展开有以下两种形式：

❏如果子查询中出现了聚集、GROUPBY、DISTINCT子句，则子查询只能单独求解，不可以上拉到上层。

❏如果子查询只是一个简单格式（SPJ格式）的查询语句，则可以上拉到上层，这样往往能提高查询效率。子查询上拉讨论的就是这种格式，这也是子查询展开技术处理的范围。

把子查询上拉到上层查询，前提是上拉（展开）后的结果不能带来多余的元组，所以子查询展开需要遵循如下规则：

❏如果上层查询的结果没有重复（即SELECT子句中包含主码），则可以展开其子查询，并且展开后的查询的SELECT子句前应加上DISTINCT标志。

❏如果上层查询的SELECT语句中有DISTINCT标志，则可以直接进行子查询展开。

❏如果内层查询结果没有重复元组，则可以展开。

子查询展开的具体步骤如下：

1）将子查询和上层查询的FROM子句连接为同一个FROM子句，并且修改相应的运行参数。

2）将子查询的谓词符号进行相应修改（如：IN修改为=ANY）。

3）将子查询的WHERE条件作为一个整体与上层查询的WHERE条件合并，并用AND条件连接词连接，从而保证新生成的谓词与原谓词的上下文意思相同，且成为一个整体。

3.最常见的子查询类型的优化

子查询的格式有多种，常见的子查询格式有IN类型、ALL/ANY/SOME类型、EXISTS类型。下面我们就基于这3种常见类型对子查询类型的优化进行介绍。

（1）IN类型

IN类型有3种不同的格式，具体如下。

格式一：

outer_expr [NOT] IN (SELECT inner_expr FROM ... WHERE subquery_where)

格式二：

outer_expr =ANY (SELECT inner_expr FROM ... WHERE subquery_where)

格式三：

(oe_1, ..., oe_N) [NOT] IN (SELECT ie_1, ..., ie_N FROM ... WHERE subquery_where)

对于IN类型子查询的优化（可以转换的形式和转换需要的必备条件分为几种情况），如表2-7所示。

表2-7 IN类型子查询优化的情况表

情况一：outer_expr和inner_expr均为非NULL值。

优化后的表达式（外部条件outer_expr下推到子查询中）如下：

EXISTS (SELECT 1 FROM ... WHERE subquery_where AND outer_expr=inner_expr)

即：

EXISTS (SELECT 1 FROM ... WHERE subquery_where
                          AND oe_1 = ie_1
                          AND ...
                          AND oe_N = ie_N)

子查询优化需要满足的以下两个条件（全部满足）：

❏outer_expr和inner_expr不能为NULL。

❏不需要从结果为FALSE的子查询中区分NULL。

情况二：outer_expr是非NULL值（情况一的两个转换条件中至少有一个不满足时）。

优化后的表达式（外部条件outer_expr下推到子查询中，另外内部条件inner_expr为NULL）如下：

EXISTS (SELECT 1 FROM ... WHERE subquery_where AND
        (outer_expr=inner_expr OR inner_expr IS NULL))

假设outer_expr是非NULL值，但是如果outer_expr=inner_expr表达式不产生数据，则outer_expr IN(SELECT...)的计算结果如果是NULL值或FALSE值时，转换条件如下：

❏为NULL值。SELECT语句查询得到任意的行数据，inner_expr是NULL（outer_expr IN(SELECT...)==NULL）。

❏为FALSE值。SELECT语句产生非NULL值或不产生数据（outer_expr IN(SELECT...)==FALSE）。

情况三：outer_expr为NULL值。

原先的表达式等价于如下形式：

NULL IN (SELECT inner_expr FROM ... WHERE subquery_where)

假设outer_expr是NULL值，NULL IN(SELECT inner_expr...)的计算结果如果是NULL值或FALSE值时，转换条件如下：

❏为NULL值。SELECT语句产生任意行数据。

❏为FALSE值。SELECT语句不产生数据。

对于上面的等价形式，还有两点需要说明：

❏谓词IN等价于=ANY，例如下面的两条SQL语句是等价的：

SELECT col_1 FROM t1 WHERE col_1 = ANY (SELECT col_1 FROM t2);
SELECT col_1 FROM t1 WHERE col_1 IN(SELECT col_1 FROM t2);

❏带有谓词IN的子查询，如果满足上述3种情况，可以做等价变换，把外层的条件下推到子查询中，变形为一个EXISTS类型的逻辑表达式判断；而子查询为EXISTS类型则可以被半连接算法实现优化。

下面我们看几个具体的示例（以PostgreSQL为例说明子查询优化的情况）。

示例1 初始数据如下所示：

test=# SELECT * FROM x;
x_num | x_name
------+-----------
    1 | X_1
    2 | X_2
     | X_3
(3 rows)
test=# SELECT * FROM y;
y_num | y_name
----------+-----------
    1 | Y_1
      | Y_2
    3 | Y_3
(3 rows)

执行如下子查询命令：

test=# SELECT * FROM x WHERE x_num IN(SELECT y_num FROM y); //IN子查询
 x_num | x_name
----------+-----------
     1 | X_1
(1 row)

执行计划具体如下：

test=# EXPLAIN SELECT * FROM xWHERE x_num IN(SELECT y_num FROM y);
                         QUERY PLAN
-------------------------------------------------------------
Hash IN Join(cost=1.07..2.14 rows=3 width=18)
  Hash Cond: (x.x_num = y.y_num)
  -＞Seq Scan on x(cost=0.00..1.03 rows=3 width=18)
  -＞Hash(cost=1.03..1.03 rows=3 width=4)
      -＞Seq Scan on y(cost=0.00..1.03 rows=3 width=4)
(5 rows)

示例说明：

❏Hash IN Join表示执行的是两表Hash连接（已经使用两表连接替代了子查询），IN表示原子查询是“IN子查询”。

❏原始查询SQL中没有(x.x_num=y.y_num)，只是一个IN子查询，而查询计划中出现(x.x_num=y.y_num)，表明此IN子查询被优化，优化后执行的是符合连接条件(x.x_num=y.y_num)的一个两表连接的查询。

示例2 表t_1、表t_2定义和数据如下所示：

CREATE TABLE t_1 (t_1_id INT UNIQUE, t_1_col_1 INT, t_1_col_2 VARCHAR(10));
CREATE TABLE t_2 (t_2_id INT UNIQUE, t_2_col_1 INT, t_2_col_2 VARCHAR(10));
INSERT INTO t_1 VALUES (1, 11, 't_1_1');
INSERT INTO t_1 VALUES (2, 12, NULL);
INSERT INTO t_1 VALUES (3, NULL, 't_1_3');
INSERT INTO t_1 VALUES (4, 14, 't_1_4');
INSERT INTO t_1 VALUES (5, 15, NULL);
INSERT INTO t_1 VALUES (7, NULL, NULL);
INSERT INTO t_2 VALUES (1, 11, 't_2_1');
INSERT INTO t_2 VALUES (2, NULL, 't_2_2');
INSERT INTO t_2 VALUES (3, 13, NULL);
INSERT INTO t_2 VALUES (4, 14, 't_2_4');
INSERT INTO t_2 VALUES (6, 16, 't_2_6');
INSERT INTO t_2 VALUES (7, NULL, NULL);

语句一 简单的IN子查询如下：

SELECT t_1.* FROM t_1 WHERE t_1_id IN (SELECT t_2_id FROM t_2);

语句二 简单IN子查询但子查询结果不影响父查询，如下所示：

SELECT t_1.* FROM t_1 WHERE 10 IN (SELECT t_2_id FROM t_2);

语句三 父查询中的易失函数影响子查询的优化，如下所示：

SELECT t_1.* FROM t_1 WHERE t_1_id + div((random()*10)::numeric,2) IN (SELECT t_2_idFROM t_2);

对于语句一，简单的IN子查询的查询执行计划如下：

test=# EXPLAIN SELECT t_1.* FROM t_1 WHERE t_1_id IN (SELECT t_2_id FROM t_2);
                            QUERY PLAN
-----------------------------------------------------------
Hash Semi Join(cost=45.33..94.58 rows=1570 width=22)
  Hash Cond: (t_1.t_1_id = t_2.t_2_id)
  -＞Seq Scan on t_1(cost=0.00..25.70 rows=1570 width=22)
  -＞Hash(cost=25.70..25.70 rows=1570 width=4)
      -＞Seq Scan on t_2(cost=0.00..25.70 rows=1570 width=4)
(5 rows)

查询优化器对查询做了优化，把子查询转换使用t_1.t_1_id=t_2.t_2_id作为连接条件的为Hash半连接（Hash Semi Join）。如果不做优化，则t_1表有多少条记录，就需要扫描t_2表多少次，而且每次都得对t_2表做全表顺序扫描，这样会花费较多时间；而优化后，对t_2表只做了一次全表顺序扫描，然后采用Hash Semi Join算法，对t_1和t_2做连接操作即可，节约了很多次对t_2表的全表扫描，达到了优化的目的。

对于语句二，简单却不影响父查询的IN子查询的查询执行计划如下：

test=# EXPLAIN SELECT t_1.* FROM t_1 WHERE 10 IN (SELECT t_2_id FROM t_2);
                            QUERY PLAN
---------------------------------------------------------------------------------
 Result(cost=29.63..55.33 rows=1570 width=22)
   One-Time Filter: (hashed SubPlan 1)
   -＞Seq Scan on t_1(cost=29.63..55.33 rows=1570 width=22)
 SubPlan 1
    -＞Seq Scan on t_2(cost=0.00..25.70 rows=1570 width=4)
(5 rows)

查询优化器不能对查询做优化。查询计划是对t_2做一个顺序扫描，结果作为过滤器为t_1扫描服务。子查询与上层查询（t_1表所在的查询）没有关系，而IN子查询的左操作符是常量，所以对子查询直接求值，没有办法做上拉优化。

对于语句三，带有易失函数random()的IN子查询的查询执行计划如下：

test=# EXPLAIN SELECT t_1.* FROM t_1 WHERE t_1_id + div((random()*10)::numeric,2) IN (SELECT t_2_idFROM t_2);
                           QUERY PLAN
----------------------------------------------------------------------------------
 Seq Scan on t_1(cost=29.63..86.73 rows=785 width=22)
   Filter: (hashed SubPlan 1)
 SubPlan 1
    -＞Seq Scan on t_2(cost=0.00..25.70 rows=1570 width=4)
(4 rows)

查询中出现了易失函数random()，子查询结果不确定，查询优化器就不能对子查询做优化。

（2）ALL/ANY/SOME类型

ALL/ANY/SOME类型的子查询格式，具体如下：

outer_expr operator ANY (subquery)
outer_expr operator SOME (subquery)
outer_expr operator ALL (subquery)

ALL表示对于子查询的全部元组进行operator指定的操作；ANY表示对于子查询的任何元组进行operator指定的操作；SOME表示对于子查询的某些元组进行operator指定的操作。另外，使用ALL/ANY/SOME类型的子查询，还需要注意：

❏operator为操作符，通常可以是＜、=＜、＞、＞=中的任何一个。具体是否支持某个操作符，取决于表达式值的类型。

❏=ANY与IN含义相同，可以采用IN子查询优化方法。

❏SOME与ANY含义相同。

❏NOT IN与＜＞ALL含义相同。

❏NOT IN与＜＞ANY含义不相同。

❏＜＞ANY表示不等于任何值。

对于ALL/ANY/SOME类子查询的优化，如果子查询中没有GROUPBY子句，也没有聚集函数，则下面的表达式还可以使用聚集函数MAX/MIN做类似下面的等价转换：

❏val＞ALL(SELECT...)等价变化为val＞MAX(SELECT...)

❏val＜ALL(SELECT...)等价变化为val＜MIN(SELECT...)

❏val＞ANY(SELECT...)等价变化为val＞MIN(SELECT...)

❏val＜ANY(SELECT...)等价变化为val＜MAX(SELECT...)

❏val＞=ALL(SELECT...)等价变化为val＞=MAX(SELECT...)

❏val＜=ALL(SELECT...)等价变化为val＜=MIN(SELECT...)

❏val＞=ANY(SELECT...)等价变化为val＞=MIN(SELECT...)

❏val＜=ANY(SELECT...)等价变化为val＜=MAX(SELECT...)

具体变换的形式如下：

val＞ANY (SELECT item ...)等价变化为val＞SELECT MIN(item)...

（3）EXISTS类型

EXISTS类型的子查询格式如下：

[NOT] EXISTS (subquery)

这里有以下几点需要注意：

❏EXISTS对于子查询而言，其结果值是布尔值；如果subquery有返回值，则整个EXISTS(subquery)的值为TRUE，否则为FALSE。

❏EXISTS(subquery)不关心subquery返回的内容，这使得带有EXISTS(subquery)的子查询存在优化的可能。

❏EXISTS(subquery)自身有着“半连接”的语义，所以，一些数据库实现代码中（如PostgreSQL），用半连接完成EXISTS(subquery)求值。

❏NOT EXISTS(subquery)通常会被标识为“反半连接”处理。

❏一些诸如IN(subquery)的子查询可以等价转换为EXISTS(subquery)格式，所以可以看到IN(subquery)的子查询可被优化为半连接实现的表连接。

下面通过一个示例来进行说明。

示例3 沿用示例2的表和数据。

语句四 EXISTS类型的普通相关子查询，子查询条件和父查询有关联：

SELECT t_1.* FROM t_1 WHERE EXISTS (SELECT t_2_id FROM t_2 WHERE t_1_id=t_2_id);

语句五 EXISTS类型的普通相关子查询，子查询条件和子查询没有关系：

SELECT t_1.* FROM t_1 WHERE EXISTS (SELECT t_2_id FROM t_2 WHERE t_1_id=10);

语句六 EXISTS类型的普通非相关子查询：

SELECT t_1.* FROM t_1 WHERE EXISTS (SELECT t_2_id FROM t_2 WHERE t_2_id=10);

语句七 EXISTS类型的普通非相关子查询，子查询简单没有表存在：

SELECT t_1.* FROM t_1 WHERE EXISTS (SELECT 10);

对于语句四，EXISTS类型的普通相关子查询的查询执行计划如下：

test=# EXPLAIN SELECT t_1.* FROM t_1 WHERE EXISTS (SELECT t_2_id FROM t_2 WHERE t_1_id=t_2_id);
                            QUERY PLAN
---------------------------------------------------------------------------------
Hash Semi Join(cost=45.33..94.58 rows=1570 width=22)
   Hash Cond: (t_1.t_1_id = t_2.t_2_id)
   -＞Seq Scan on t_1(cost=0.00..25.70 rows=1570 width=22)
   -＞Hash(cost=25.70..25.70 rows=1570 width=4)
      -＞Seq Scan on t_2(cost=0.00..25.70 rows=1570 width=4)
(5 rows))

查询优化器对查询做了优化，通过子查询上拉技术，把子查询转换为使用t_1.t_1_id=t_2.t_2_id作为连接条件实现Hash半连接（Hash Semi Join）操作。如果不做优化，则t_1表有多少条记录，都需要扫描t_2表多少次，每次都得对t_2表做全表顺序扫描，这样会花费较多时间；而优化后，对t_2表只做了一次全表顺序扫描，然后采用Hash Semi Join算法，对t_1和t_2做连接操作即可，节约了很多次对t_2表的全表扫描，达到了优化的目的。

对于语句五，EXISTS类型的普通相关子查询的查询执行计划如下：

test=# EXPLAIN SELECT t_1.* FROM t_1 WHERE EXISTS (SELECT t_2_id FROM t_2 WHERE t_1_id=10);
                        QUERY PLAN
-----------------------------------------------------------------------------------------------------------
Nested Loop Semi Join(cost=0.00..33.99 rows=1 width=22)
 -＞Index Scan using t_1_t_1_id_key on t_1(cost=0.00..8.27 rows=1 width=22)
     Index Cond: (t_1_id = 10)
 -＞Seq Scan on t_2(cost=0.00..25.70 rows=1570 width=0)
(4 rows)

查询优化器能对查询做优化。通过子查询上拉技术，查询执行计划对子查询t_2做一个顺序扫描，然后与做顺序扫描的t_1表扫描的结果进行嵌套循环半连接（Nested Loop Semi Join）。

对于语句六，EXISTS类型的普通非相关子查询的查询执行计划如下：

test=# EXPLAIN SELECT t_1.* FROM t_1 WHERE EXISTS (SELECT t_2_id FROM t_2 WHERE t_2_id=10);
                                     QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------
 Result(cost=8.27..33.97 rows=1570 width=22)
 One-Time Filter: $0
 InitPlan 1 (returns $0)
    -＞Index Scan using t_2_t_2_id_key on t_2(cost=0.00..8.27 rows=1 width=0)
          Index Cond: (t_2_id = 10)
 -＞Seq Scan on t_1(cost=0.00..25.70 rows=1570 width=22)
(6 rows)

子查询是非相关子查询，子查询只要执行一次即可推知EXISTS的结果是TRUE或FALSE，所以不会执行多次，也没有必要进行优化，所以查询执行计划中存在One-Time，表示只执行一次。

对于语句七，EXISTS类型的非相关子查询的查询执行计划如下：

test=# EXPLAIN SELECT t_1.* FROM t_1 WHERE EXISTS (SELECT 10);
                           QUERY PLAN
------------------------------------------------------------------------------------------
 Result(cost=0.01..25.71 rows=1570 width=22)
   One-Time Filter: $0
   InitPlan 1 (returns $0)
      -＞Result(cost=0.00..0.01 rows=1 width=0)
     -＞Seq Scan on t_1(cost=0.00..25.70 rows=1570 width=22)
(5 rows)

子查询比语句三更为简单，道理同对语句六的分析。查询执行计划中存在One-Time，表示只执行一次。

2.2.2 视图重写

视图是数据库中基于表的一种对象，视图重写就是将对视图的引用重写为对基本表的引用。视图重写后的SQL多被作为子查询进行进一步优化。所有的视图都可以被子查询替换，但不是所有的子查询都可以用视图替换。这是因为，子查询的结果作为一个结果集，如果是单行单列（标量），则可以出现在查询语句的目标列；如果是多行多列，可以出现在FROM、WHERE等子句中。但即使是标量视图（视图等同于表对象），也不可以作为目标列单独出现在查询语句中。

从视图的构成形式看，类似于查询的SPJ与非SPJ，视图可以分为简单视图和复杂视图。

❏用SPJ格式构造的视图，称为简单视图。

❏用非SPJ格式构造（带有GROUPBY等操作）的视图，称为复杂视图。

下面通过一个例子来具体看一下视图重写。SQL语句如下：

CREATE TABLE t_a(a INT, b INT);
CREATE VIEW v_a AS SELECT * FROM t_a;

基于视图的查询命令如下：

SELECT col_a FROM v_a WHERE col_b＞100;

经过视图重写后可变换为如下形式：

SELECT col_a FROM
(
    SELECT col_a, col_b FROM t_a
)
WHERE col_b＞100;

未来经过优化，可以变换为如下等价形式：

SELECT col_a FROM t_a WHERE col_b＞100;

简单视图能够被查询优化器较好地处理；但是复杂视图则不能被查询优化器很好地处理。一些商业数据库，如Oracle，提供了一些视图的优化技术，如“复杂视图合并”、“物化视图查询重写”等。但从整体上看，复杂视图优化技术还有待继续提高。

2.2.3 等价谓词重写

数据库执行引擎对一些谓词处理的效率要高于其他谓词，基于这点，把逻辑表达式重写成等价的且效率更高的形式，能有效提高查询执行效率。这就是等价谓词重写。

常见的等价谓词重写规则如下。

1.LIKE规则

LIKE谓词是SQL标准支持的一种模式匹配比较操作，LIKE规则是对LIKE谓词的等价重写，即改写LIKE谓词为其他等价的谓词，以更好地利用索引进行优化。如列名为name的LIKE操作示例如下：

name LIKE 'Abc%'

重写为：

name＞='Abc' AND name ＜'Abd'

应用LIKE规则的好处是：转换前针对LIKE谓词只能进行全表扫描，如果name列上存在索引，则转换后可以进行索引范围扫描。

LIKE其他形式还可以转换：LIKE匹配的表达式中，若没有通配符（%或_），则与=等价。如：

name LIKE 'Abc'

重写为：

name='Abc'

2.BETWEEN-AND规则

BETWEEN-AND谓词是SQL标准支持的一种范围比较操作，BETWEEN-AND规则是指BETWEEN-AND谓词的等价重写，即改写BETWEEN-AND谓词为其他等价的谓词，以更好地利用索引进行优化。BETWEEN-AND谓词的等价重写类似于LIKE谓词的等价重写，如：

sno BETWEEN 10 AND 20

重写为：

sno＞=10 AND sno ＜=20

应用BETWEEN-AND规则的好处是：如果sno上建立了索引，则可以用索引扫描代替原来BETWEEN-AND谓词限定的全表扫描，从而提高了查询的效率。

3.IN转换OR规则

IN是只IN操作符操作，不是IN子查询。IN转换OR规则就是IN谓词的OR等价重写，即改写IN谓词为等价的OR谓词，以更好地利用索引进行优化。将IN谓词等价重写为若干个OR谓词，可能会提高执行效率。如：

age IN (8,12,21)

重写为：

age=8 OR age=12 OR age=21

应用IN转换OR规则后效率是否能够提高，需要看数据库对IN谓词是否只支持全表扫描。如果数据库对IN谓词只支持全表扫描且OR谓词中表的age列上存在索引，则转换后查询效率会提高。

4.IN转换ANY规则

IN转换ANY规则就是IN谓词的ANY等价重写，即改写IN谓词为等价的ANY谓词。因为IN可以转换为OR，OR可以转为ANY，所以可以直接把IN转换为ANY。将IN谓词等价重写为ANY谓词，可能会提高执行效率。如：

age IN (8,12,21)

重写为：

age ANY(8,12,21)

应用IN转换ANY规则后效率是否能够提高，依赖于数据库对于ANY操作的支持情况。如，PostgreSQL没有显式支持ANY操作，但是在内部实现时把IN操作转换为了ANY操作，如下所示：

test=# \d t1;
  资料表 "public.t1"
 栏位 |型别 | 修饰词
--------+----------+----------
 id1| integer | 非空
 a1 | integer |
 b1 | integer |
索引：
   "t1_pkey" PRIMARY KEY, btree (id1)
test=# EXPLAIN SELECT * FROM t1 WHERE a1 IN (1,3,5);
                       QUERY PLAN
---------------------------------------------------------------------------
Seq Scan on t1(cost=0.00..192.50 rows=3 width=12)
  Filter: (a1 = ANY ('{1,3,5}'::integer[]))
(2 行记录)

5.OR转换ANY规则

OR转换ANY规则就是OR谓词的ANY等价重写，即改写OR谓词为等价的ANY谓词，以更好地利用MIN/MAX操作进行优化。如：

sal＞1000 OR dno=3 AND (sal＞1100 OR sal＞base_sal+100) OR sal＞base_sal+200 OR sal＞base_sal*2

重写为：

dno=3 AND (sal＞1100 OR sal＞base_sal+100) OR sal＞ANY (1000, base_sal+200, base_sal*2)

OR转换ANY规则依赖于数据库对于ANY操作的支持情况。PostgreSQL V9.2.3和MySQLV5.6.10目前都不支持本条规则。

6.ALL/ANY转换集函数规则

ALL/ANY转换集函数规则就是将ALL/ANY谓词改写为等价的聚集函数MIN/MAX谓词操作，以更好地利用MIN/MAX操作进行优化。如：

sno＞ANY(10, 2*5+3, sqrt(9))

重写为：

sno＞sqrt(9)

上面这个ALL/ANY转换集函数规则的示例，有以下两点需要注意：

❏本示例中存在＞和ANY，其意是在找出(10，2*5+3，sqrt(9))中的最小值，所以可以重写为sno＞sqrt(9)。

❏通常，聚集函数MAX()、MIN()等的执行效率比ANY、ALL谓词的执行效率高，因此在这种情况下对其进行重写可以起到比较好的效果。如果有索引存在，求解MAX/MIN的效率更高。

7.NOT规则

NOT谓词的等价重写。如下：

NOT (col_1 !=2)重写为col_1=2
NOT (col_1 !=col_2)重写为col_1=col_2
NOT (col_1 =col_2)重写为col_1!=col_2
NOT (col_1 ＜col_2)重写为col_1＞=col_2
NOT (col_1 ＞col_2)重写为col_1＜=col_2

NOT规则重写的好处是：如果在col_1上建立了索引，则可以用索引扫描代替原来的全表扫描，从而提高查询的效率。

8.OR重写并集规则

OR条件重写为并集操作，形如以下SQL示例：

SELECT *
FROM student
WHERE(sex='f' AND sno＞15) OR age＞18;

假设所有条件表达式的列上都有索引（即sex列和age列上都存在索引），数据库可能对于示例中的WHERE语句强迫查询优化器使用顺序存取，因为这个语句要检索的是OR操作的集合。为了能利用索引处理上面的查询，可以将语句改成如下形式：

SELECT *
FROM student
WHERE sex='f' and sno＞15
UNION
SELECT *
FROM student
WHERE age＞18;

改写后的形式，可以分别利用列sex和age上的索引，进行索引扫描，然后再提供执行UNION操作获得最终结果。

2.2.4 条件化简

WHERE、HAVING和ON条件由许多表达式组成，而这些表达式在某些时候彼此之间存在一定的联系。利用等式和不等式的性质，可以将WHERE、HAVING和ON条件化简，但不同数据库的实现可能不完全相同。

将WHERE、HAVING和ON条件化简的方式通常包括如下几个：

❏把HAVING条件并入WHERE条件。便于统一、集中化解条件子句，节约多次化解时间。但不是任何情况下HAVING条件都可以并入WHERE条件，只有在SQL语句中不存在GROUPBY条件或聚集函数的情况下，才能将HAVING条件与WHERE条件的进行合并。

❏去除表达式中冗余的括号。这样可以减少语法分析时产生的AND和OR树的层次。如((a AND b)AND(c AND d))就可以化简为a AND b AND c AND d。

❏常量传递。对不同关系可以使得条件分离后有效实施“选择下推”，从而可以极大地减小中间关系的规模。如col_1=col_2AND col_2=3就可以化简为col_1=3AND col_2=3。操作符=、＜、＞、＜=、＞=、＜＞、LIKE中的任何一个，在col_1＜操作符＞col_2条件中都会发生常量传递。

❏消除死码。化简条件，将不必要的条件去除。如WHERE(0＞1AND s1=5)，0＞1使得AND恒为假，则WHERE条件恒为假。此时就不必再对该SQL语句进行优化和执行了，加快了查询执行的速度。

❏表达式计算。对可以求解的表达式进行计算，得出结果。如WHERE col_1=1+2变换为WHERE col_1=3。

❏等式变换。化简条件（如反转关系操作符的操作数的顺序），从而改变某些表的访问路径。如-a=3可化简为a=-3。这样的好处是如果a上有索引，则可以利用索引扫描来加快访问。

❏不等式变换。化简条件，将不必要的重复条件去除。如a＞10AND b=6AND a＞2可化简为b=6AND a＞10。

❏布尔表达式变换。在上面的内容中，涉及了一些布尔表达式参与的变换（如上一条中的示例是AND的表达式）。布尔表达式还有如下规则指导化简。

○谓词传递闭包。一些比较操作符，如＜、＞等，具有传递性，可以起到化简表达式的作用。如由a＞b AND b＞2可以推导出a＞b AND b＞2AND a＞2，a＞2是一个隐含条件，这样把a＞2和b＞2分别下推到对应的关系上，就可以减少参与比较操作a＞b的元组了。

○任何一个布尔表达式都能被转换为一个等价的合取范式（CNF）。因为合取项只要有一个为假，整个表达式就为假，故代码中可以在发现一个合取项为假时，即停止其他合取项的判断，以加快判断速度。另外因为AND操作符是可交换的，所以优化器可以按照先易后难的顺序计算表达式，一旦发现一个合取项为假时，即停止其他合取项的判断，以加快判断速度。

○索引的利用。如果一个合取项上存在索引，则先判断索引是否可用，如能利用索引快速得出合取项的值，则能加快判断速度。同理，OR表达式中的子项也可以利用索引。

2.2.5 外连接消除

外连接消除是查询优化器的主要功能之一。下面从外连接消除的意义和条件两方面对外连接优化技术进行介绍。

1.外连接消除的意义

外连接操作可分为左外连接、右外连接和全外连接。连接过程中，外连接的左右子树不能互换，并且外连接与其他连接交换连接顺序时，必须满足严格的条件以进行等价变换。这种性质限制了优化器在选择连接顺序时能够考虑的表与表交换连接位置的优化方式。

查询重写的一项技术就是把外连接转换为内连接，转换的意义（对优化的意义）如下：

❏查询优化器在处理外连接操作时所需执行的操作和时间多于内连接。

❏优化器在选择表连接顺序时，可以有更多更灵活的选择，从而可以选择更好的表连接顺序，加快查询执行的速度。

❏表的一些连接算法（如块嵌套连接和索引循环连接等）将规模小的或筛选条件最严格的表作为“外表”（放在连接顺序的最前面，是多层循环体的外循环层），可以减少不必要的IO开销，极大地加快算法执行的速度。

为什么外连接可以转换为内连接？为了弄明白其中的原因，我们先来看一下表2-8（借助PostgreSQL对外连接的注释）。

表2-8 PostgreSQL外连接注释表

下面我们分3种情况讨论表2-8。

情况一：左外连接向内连接转换。

❏观察表2-8，先看θ-连接和左外连接，相同之处在于都具有A部分，不同之处表现在B部分有差异。左外连接比θ-连接多了B部分。这表明左外连接的结果中，会比θ-连接多出“不满足连接条件的外表中的元组（unmatched LHS tuples）”。

❏假设一个左外连接执行之后，其结果等同于内连接，即B部分不存在，则这种情况下，左外连接就可以向内连接转换。这种转换是有条件的，条件是：右面关系中对应的条件，保证最后的结果集中不会出现B部分这样特殊的元组（这样的条件称为“reject-NULL条件”）。

❏不是所有的左外连接都可以向内连接转换，需要满足一定的条件才可以是等价转换。

❏左外连接向内连接转换，语义满足左外连接，但实际结果因两个表中数据的有特点（满足reject-NULL条件）。形式上看是外连接，其实质成为一种褪化的内连接。

情况二：全外连接向左外连接转换。

❏观察表2-8，先看全外连接和左外连接，相同之处在于都具有A、B部分，不同之处表现在C部分有差异。全外连接比左外连接多了C部分。

❏假设一个全外连接执行之后，其结果等同于左外连接，即C部分不存在，则这种情况下，全外连接就可以向左外连接转换。这种转换是有条件的，条件是：左面关系中对应的条件，保证最后的结果集中不会出现C部分这样特殊的元组。

❏不是所有的全外连接都可以向左外连接转换，需要满足一定条件才可以是等价转换。

❏全外连接向左连接转换，形式满足全外连接，但实际结果因两个表中数据的特点，其实质成为一种褪化的左外连接。

❏全外连接向右外连接转换，基本道理等同向左外连接转换，不赘述。

❏全外连接如果能同时向左外连接和右外连接转换，则意味着全外连接能转换为内连接。其条件是：左面和右面关系中对应的条件，均能满足reject-NULL条件。

情况三：右外连接向内连接转换。

❏在实际处理中，因右外连接对称等同左外连接，所以通常都是把右外连接转换为左外连接，然后再向内连接转换。

❏右外连接向左外连接转换，通常是发生在语法分析阶段（这是一种外表样式的转换，但不是全部），在进入查询优化阶段后，才对左外连接和全外连接进行等价转换（进入优化器后执行的这个转换，需要对连接的列和查询的列做判断，所以语法分析阶段没有得到列的详细信息是不能进行此优化的）。

下面我们通过一个例子，来帮助读者对上述知识加深理解。

示例4 具体的示例代码如下：

SELECT * FROM t_1 LEFT JOIN t_2 ON t_2.a=t_1.a WHERE t_2.b = 5;

由上述示例代码可知，左外连接的内表（t_2）不能先于外表（t_1）被访问，所以查询计划优化阶段，只能将表的连接顺序定为(t_1，t_2)，而不是(t_2，t_1)。

如果t_1表的元组数很大，t_2.b上建有唯一索引，但查询效率会很低。但是，如果能交换t_1和t_2的表连接顺序，即表的连接顺序为(t_2，t_1)，则可以利用t_2.b=5条件迅速降低运算的中间规模，提高查询的速度。

2.外连接消除的条件

外连接可转换为内连接的条件：WHERE子句中与内表相关的条件满足“空值拒绝”（reject-NULL条件）。那么条件怎么才算是满足空值拒绝呢？一般认为满足下面任意一种情况时，即满足空值拒绝：

❏条件可以保证从结果中排除外连接右侧（右表）生成的值为NULL的行（即条件确保应用在右表带有空值的列对象上时，条件不满足，条件的结果值为FLASE或UNKOWEN，这样右表就不会有值为NULL的行生成），所以能使该查询在语义上等效于内连接。

❏外连接的提供空值的一侧（可能是左侧的外表也可能是右侧的内表）为另一侧的每行只返回一行。如果该条件为真，则不存在提供空值的行，并且外连接等价于内连接。

示例5 以PostgreSQL对外连接的优化为例，初始数据如下：

create table X (X_num int, X_name varchar(10));
create table Y (Y_num int, Y_name varchar(10));
insert into X values(1, 'X_1');
insert into X values(2, 'X_2');
insert into X values(NULL, 'X_3');
insert into Y values(1, 'Y_1');
insert into Y values(NULL, 'Y_2');
insert into Y values(3, 'Y_3');

例如，如下3种外连接查询语句，外连接处理方式不同。

语句一 表X和Y执行简单左外连接：

SELECT * FROM X LEFT JOIN Y on (X.X_num=Y.Y_num);

语句二 表X和Y执行简单左外连接，但带有WHERE条件且内表Y的连接条件列非空：

SELECT * FROM X LEFT JOIN Y ON (X.X_num=Y.Y_num) WHERE Y.Y_num IS NOT NULL;

语句三 表X和Y执行内连接，带有WHERE条件：

SELECT * FROM X, Y WHERE X.X_num=Y.Y_num;

通过查询计划看优化结果，具体如下：

对于语句一，左外连接不满足优化条件，没有被优化。查询执行计划如下：

test=# EXPLAIN SELECT * FROM X LEFT JOIN Y on (X.X_num=Y.Y_num);
                            QUERY PLAN
------------------------------------------------------------------
Merge Left Join(cost=236.43..461.68 rows=14450 width=36)//左外连接
   Merge Cond: (x.x_num = y.y_num)
   -＞Sort(cost=118.22..122.47 rows=1700 width=18)
       Sort Key: x.x_num
       -＞Seq Scan on x(cost=0.00..27.00 rows=1700 width=18)
   -＞Sort(cost=118.22..122.47 rows=1700 width=18)
       Sort Key: y.y_num
       -＞Seq Scan on y(cost=0.00..27.00 rows=1700 width=18)
(8 rows)

查询语句中只有连接条件X.X_num=Y.Y_num，没有WHERE条件，所以不满足空值拒绝中的任何一个条件，所以查询优化器没有把左外连接优化为连接操作，执行的是归并左外连接操作（Merge Left Join）。

对于语句二，左外连接被优化为内连接，查询执行计划如下：

test=# EXPLAIN SELECT * FROM X LEFT JOIN Y ON (X.X_num=Y.Y_num) WHERE Y.Y_num ISNOT NULL;
                             QUERY PLAN
--------------------------------------------------------------------------------------------
Merge Join(cost=235.88..459.93 rows=14373 width=36)/* 因为存在WHERE子句中内表对应的列满足“空值拒绝”，使得左外连接可以被优化为内连接 */
   Merge Cond: (y.y_num = x.x_num)
   -＞Sort(cost=117.67..121.90 rows=1691 width=18)
       Sort Key: y.y_num
       -＞Seq Scan on y(cost=0.00..27.00 rows=1691 width=18)
           Filter: (y_num IS NOT NULL)
    -＞Sort(cost=118.22..122.47 rows=1700 width=18)
        Sort Key: x.x_num
        -＞Seq Scan on x(cost=0.00..27.00 rows=1700 width=18)
(9 rows)

查询语句除了连接条件X.X_num=Y.Y_num外，包含WHERE条件（Y.Y_num IS NOT NULL），满足空值拒绝中的第一个条件，所以查询优化器把左外连接优化为连接操作，执行的是归并连接操作（Merge Join）。

对于语句三，内连接等价于上一种的可被优化的左外连接，查询执行计划如下：

test=# explain SELECT * FROM X, Y WHERE X.X_num=Y.Y_num;
                             QUERY PLAN
-----------------------------------------------------------------------------------------
Merge Join (cost=236.43..461.68 rows=14450 width=36)//内连接
   Merge Cond: (x.x_num = y.y_num)
   -＞Sort(cost=118.22..122.47 rows=1700 width=18)
       Sort Key: x.x_num
       -＞Seq Scan on x(cost=0.00..27.00 rows=1700 width=18)
   -＞Sort (cost=118.22..122.47 rows=1700 width=18)
       Sort Key: y.y_num
       -＞Seq Scan on y(cost=0.00..27.00 rows=1700 width=18)
 (8 rows)

普通查询语句连接条件为X.X_num=Y.Y_num，查询优化器把执行连接操作等价于上一种的可被优化的左外连接，查询执行计划除花费（cost）外完全相同。

最后，可以通过执行上两条SQL语句，查看查询结果，验证两者等价。具体结果如下：

test=# SELECT * FROM X, Y WHERE X.X_num=Y.Y_num;
x_num | x_name | y_num | y_name
----------+------------+-----------+--------
    1 | X_1 |1 | Y_1
(1 row)
test=# SELECT * FROM X LEFT JOIN Y on (X.X_num=Y.Y_num) WHERE Y.Y_num IS NOT NULL;
x_num | x_name | y_num | y_name
----------+------------+-----------+--------
    1 | X_1 |1 | Y_1
(1 row)

注意

对于外连接的查询优化，从格式上看用户书写的SQL可能是语句一的格式，但这种格式因其他原因，存在被改写为语句二的格式的可能。查询优化前通过对条件的分析，就是要确认是否可以为语句一的格式找到满足语句二的格式中的WHERE Y.Y_num IS NOT NULL类似条件，如果能找到这样的条件，则查询优化器可自动对第一种左外连接做优化，转换为语句二的格式。

2.2.6 嵌套连接消除

多表连接有时会存在嵌套的情况。对于一个无嵌套的多表连接，表之间的连接次序是可以交换的，这样能灵活求解不同连接方式的花费，进而得到最小花费的连接方式。而嵌套连接则不能够利用交换表的位置而获得优化。

那么，什么是嵌套连接呢？

当执行连接操作的次序不是从左到右逐个进行时，就说明这样的连接表达式存在嵌套。看下面的例子：

SELECT *
FROM t1 LEFT JOIN (t2 LEFT JOIN t3 ON t2.b=t3.b) ON t1.a=t2.a
WHERE t1.a ＞ 1

先t2与t3连接，得到中间结果{t2t3}后再与t1连接，这种方式就是嵌套连接，括号不可以去掉，没有去掉括号的等价形式。如果连接顺序是t1、t2、t3，则不存在嵌套。

另外，如下格式也是嵌套，这种格式用括号把连接次序做了区分。

SELECT * FROM A JOIN (B JOIN C ON B.b1=C.c1) ON A.a1=B.b1 WHERE A.a1 ＞ 1;

上面的格式可以等价转换为（圆括号去掉，不影响原先语义）下面的格式：

SELECT * FROM A JOIN B JOIN C ON B.b1=C.c1 ON A.a1=B.b1 WHERE A.a1 ＞ 1;

综上所述，我们得到以下两条结论：

❏如果连接表达式只包括内连接，括号可以去掉，这意味着表之间的次序可以交换，这是关系代数中连接的交换律的应用。

❏如果连接表达式包括外连接，括号不可以去掉，意味着表之间的次序只能按照原语义进行，至多能执行的就是外连接向内连接转换的优化，该部分的内容详见2.2.5节。

2.2.7 连接消除

根据不同分类角度，连接可以分成很多种：根据连接语义方式的不同分为内连接、外连接、半连接、反半连接等；根据连接对象的不同分为自连接（FROM子句后同一个表出现多次，并连接）和非自连接；根据连接条件的有无分为笛卡儿积式的连接和带有限定条件的连接；根据连接条件形式的不同分为等值连接（如支持=）和范围连接（如支持＞、＜、＜＞）。

有的连接类型可能有特定的优化方式（如外连接可优化）。除了以上可能的连接类型外，在某些特殊的情况下（例如下文的情况一、情况二、情况三），可能存在一些连接，这些连接中的连接对象可以被去掉（因为这样的连接对象存在只会带来连接计算的耗费，而对连接结果没有影响），所以这类连接存在优化的可能，其中的一些连接是可以消除掉的。

下面我们就分情况看看这些连接。

情况一：主外键关系的表进行的连接，可消除主键表，这不会影响对外键表的查询。

例如，创建表定义如下：

CREATE TABLE B (b1 INT, b2 VARCHAR(9), PRIMARY KEY(b1));
CREATE TABLE A (a1 INT, a2 VARCHAR(9), FOREIGN KEY(a1) REFERENCES B(b1) );
CREATE TABLE C (c1 INT, c2 VARCHAR(9));

对于关系A、B、C，如果存在A参照B（连接条件上是主外键关系，A依赖于B），且三者之间的连接条件是等值连接（A join B join C，连接条件是A.a1=B.b1AND B.b1=C.c1），结果集不包含关系B中的任何属性，且在B上没有任何限定条件，那么A的连接条件上添加连接属性不为空的限制后（因为A.a1=B.b1连接，而B.b1是主键，不为NULL），可以去除关系B，这样优化不会影响结果（即优化为A join C，连接条件变为A.a1=C.c1AND A.a1IS NOT NULL；因为等值连接A.a1=C.c1，如果遇到NULL=NULL的情况，通常的处理都是FALSE，所以。以上条件可以进一步简化为A.a1=C.c1，但请注意A依赖于B的条件不变）。

如果关系A、B、C中B没有主键（主键保证了非空约束的存在），则当B.b1=NULL时，A.a1和C.c1为非NULL时，A.a1=C.c1的连接方式（即消除B的连接方式）和A.a1=B.b1AND B.b1=C.c1的连接方式（即没有消除B的连接方式）相比，前一种连接方式比后一种产生了新的元组，所以不存在连接可以消除的可能。

再进一步，如果关系A、B、C中B有主键，但A不依赖于B（无主外键关系），三者之间的连接条件是等值连接（A join B join C，连接条件是A.a1=B.b1AND B.b1=C.c1），因为B有主键，意味着B非NULL所以A.a1和C.c1都应该为非NULL，才可能保证连接可以消除（连接条件变为A.a1=C.c1AND A.a1IS NOT NULL AND C.c1IS NOT NULL）。但实际上不是这样，B和A没有依赖关系的时候，单纯靠A、C之间的条件，因为去掉B使得A中存在的值没有受到B的限制，所以不能保证B可被放心地去掉。在有主外键约束的情况下，A.a1依赖B.b1使得A.a1的值范围受到约束（A.a1的值在生成时已经参照了B.b1)，所以可以放心地去掉B。

如果对于关系A、B存在A参照B（连接条件上是主外键关系，A依赖于B），且二者之间的连接条件是等值连接（A join B，连接条件是A.a1=B.b1），则经过连接消除，二表连接变为单表扫描（A.a1IS NOT NULL），这样能有效提高SQL的执行效率。

情况二：唯一键作为连接条件，三表内连接可以去掉中间表（中间表的列只作为连接条件）。

举例说明，假设3个表都有唯一键存在，如下所示：

CREATE TABLE A (a1 INT UNIQUE, a2 VARCHAR(9), a3 INT);
CREATE TABLE B (b1 INT UNIQUE, b2 VARCHAR(9), c2 INT);
CREATE TABLE C (c1 INT UNIQUE, c2 VARCHAR(9), c3 INT);

B的列在WHERE条件子句中只作为等值连接条件存在，则查询可以去掉对B的连接操作。

SELECT A.*, C.* FROM A JOIN B ON (a1=b1) JOIN CON (b1=c1);

相当于：

SELECT A.*, C.* FROM A JOIN C ON (a1= c1);

情况三：其他一些特殊形式，可以消除连接操作（可消除的表除了作为连接对象外，不出现在任何子句中，创建表的语句参见情况一）。示例如下：

SELECT MAX(a1) FROM A, B;/* 在这样格式中的MIN、MAX函数操作可以消除连接,去掉B表不影响结果;其他聚集函数不可以 */
SELECT DISTINCT a3 FROM A, B; /* 对连接结果中的a3列执行去重操作*/
SELECT a1 FROM A, B GROUP BY a1;/* 对连接结果中的a1列执行分组操作 */

2.2.8 语义优化

因为语义的原因，使得SQL可以被优化。这里包括以下两个基本概念：

❏语义转换。因为完整性限制等的原因使得一个转换成立的情况称为语义转换。

❏语义优化。因为语义转换形成的优化称为语义优化。

通常，任何的完整性限制条件等都可以用于语义优化。语义转换其实是根据完整性约束等信息对“某特定语义”进行推理，进而得到的一种查询效率不同但结果相同的查询。语义优化是从语义的角度对SQL进行优化，不是一种形式上的优化，所以其优化的范围，可能覆盖其他类型的优化范围。

语义优化常见的方式如下：

❏连接消除（Join Elimination）。对一些连接操作先不必评估代价，根据已知信息（主要依据完整性约束等，但不全是依据完整性约束）能推知结果或得到一个简化的操作。例如，利用A、B两个基表做自然连接，创建一个视图V，如果在视图V上执行查询只涉及其中一个基表的信息，则对视图的查询完全可以转化为对某个基表的查询。

❏连接引入（Join Introduction）。增加连接有助于原关系变小或原关系的选择率降低。

❏谓词引入（Predicate Introduction）。根据完整性约束等信息引入新谓词，如引入基于索引的列，可能使得查询更快。如一个表上，有c1＜c2的列约束，c2列上存在一个索引，查询语句中的WHERE条件有c1＞200，则可以推知c2＞200，WHERE条件变更为c1＞200AND c2＞200AND c1＜c2，由此可以利用c2列上的索引，对查询语句进行优化。如果c2列上的索引的选择率很低，则优化效果会更高。

❏检测空回答集（Detecting the Empty Answer Set）。查询语句中的谓词与约束相悖，可以推知条件结果为FALSE，也许最终的结果集能为空；如CHECK约束限定score列的范围是60到100，而一个查询条件是score＜60，则能立刻推知条件不成立。

❏排序优化（Order Optimizer）。ORDERBY操作通常由索引或排序（sort）完成；如果能够利用索引，则排序操作可省略。另外，结合分组等操作，考虑ORDERBY操作的优化。

❏唯一性使用（Exploiting Uniqueness）。利用唯一性、索引等特点，检查是否存在不必要的DISTINCT操作，如在主键上执行DISTINCT操作，若有则可以把DISTINCT消除掉。

例如：

CREATE TABLE student (name VARCHAR(30) NOT NULL, age INT);

可被优化为如下形式：

SELECT * FROM student WHERE name IS NULL AND age＞18;

在上面的例子中，name列被定义为非空，这是完整性限制，但查询条件和语义相悖，则可以直接返回name IS NULL=false，进而false AND age＞18=false，查询语句可以终止。

2.2.9 针对非SPJ的优化

如果查询中包含GROUPBY子句，那么这种查询就称为非SPJ查询。

现在，决策支持系统、数据仓库、OLAP系统的应用日益广泛，SQL语句中的GROUPBY、聚集函数、WINDOWS函数（分析函数）等成为SQL语言的重要特性，被应用广泛。

早期的关系数据库系如System-R，对GROUPBY和聚集等操作一般都放在其所在的查询的最后进行处理，即在执行完所有的连接和选择操作之后再执行GROUPBY和聚集。这样的处理方式比较简单，而且编码容易，但执行效率会比较低。所以，现代的商业数据库和开源的数据库，通常都使用了一些非SPJ的优化技术。

1.GROUPBY优化

对于GROUPBY的优化，可考虑分组转换技术，即对分组操作、聚集操作与连接操作的位置进行交换。常见的方式如下：

❏分组操作下移。GROUPBY操作可能较大幅度地减少关系元组的个数，如果能够对某个关系先进行分组操作，然后再进行表之间的连接，很可能提高连接效率。这种优化方式是把分组操作提前执行。下移的含义，是在查询树上让分组操作尽量靠近叶子结点，使得分组操作的结点低于一些选择操作。

❏分组操作上移。如果连接操作能够过滤掉大部分元组，则先进行连接后进行GROUPBY操作，可能提高分组操作的效率。这种优化方式是把分组操作置后执行。上移的含义和下移正好相反。

对于带有GROUPBY等操作的非SPJ格式的SQL语句，在本节之前提及的技术都适用，只是结合了GROUPBY操作的语义进行分组操作。因为GROUPBY操作下移或上移均不能保证重写后的查询效率一定更好，所以，要在查询优化器中采用基于代价的方式来估算某几种路径的优劣。

另外，GROUPBY、ORDERBY优化的另外一个思路是尽量利用索引，这部分内容将在3.3节详细讨论。

2.ORDERBY优化

对于ORDERBY的优化，可有如下方面的考虑：

❏排序消除（Order By Elimination，OBYE）。优化器在生成执行计划前，将语句中没有必要的排序操作消除（如利用索引），避免在执行计划中出现排序操作或由排序导致的操作（如在索引列上排序，可以利用索引消除排序操作）。

❏排序下推（Sort push down）。把排序操作尽量下推到基表中，有序的基表进行连接后的结果符合排序的语义，这样能避免在最终的大的连接结果集上执行排序操作。

3.DISTICT优化

对于DISTICT的优化，可有如下方面的考虑：

❏DISTINCT消除（Distinct Elimination）。如果表中存在主键、唯一约束、索引等，则可以消除查询语句中的DISTINCT（这种优化方式，在语义优化中也涉及，本质上是语义优化研究的范畴）。

❏DISTINCT推入（Distinct Push Down）。生成含DISTINCT的反半连接查询执行计划时，先进行反半连接再进行DISTICT操作，也许先执行DISTICT操作再执行反半连接更优，这是利用连接语义上确保唯一功能特性进行DISTINCT的优化。

❏DISTINCT迁移（Distinct Placement）。对连接操作的结果执行DISTINCT，可能把DISTINCT移到一个子查询中优先进行（有的书籍把这项技术称为“DISTINCT配置”）。

2.3 启发式规则在逻辑优化阶段的应用

逻辑优化阶段使用的启发式规则通常包括如下两类。

❏一定能带来优化效果的，主要包括：

○优先做选择和投影（连接条件在查询树上下推）。

○子查询的消除。

○嵌套连接的消除。

○外连接的消除。

○连接的消除。

○使用等价谓词重写对条件化简。

○语义优化。

○剪掉冗余操作（一些剪枝优化技术）、最小化查询块。

❏变换未必会带来性能的提高，需根据代价选择，主要包括：

○分组的合并。

○借用索引优化分组、排序、DISTINCT等操作。

○对视图的查询变为基于表的查询。

○连接条件的下推。

○分组的下推。

○连接提取公共表达式。

○谓词的上拉。

○用连接取代集合操作。

○用UNIONALL取代OR操作。

2.4 本章小结

本章从逻辑查询优化的基础关系代数讲起，首先简略概述了关系代数的基础知识，这部分不侧重关系代数原理的推导和证明，重点在于描绘关系代数的主要概念，分析关系代数的原理对查询优化的指导意义，为查询优化技术做铺垫；然后以PostgresSQL为示例，全面分析了查询优化可用的技术，这是本章的重点；最后对查询优化技术做了一个简单总结，从整体上提升对查询优化的理解和认识。