数据库查询优化器

引言

我们知道，目前通用的数据库查询语言是SQL语言（Structured Query Language）。SQL语言也是一种编译型语言，需要SQL编译器编译后才能执行，但它与C、C++、Java等语言不同，SQL语言是一种非过程化语言，这意味着使用SQL进行操作的时候，你只需要指定你要达到什么目的，而无需指明要怎样达到目的。比如要查询EMPLOYEE的所有行，使用语句“Select * From EMPLOYEE”就行了，不需要规定该怎样查询这些行。

既然用户只需要解决“做什么”的问题，那么，“怎么做”的问题由谁来解决呢？这正是本文要讨论的问题。

优化器（Optimizer）

优化器

解决“怎么做”问题的工具就是“优化器”。优化器也称查询优化器（Query Optimizer）【注意这里的“查询”并不仅仅指Select操作，包括Select，Update，Delete，Insert等等在内的任何带WHERE条件子句的SQL操作都包含查询操作的】。它的主要工作是优化数据访问，根据提交的SQL语句，综合各种已有的信息（主要是系统编目表）来产生最优的可执行的访问方案。

优化器在整个数据库系统中占据着至高无上的地位，它是数据库性能的决定因素，是所有数据库引擎中最重要的组件。当前所有的数据库产品中，DB2的优化器是最强大的。这一点也是大多数拥有海量数据的企业选择DB2的主要原因。（事实上，70%以上的世界500强企业使用DB2作为主数据库）

优化器的工作可以直观的理解为以下4个步骤：

1.接收并验证SQL语句的语法语义；

2.分析环境并优化满足SQL语句的方法；

3.创建计算机可读指令来执行优化的SQL；

4.执行指令或存储他们以便将来执行。

这其中的第2步是本文讨论的重点。至于优化器的其他内容，不介绍也不知道。

SQL语句执行过程

先来看看SQL语句的大致执行流程（SQL编译器是优化器的组成部分）：

简述一下整个流程：

1.语法分析（Parse Query）

SQL语句被提交给SQL编译器，编译器分析该语句，检查其语法（Parse Query：语法分析），如果存在语法错误，编译器就停止处理并返回错误信息；如果不存在语法问题，编译器会将SQL语句转换为可被优化器分析的关系代数语句，并据此创建该查询的查询图模型（Query Graph Model，又称语法树）。

2.语义检查（Check Semantics）

语法分析完成后，编译器会根据查询图模型进行语义检查（比如检查语句中的数据类型是否与数据库的表列的数据类型一致），语义检查完成后也会将相关信息添加到查询图模型，包括参考约束，表检查约束，触发器，和视图信息等。

3.查询重写（Rewrite Query）

如果SQL语句的语法语义都没有问题，就可以正式进行查询操作了。这是优化器进行查询优化的开始阶段，DB2优化器三大组件之一的查询重写器（Query Rewriter）就是处理这一工作的。其目的是将提交的SQL语句优化成效率更高的形式，这种优化可以是基于查询成本的考虑，也可以是基于查询规则的考虑。举一个直观的例子：

考虑下面两条SQL语句（查询工龄为5年的员工及其所享有的年终奖级别）：

Select EMPLOYEE.Name , WELFARE .Bonus From EMPLOYEE , WELFARE Where EMPLOYEE.Seniority > 5 And EMPLOYEE.Seniority = WELFARE .Seniority ;

Select EMPLOYEE.Name , WELFARE .Bonus From EMPLOYEE , WELFARE Where EMPLOYEE.Seniority > 5 And EMPLOYEE.Seniority = WELFARE .Seniority And EMPLOYEE.Seniority > 5;

很显然，两条语句的功能相同，第二条后面的“EMPLOYEE.Seniority = 5”条件还有点多余，那么，那条语句的执行效率更高？

答案是第二条！因为第一条将EMPLOYEE中Seniority>5的行与WELFARE中的所有行作外连接再来找Seniority相等的行，而第二条则是将EMPLOYEE中Seniority>5的行和WELFARE中Seniority>5的行作外连接再来找Seniority相等的行。显然，第二条语句只有更少的行参与外连接，效率自然更高。

可是，我们通常写出的查询语句都是第一条的形式，岂不是会影响效率？这就是查询重写的作用所在了，优化器的查询重写器能自动帮我们完成查询语句的优化，找到更高效的查询形式。当然了，查询重写并不是直接对SQL语句作上述例子那样的优化，它操作的是由语法分析转换过的关系代数语句，且需要根据重写图模型提供的信息作出形式优化。直观上是这么个意思而已。

查询重写完成语句形式的转换后同样会将结果存储在查询图模型中。

4.优化访问计划（Optimizer Access Plan）

根据查询图模型提供的信息，优化器会生成许多能够满足查询请求的访问计划（执行方案方案），然后优化器综合系统编目表中关于表，索引，列和函数等等的统计信息，估计每种访问计划的执行成本，并选择具有最小成本的方案作为最终的访问计划（Acess Plan）。这个进行优化选择的工作是由DB2优化器的另两大组件成本评估器（Estimator）和计划生成器（Plan Generator）完成的。需要注意的是：优化器内部有若干优化度不同的优化算法，优化度越高（优化效果好）的算法所需要的优化时间也是越长的。优化器会根据设定的优化级来选择不同的优化算法。通常数据量越大，越复杂的查询会使用优化度更高的算法，因为执行优化算法所花费的时间对于优化后的查询所带来的缩短查询时间的收益而言是微不足道的。这应该不难理解。

5.生成可执行代码（Generate Executable Code）

根据最终选定的访问计划生成执行代码，类似C语言编译后生成可被机器识别的机器码一样。没什么好说的。

6.执行访问计划（Execute Plan）

执行可执行代码，获取查询结果集。更没什么好说的。

这个流程还有更加细化的步骤划分以及根据环境的不同而增加新的步骤，不去了解。最后要说明的是Visual Explain、db2exfmt、db2expln。它们是DB2数据库系统提供的解释工具，使用它们能够以GUI或者文本的形式查看DB2优化器是如何优化查询以及最终的访问计划的结果。详细说明参见：《使用Explain分析SQL》

查询过程（Query Processing）

以上这么多内容都算是背景知识，到这里才算是真正进入了正题，也就是查询过程所关注的主要问题：访问优化，即SQL查询过程的第4步。

成本估算（Cost Estimation）

成本估算（开销估算）是数据库系统评价一个访问计划优化好坏的标准。对于每一个生成的访问计划，优化器都必须根据相关统计信息（statistics）对其成本进行评估。

成本估算的主要指标是CPU时间和I/O数量。另外计算内存也是一个重要指标，不过这个指标的各个参数在数据库系统初始化时已经设定完成了，优化器并不能对这种硬性参数产生什么影响。所以可以将成本简化为CPU成本+I/O成本。

下面是关于成本估算的结构图：

图中的Statistics(统计信息)和Filter Factor（过滤因子）是系统进行成本估算的主要参考，后面会详细解释。可以看到，总成本（Total Cost）=CPU成本（CPU Cost）+I/O成本（I/O Cost）。而CPU成本（CPU Cost）=基本成本（Base Cost）+页成本（Page Cost）+扫描成本（Scan Cost）+行成本（Row Cost）。注意：所有的成本都指的是时间上的开销，而非硬件设备的开销。下面对这些成本一一进行解释。

I/O Cost

I/O成本指从磁盘取一页数据（一次I/O取一页数据）所花费的时间。关于磁盘存储的文章（《深入理解数据库磁盘存储（Disk Storage）》）中已经介绍过：一次I/O操作的经验时间是1/80秒。

CPU Base Cost

CPU基本成本指不依赖对象大小的一个值固定的CPU时间开销。

CPU Page Cost

CPU页成本指CPU从缓冲池中定位一个数据页的时间开销。

CPU Scan Cost

CPU扫描成本指对数据页中的记录（数据行）进行Sargable谓词扫描所需的时间开销。

Sargable谓词

考虑下面的SQL查询语句：

Select * From EMPLOYEE Where EMPNO = 100 And DEPTNO <> 010

Where条件子句后面的表达式EMPNO=100和DEPTNO<>010就是谓词，=、<>是操作符。所有的SQL谓词中，有些是可以使用索引的，有些则不能，例如在EMPNO和DEPTNO上分别创建了索引，EMPNO=100就可以利用EMPNO的索引优化查询，而DEPTNO<>010就无法使用DEPTNO上的索引了，至于为什么是这样，理解了索引机制就很容易理解了(参看：深入理解DB2索引（Index）)。

IBM就将那些使用了诸如=,>,<,in,like等操作符的可以转化为索引操作的谓词称为Sargable谓词（Sargable是一个自创词，字典中是没有的）。可以译作可索引谓词。

所以CPU Scan Cost可以理解成在数据页中使用可索引谓词来查找符合条件的记录（数据行）的时间开销。

CPU Row Cost

CPU行成本指将数据页中查找到的满足Sargable谓词条件的记录（数据行）复制到线程私有的内存空间以及对这些记录使用不可索引谓词进行进一步筛选所需的时间开销。

实例

现在以一个实例具体看看成本估算的计算过程。

考虑查询语句：

Select C1，C2 From T1 Where C1=100 And Length(C2) >5 (=是可索引谓词[Sargable]，但Length()>则是不可索引谓词[Residual])

现在假设：

一次I/O开销是10ms；

T1表占用的数据页数量为500页；

记录数为10000条；

CPU Base Cost为2ms；

CPU Page Cost为1ms/page；

CPU Scan Cost为0.1ms/record；

CPU Row Cost为0.5ms/record;

filter factor为0.25，filter factor为过滤因子，指具有相同搜索码的记录的条数(本例中C1=100的记录数)占总记录数的比例。则满足C1=100条件的记录为10000*filter factor条。

则总成本Total Cost = I/O Cost + CPU Cost = I/O Cost + Base Cost + Page Cost + Scan Cost + Row Cost

=500*10 + 2 + 1*500 + 0.1*10000 + 0.5*10000*0.25

=7752 ms

权重（Weight）

当然了，上面的计算只是理论上的，实际上由于硬件的不同和实际需要的不同，对于CPU开销和I/O开销这两个指标的相关值并不是一定的，考虑的侧重点也往往是不同的，例如，访问计划Plan1的CPU成本为10 CPU seconds，I/O成本为100 reads；访问计划Plan2CPU成本为5 CPU seconds，I/O成本为500 reads。哪一个更优呢？

数据库系统的策略是根据情况的不同为这两个指标各增加一个权重，比如CPU 成本的权重W1为0.3，I/O成本的权重W2为0.7，则Cost（plan）=Cost（CPU）*W1+Cost（I/O）*W2。这样就可以进行比较了。

timeron

实际上，DB2所参照的成本指标更多且计算方法更加复杂，不仅有时间上的考虑，利用率，资源占用量等等其他方面的因素也被纳入成本估算的考量。这些不同量使用特定的算法计算得出的值使用了一个新的计量单位timeron，timeron 是IBM发明出来的计量单位，没有公式可用来将 timeron 的数量转换成执行一次查询所需的时间（以秒表示）或者比率，数量。。。但是只要比较timeron的值就可以比较若干个访问计划的优劣。

由于timeron 综合了时间、CPU 利用率、I/O 和其它因素。这些参数值是变化的，因此执行某个查询所需的 timeron 数量是动态的，每次执行该查询所需的 timeron 都可能不同。

统计信息（Statistics）

正如上图表示的，一个查询优化器想要对访问计划进行评估并选择最优的访问计划，就必须知道评估所需的各种信息，这些信息包括各种表，行，索引，数据页占用，列值等数据库对象的方方面面的信息。这些信息就被统称为统计信息。无信息，无优化，只有掌握足够的统计信息，优化器才可能进行更准确的估算，作出更优化的选择。统计信息被保存在系统编目表（System Catalog）中。

但是需要特别注意的是：统计信息并不是自动收集（gather）的，对数据库的某些诸如table load、index create等操作对数据库的改变并不会被自动更新到系统编目表的统计信息中，比如对于查询：

Select * From EMPLOYEE Where DEPTNO = 010

如果没有为DEPTNO创建索引，数据库系统就只能对EMPLOYEE表进行表扫描了，而如果后来添加了索引，再进行上述查询，系统仍然只能进行表扫描，因为系统编目表中并没有这条索引的信息，优化器就无法探知该索引的存在，只能使用旧的统计信息进行优化了。

因此，为了使这些更新马上被统计信息收录并为优化器所用，需要使用一条特殊的命令强制数据库系统将表或索引的统计信息更新到系统编目表中。DB2数据库使用RUNSTATS命令完成这一收集操作，Oracle则使用Analyze命令实现。

需要说明的是：从DB2 V9开始拥有了自动维护的特性，其中就包括统计信息的自动收集。数据库系统会自动判断哪些情况需要进行统计信息收集工作并自动进行统计信息的更新。无需再由DBA手动进行这一操作。Oracle从10g版开始也加入了这一特性。

过滤因子（Filter Factors）

过滤因子是数据库系统中一个非常重要的概念，它是数据库优化器进行优化的一个重要参数。过滤因子源于DB2对于查询优化的需要。Oracle中也引入了这一概念。其作用笼统的说就是过滤。

对于一个特定的谓词P，我们认为P的过滤因子为表中满足谓词P的约束条件的行数占表中所有行数的比例。记为FF(P);

例如查询：

Select * From EMPLOYEE Where EMPNO=101

假设EMPLOYEE表中总共有1000行，由于EMPNO是主键，所以满足EMPNO=101的只有一行。因此FF(EMPNO=101)=1/1000=0.001;

再比如查询：

Select * From EMPLOYEE Where SALARY Between 50000 And 100000

假设EMPLOYEE表中总共有1000行，工资介于50000到100000的员工有20人，则FF(SALARY Between 50000 And 100000)=20/1000=0.02;

过滤因子对优化器在索引的选择上有非常重要的影响，会和统计信息一起单独介绍，这里不细说。

解释计划（Explain Plan）

DB2和Oracle都提供了访问计划解释工具，可以使用这些工具查看优化器是如何进行访问计划的优化以及最终选择了怎样的访问计划。

DB2提供的工具有四种：db2expln命令、dynexpln命令、db2exfmt命令和Visual Explain。

db2expln命令可以用于查看系统编目表中存储的静态SQL包（静态SQL语句编译后生成SQL包），另外也可以动态的执行SQL语句。但是无论如何，该命令只能查看优化器最终选择的访问计划的信息。dynexpln命令作用类似db2expln，用于兼容DB2早期版本产品。

db2exfmt命令则可以查看包括统计信息在内的优化器详细信息，能够呈现优化器详细的优化过程。

Visual Explain是以图形化的形式呈现优化器详细信息，相当于db2exfmt命令的GUI呈现方式。

其中db2expln、dynexpln、db2exfmt命令支持以文本信息方式和文本树模型方式显示信息，Visual Explain支持以文本信息和可视化树模型的方式显示信息。

关于解释工具的详细介绍可以参看：《使用Explain分析SQL》

另外，还可以使用一个特殊的Explain Plan SQL语句生成访问计划，该语句会对SQL语句进行编译并将生产的访问计划存储在若干解释表中。注意：数据库创建时并不会自动创建这些表，因为它们对于数据库性能没有存在意义。如果需要使用Explain Plan语句就必须先手动创建这些表才行。数据库通常会提供创建这些表的SQL脚本（DB2数据库创建解释计划表的方式参看：《使用Explain分析SQL》）。DB2数据库下该语句的格式为：

EXPLAIN PLAN [SET QUERYNO = n] [SET QUERYTAG = 'string'] FOR explainable-sql-statement //可选参数还有很多

QUERYNO表示查询号，用于为生成的访问计划提供一个编号，方便查询生成的访问计划。例如：

explain plan set queryno = 1000 for "select * from employee where salary>70000" //为一条SQL语句创建访问计划

select * from explain_statement where queryno = 1000 //查询创建的访问计划的详细信息

Oracle数据库下该语句格式为：

EXPLAIN PLAN [SET STATEMENT_ID = 'text-identifier'] [INTO [schema.]tablename] FOR explainable-sql-statement

语句结构上大同小异，就不举例了。

要说明的是，Explain plan语句只是对SQL语句进行编译生成了访问计划，并没有进行执行，不会产生输出结果。

过程化级（Procedural Steps）

prcedural steps又称procedural access steps 或 access steps。指的是查询过程中的各种数据访问方式，由于这些方式在效率上是逐级递增（递减）的，优化器会按照效率级别选择访问方式，所以将这些访问方式成为过程化级（procedural steps），并不是表示在查询过程中会依次使用这些访问方式。不过有些查询是需要几种访问方式结合使用的。为了便于理解，后面还是称procedural steps为访问方式吧。

典型的访问方式只有2类，这两类中又分若干小类：

表扫描（Table Scan）

扫描表中的所有行来查找所需数据行。有时候表扫描又可称表空间扫描(Tablespace Scan)，因为有的系统上的数据库系统允许一个Extent上存在不同的表数据，用表扫描表述不准确。

索引扫描（Index Scan）

通过扫描索引来定位所需数据行。索引扫描的情况非常复杂，又分为唯一索引扫描，非匹配索引扫描，匹配索引扫描，只扫描索引等几种，这些方式甚至还可以继续划分，而且按照具体情况的不同，还有简单索引，复合索引，多索引之分等等。另外，还有一种访问方式称为直接索引查找，这种使用索引的访问方式并不需要进行扫描工作，可以自己查找定位，我们仍然直接将其归为索引扫描。