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

1 引言
    随着各个应用领域信息化程度日益提高，数据库中的数据量迅猛增长，导致数据库系统的查询性能下降。但是一个数据库应用系统的查询性能直接影响到系统的推广和应用，因此数据库系统性能和查询优化成为数据库应用领域备受关注的热点问题。
    影响数据库系统性能的因素很多，包括数据库连接方式、应用系统架构、数据库设计、管理等。其中最本质又至关重要的是数据库管理系统本身的查询优化技术。在数据库系统开发中，用户业务逻辑必须转换成数据库查询语言执行，或将数据库查询语言嵌入在宿主语言程序中执行。通过分析关系代数表达式的等价变换准则及查询代价，于给定的SQL查询与关系代数表达式对应关系，研究并分析基于关系代数等价变换规则的SQL查询优化。

2 关系代数表达式的等价变换规则
    数据库查询是指从数据库中提取数据的一系列活动，包括：将高级数据库语言表示的查询语句翻译为能在文件系统这一物理层次上实现的表达式，为优化查询进行各种转换，生成可供执行的查询计划。对于数据库的查询要求可通过关系代数的运算(操作)表达，而在SQL语言中通过SELECT语句实现查询要求。南于关系代数运算与SELECT语句描述之间存在着对应关系，凶此可将数据库查询转换成关系代数运算，并利用关系代数等价变换规则生成优化SOL的查询计划。
2．1 关系代数等价变换规则
    设E、E1、E2和E3是关系代数表达式，A1,…，An和B1，…，Bm是属性名，且A1,…，An是B1，…，Bm的子集，F、F1、F2和F3是条件表达式。则有常用的等价变换规则如表1所示。

2．2 查询代价分析
    从优化的角度考虑，规则1与规则2等价变换前后的中间结果规模几乎不发生变化，因此无需考虑优化问题。但规则3～规则10变换前后中间结果规模会发生变化，例如规则3若选取的条件F只与E1有关，那么先进行E1的条件选取，再与E2笛卡尔积的时间代价将大大减少，下面通过例子进行查询代价分析。
    假设关系E1有106个元组，关系E2有103个元组。那么执行E1xE2，则有109个元组。若条件F只与E1有关，且满足F的选择性为0．1％，则意味着只有103个元组满足条件，而另外的1O9-103个元组都不满足条件。因此将σF(E1xE2)等价变换为σF(E1)xE2后，其中间结果σF (E1)的规模仅103元组。若1个物理块可允许存放100个E1元组，10个E2元组，而主存中可允许存放10块E1元组，1块E2元组，以下估计分析等价变换前后的查询代价。
2．2．1 等价变换前查询代价估计分析
    等价变换前查询代价是指采用σF(E1)xE2方式所需花费的查询代价。下面分别从E1×E2和σF两个方面分析：
    (1)E1×E2代价估计E1xE2代价估计主要是从磁盘读块和中间结果写盘的时间考虑，而对主存中数据的处理时间忽略不计。
    E1xE2读块总数=E1的块数+E2的块数×读E2的遍数=104+100x103=110 000块。若每秒可以读50块，读块时间为2 200 s(约0．6 h)。连接后的元组数为109，若每块可存放10个元组，那么写中间结果需要的时间是108/50=2x1 06 s。故E1xE2花费的时间为2×106 s+2．2×103s≈556．2 h。
    (2)σF代价估计 σF运算时需将E1xE2的中间结果依次读入内存进行运算，凶此需要108／50=2×106s；满足条件的103个元组，共需100个块写回磁盘，需2 s。故σF花费的时间为2x106s+2．2x103s≈556．2 h。
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个问题：第一，无法产生全部可能的、并可供选择的查询计划；第二，无法准确地估计查询成本。另外，查询处理的代价通常取决于磁盘的访问，因为磁盘的访问比内存访问速度慢得多，就所需的磁盘访问次数而言，策略好坏差别很大，甚至相差几个数量级。所以，对于一个给定的查询，查询优化器系统如何快速选择一个生成成本相对较小的查询计划很值得研究。