关系代数与SQL查询优化的研究

2．2．2 等价变换后查询代价估计分析

等价变换后查询代价是指采用σF(E1)xE2方式所需花费的查询代价。σF(E1)代价估计约为200 s，读E2的时间为2 s。又由于读E1进行选择的同时将满足条件的元组与E2连接，形成的中间结果有103全部可以放在主存，故无需写盘时间。从分析可知，等价变换后查询代价约为202 s。

2．3 关系代数表达式的优化规则

由上述分析可知，一个关系代数表达式可以有多种查询方案，每个方案的代价相差几个数量级，特别是当查询非常复杂的时候。因此生成一个好的查询方案非常重要。

但需要看到，生成每个可能的方案和测算代价需花费大量的时间，而生成的却可能是即将被抛弃的方案。解决办法是定义一般的优化规则，从而避免DBMS查询优化器枚举出一些差的方案。针对给定的查询问题，通常有以下优化规则：

规则1：尽量将选择和投影运算提前，以减少元组数和关系大小。

　规则2：把某些选择运算和笛卡尔积相结合，即将选择运算附加在连接运算上，可减少中间结果保存以备后用的时间代价。

　规则3：对同一关系上的多个选择和投影运算同时进行，以避免重复扫描同一关系。

　规则4：把投影操作和连接运算结合起来执行。

3 SQL查询优化

查询优化是为查询选择最有效的查询计划过程。查询优化一方面是在关系代数级进行优化，目的是力图找出与给定查询等价，但执行效率更高的一个表达式。

3．1 等价变换策略

查询优化的另一方面涉及查询语句处理的详细策略的选择，例如选择执行运算所采用的具体算法以及将使用的特定索引等。事实RDBMS优化器的查询优化从给定的SQL查询开始，转换查询形式，直至所得到的形式依据某些规则是最优的。选择与投影等价变换策略有：

策略1：对同一关系的多个选择可以转换为一个用and连接的选择操作。例如：Select A1，…，AnFrom E where F1=

(Select A1 From E where F2)XXXXXXXXXXXXXXXXXXXXXSelect A1，…，AnFrom E where F1and F2。原始的查询意味着要对E进行2次扫描，而变换后只需要1次。

策略2：对同一关系连续的多个投影可转换为仅含最后一个投影的操作。例如：Select A1，…AnFrom E(Select B1，…，Bm From E)XXXXXXXXXXXXXXXXXXXXXSelectA1，…，AnFrom E。因为A1，…，An∈B1，…，Bm，所以根据表1规则9等价于直接对子集A1,…，An投影。

策略3：投影后的选择操作可转换为选择操作后的投影操作，例如：Select A1,A2 From E1 Where A1=(Select B1 From E2Where B2>F2)等价于A1,A2 From E1E2Where A1=B1 And B2>F2。

经等价变换使得条件A1=B1 And B2>F2满足时再进行投影，这样可减少中间结果的规模。

策略4：投影操作在并操作、交操作和连接操作上满足分配律。例如：σF(E1∪E2)=σF(E1)∪σF(E2)等价于Select A1，A2From E1 Where F union Select B1，B2 From E2 Where F。对于E1，E2若在不同的服务器上，先进行本地服务器上的选择再进行并行运算将减少查询代价。

策略5：并操作和交操作满足吸收律，即：E1∪(E1∩E2)=E1或E1 ∩(E1 UE2)=E1。例如：Select*From E1 union(Select*E1 From insersect Select* From E2)等价于Select *From E1。等价变换前对E1扫描2次，E2扫描1次，但等价变换后仅对E1扫描1次。

3．2 成本最小的查询计划

数据库查询优化器是关系数据库服务器的一个组成部分。基于成本的数据库查询优化器的任务是通过产生可供选择的查询计划，找到最低估算成本的查询计划来优化一条SQL语句，其过程如图1所示。查询计划对SQL语句性能十分重要。当一条SQL 语句被送人RDBMS服务器，将被解析并提交给数据库查询优化器。查询优化器进行查询等价变换，并对查询表达式进行评估，以产生若干可供选择的查询计划。估计每个待选的查询计划的成本，选用成本最小的查询计划，最终生成可执行的SQL语句。

4 结束语

数据库查询优化器生成查询计划存在2个问题：第一，无法产生全部可能的、并可供选择的查询计划；第二，无法准确地估计查询成本。另外，查询处理的代价通常取决于磁盘的访问，因为磁盘的访问比内存访问速度慢得多，就所需的磁盘访问次数而言，策略好坏差别很大，甚至相差几个数量级。所以，对于一个给定的查询，查询优化器系统如何快速选择一个生成成本相对较小的查询计划很值得研究。

作者：王峥,王亚平 西安外事学院 来源：国外电子元器件